Döndürme

Tek ve çift döndürmelerle dengeyi sağlamayı öğrenirsin.

Döndürme

AVL'de denge bozulduğunda döndürme (rotation) yapılır. Sağ döndürme: sol ağır durumda, sol çocuğu yukarı getirir.

Sağ döndürmede: y = x.left, x.left = y.right, y.right = x. Artık y yeni kök, x sağ çocuğu olur.

Döndürme, BST özelliğini korur ve yüksekliği azaltır. O(1) işle yapılır.

Dört durum

AVL'de dört dengesizlik durumu vardır: sol-sol (sağ döndür), sol-sağ (önce sol, sonra sağ döndür), sağ-sağ (sol döndür), sağ-sol (önce sağ, sonra sol döndür).

Sol-sağ ve sağ-sol çift döndürme gerektirir: önce alt döndürme, sonra üst döndürme. Bu, karmaşık bozuklukları düzeltir.

Her durumda sonuç: denge faktörü -1,0,+1 aralığına döner; BST özelliği korunur.

Uygulama Sağ döndürme

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

Örnek çözümü göster

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

Kendini test et

Sağ döndürme

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

Cevabı göster

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

Döndürme: kavramları eşleştir

Sol-sol

Sağ döndür
Sağ-sağ

Sol döndür
Sol-sağ

Önce sol
Sağ-sol

Önce sağ
Sağ döndürme hangi durumu düzeltir?
- Sağ-sağ
- Sol-sağ
- Sol-sol
- Sağ-sol
Cevabı göster

Sol-sol — Sol-sol

Sıradaki ders: Ekleme sonrası denge

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler