Döndürme
- Algoritmalar kursu
- Orta seviye
- Ders 34/80
- 4 dk
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.
Başlangıç kodu
def rotate_right(x):
# Sağ döndürÖrnek çözüm
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)Beklenen çıktı
2 3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Sağ döndürme
y = x.left
x.left = y.____
y.right = xy = x.left
x.left = y.right
y.right = xAçıklama: right doğru.
2 Döndürme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Sol-sol |
Sağ döndür |
Sağ-sağ |
Sol döndür |
Sol-sağ |
Önce sol |
Sağ-sol |
Önce sağ |
3 Sağ döndürme hangi durumu düzeltir?
- Sağ-sağ
- Sol-sağ
- Sol-sol Doğru cevap
- Sağ-sol
Açıklama: Sol-sol