Ekleme sonrası denge
- Algoritmalar kursu
- Orta seviye
- Ders 35/80
- 4 dk
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.
Başlangıç kodu
def rotate_left(x):
# Sol döndürÖrnek çözüm
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)Beklenen çıktı
2 1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Ekleme sonrası denge: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Ekleme |
O(log n) |
Denge kontrol |
Çıkış yolu |
|bf| > 1 |
Döndür |
Sonuç |
Dengeli |
2 Sol döndürme neyi düzeltir?
- Sol ağırlıklı
- Boş ağaç
- Dengeli
- Sağ ağırlıklı Doğru cevap
Açıklama: Sağ ağırlıklı
3 Sol döndürme
y = x.right
x.right = y.____
y.left = xy = x.right
x.right = y.left
y.left = xAçıklama: left doğru.