Dengeli ağaç
- Algoritmalar kursu
- Orta seviye
- Ders 33/80
- 4 dk
Yükseklik farkının en fazla 1 olduğu AVL ağacını öğrenirsin.
Dengeli ağaç
AVL ağacı, her düğümün sol ve sağ alt ağaçlarının yükseklikleri arasındaki farkın (denge faktörü) en fazla 1 olduğu bir BST'dir. Bu, otomatik denge sağlar.
Denge faktörü height(left) - height(right). -1, 0 veya +1 olmalıdır. Aksi halde döndürme (rotation) ile düzeltilir.
AVL sayesinde arama, ekleme, silme her zaman O(log n) olur; dengesiz BST'nin O(n) kötü durumundan kaçınılır.
Denge faktörü hesabı
Her düğüm için denge faktörü bf = height(left) - height(right) ile hesaplanır. Ekleme ve silme sonrası bu değer değişebilir.
bf > 1 ise sol ağırlıklı, bf < -1 ise sağ ağırlıklı. Bu durumlar döndürme gerektirir.
Denge faktörü, ağacın çarpık olup olmadığını tek bakışta gösterir; AVL'nin temel göstergesidir.
Uygulama Denge faktörü
balance_factor(node) yaz. height(sol) - height(sağ). None ise 0. root = Node(1); root.left = Node(2); print(balance_factor(root)) ile 1 yazdır.
Başlangıç kodu
def balance_factor(node):
# Denge faktörüÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance_factor(node):
# Denge faktörü
if node is None:
return 0
return height(node.left) - height(node.right)
root = Node(1)
root.left = Node(2)
print(balance_factor(root))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 AVL'de denge faktörü ne olmalı?
- -2 veya +2
- -1, 0 veya +1 Doğru cevap
- 0 sadece
- herhangi
Açıklama: -1, 0 veya +1
2 Denge faktörü
bf = height(node.left) - height(node.____)bf = height(node.left) - height(node.right)Açıklama: right doğru.
3 Dengeli ağaç: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
bf = 0 |
Dengeli |
bf = +2 |
Sol ağırlıklı |
bf = -2 |
Sağ ağırlıklı |
|bf| > 1 |
Döndür |