Özet - AVL tree
- Algoritmalar kursu
- Orta seviye
- Ders 36/80
- 4 dk
AVL mantığını pekiştiren mini görev yaparsın.
Özet - AVL tree
AVL: her düğümde |bf| ≤ 1. Denge bozulursa döndürme (sağ, sol, çift) ile düzeltilir. Ekleme/silme/arama her zaman O(log n).
Dört durum: sol-sol (sağ), sağ-sağ (sol), sol-sağ (çift), sağ-sol (çift). Döndürme O(1), BST özelliği korunur.
AVL, sık arama ve seyrek ekleme senaryolarında idealdir; sık eklemede kırmızı-siyah ağaç tercih edilir.
Uygulama Özet: AVL yüksekliği
height(node) yaz. AVL'de height ≤ 1.44 log n. root = Node(1); root.left = Node(2); print(height(root)) ile 1 yazdır.
Başlangıç kodu
def height(node):
# YükseklikÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def height(node):
# Yükseklik
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
print(height(root))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - AVL tree: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Denge |
|bf| ≤ 1 |
Sol-sol |
Sağ döndür |
Sağ-sağ |
Sol döndür |
Maliyet |
O(log n) |
2 Denge faktörü sınırı
Soru
|bf| ____ 1
Cevap
|bf| <= 1Açıklama: <= doğru.
3 AVL ne zaman tercih edilir?
- Sık arama, seyrek ekleme Doğru cevap
- Hiç ekleme yoksa
- Her zaman
- Sık ekleme, seyrek arama
Açıklama: Sık arama, seyrek ekleme