Dengeli ağaç

Yükseklik farkının en fazla 1 olduğu AVL ağacını öğrenirsin.

Dengeli ağaç

AVL ağacı, her düğümün sol ve sağ alt ağaçlarının yükseklikleri arasındaki farkın (denge faktörü) en fazla 1 olduğu bir BST'dir. Bu, otomatik denge sağlar.

Denge faktörü height(left) - height(right). -1, 0 veya +1 olmalıdır. Aksi halde döndürme (rotation) ile düzeltilir.

AVL sayesinde arama, ekleme, silme her zaman O(log n) olur; dengesiz BST'nin O(n) kötü durumundan kaçınılır.

Denge faktörü hesabı

Her düğüm için denge faktörü bf = height(left) - height(right) ile hesaplanır. Ekleme ve silme sonrası bu değer değişebilir.

bf > 1 ise sol ağırlıklı, bf < -1 ise sağ ağırlıklı. Bu durumlar döndürme gerektirir.

Denge faktörü, ağacın çarpık olup olmadığını tek bakışta gösterir; AVL'nin temel göstergesidir.

Uygulama Denge faktörü

balance_factor(node) yaz. height(sol) - height(sağ). None ise 0. root = Node(1); root.left = Node(2); print(balance_factor(root)) ile 1 yazdır.

Örnek çözümü göster

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
def balance_factor(node):
    # Denge faktörü
    if node is None:
        return 0
    return height(node.left) - height(node.right)
root = Node(1)
root.left = Node(2)
print(balance_factor(root))

Kendini test et

AVL'de denge faktörü ne olmalı?
- -2 veya +2
- -1, 0 veya +1
- 0 sadece
- herhangi
Cevabı göster

-1, 0 veya +1 — -1, 0 veya +1

Denge faktörü

bf = height(node.left) - height(node.____)

Cevabı göster

bf = height(node.left) - height(node.right)

Dengeli ağaç: kavramları eşleştir

bf = 0

Dengeli
bf = +2

Sol ağırlıklı
bf = -2

Sağ ağırlıklı
|bf| > 1

Döndür

Sıradaki ders: Döndürme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler