Ekleme sonrası denge

Eklemeden sonra dengeyi yeniden kurmayı öğrenirsin.

Ekleme sonrası denge

AVL'ye eleman eklendikten sonra, eklenen düğümden köke doğru çıkılırken her düğümün denge faktörü kontrol edilir. |bf| > 1 ise o düğümde döndürme yapılır.

Döndürme sonrası alt ağacın yüksekliği eski haline döner; bu yüzden daha yukarıda denge bozulmaz. Bu, AVL'nin verimliliğinin anahtarıdır.

Ekleme O(log n): ekleme yolu + denge kontrolü, her ikisi de log n.

Sol döndürme

Sol döndürme, sağ ağırlıklı durumu düzeltir. y = x.right, x.right = y.left, y.left = x, return y.

Artık y yeni kök, x sol çocuğu olur. BST özelliği korunur, yükseklik azalır.

Sağ-sol durumunda önce sağ döndürme, sonra sol döndürme yapılır (çift döndürme).

Uygulama Sol döndürme

rotate_left(x) yaz. y = x.right, x.right = y.left, y.left = x, return y. root = Node(1); root.right = Node(2); root.right.right = Node(3); new_root = rotate_left(root); print(new_root.val, new_root.left.val) ile 2 1 yazdır.

Örnek çözümü göster

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def rotate_left(x):
    # Sol döndür
    y = x.right
    x.right = y.left
    y.left = x
    return y
root = Node(1)
root.right = Node(2)
root.right.right = Node(3)
new_root = rotate_left(root)
print(new_root.val, new_root.left.val)

Kendini test et

Ekleme sonrası denge: kavramları eşleştir

Ekleme

O(log n)
Denge kontrol

Çıkış yolu
|bf| > 1

Döndür
Sonuç

Dengeli
Sol döndürme neyi düzeltir?
- Sol ağırlıklı
- Boş ağaç
- Dengeli
- Sağ ağırlıklı
Cevabı göster

Sağ ağırlıklı — Sağ ağırlıklı

Sol döndürme

y = x.right
x.right = y.____
y.left = x

Cevabı göster

y = x.right
x.right = y.left
y.left = x

Sıradaki ders: Özet - AVL tree

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler