AVL Ağacı

Her düğümde sol ve sağ yükseklik farkını en fazla 1 tutan, rotasyonlarla kendini dengeleyen ikili arama ağacı.

Önce bunlara göz at

İkili Arama Ağacı (BST)

#Nasıl çalışır?

AVL ağacı, kendini dengeleyen ilk ikili arama ağacıdır (Adelson-Velsky ve Landis, 1962). Sıradan bir BST'ye 10, 20, 30, 40 gibi sıralı değerler eklenirse ağaç bir zincire dönüşür ve arama O(n) olur. AVL buna izin vermez.

Her düğüm için denge faktörü = sol alt ağacın yüksekliği − sağ alt ağacın yüksekliği. AVL kuralı: bu değer her düğümde −1, 0 ya da +1 olmalıdır.

Ekleme sonrası kökten yeni düğüme giden yol üzerinde bir düğümün dengesi ±2 olursa, bir ya da iki rotasyonla düzeltilir. Rotasyon, BST sırasını bozmadan bir düğümü yukarı, diğerini aşağı taşır.

Dört durum vardır: LL (sol-sol) için sağa tek rotasyon, RR için sola tek rotasyon; LR ve RL için önce çocukta, sonra dengesiz düğümde olmak üzere çift rotasyon.

#Kendin dene

$ avl_tree --interactive

-1

Bir değer ekle ve dengeyi izle: her düğümün yanındaki sayı denge faktörüdür (sol yükseklik − sağ yükseklik). ±2 olursa rotasyonla düzeltilir.

DeğerHız

Eleman: 6/12GeziliyorYeniÇıkarılıyorBulundu / okunan

#Temel işlemler

insert(x): BST gibi ekler, sonra yukarı doğru denge faktörlerini kontrol eder; gerekirse rotasyon yapar.
search(x): Sıradan BST araması; ağaç dengeli olduğu için en fazla O(log n) adım sürer.
delete(x): BST gibi siler, sonra köke kadar dengesiz düğümleri rotasyonla düzeltir (birden fazla rotasyon gerekebilir).
rotateLeft / rotateRight: Bir düğümün sağ (ya da sol) çocuğunu onun yerine çıkarır; inorder sıra değişmez, sadece yükseklikler değişir.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from typing import Optional


class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["Node"] = None
        self.right: Optional["Node"] = None
        self.height = 1  # height of the subtree rooted here


def height(node: Optional[Node]) -> int:
    return node.height if node else 0


def update(node: Node) -> None:
    node.height = 1 + max(height(node.left), height(node.right))


def balance(node: Node) -> int:
    return height(node.left) - height(node.right)


def rotate_right(y: Node) -> Node:
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x  # new root of this subtree


def rotate_left(x: Node) -> Node:
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y


def insert(node: Optional[Node], value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    else:
        return node  # no duplicates
    update(node)
    b = balance(node)
    if b > 1 and value < node.left.value:  # LL
        return rotate_right(node)
    if b > 1:  # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1 and value > node.right.value:  # RR
        return rotate_left(node)
    if b < -1:  # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def inorder(node: Optional[Node], out: list) -> list:
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)
    return out


root = None
for v in [10, 20, 30, 40, 50, 25]:
    root = insert(root, v)

print(" ".join(map(str, inorder(root, []))))  # 10 20 25 30 40 50
print(root.value)                             # 30: rotations moved it up
print(root.height)                            # 3, not 6 like a plain BST

#Karmaşıklık

İşlem	Süre
search	O(log n)
insert	O(log n)
delete	O(log n)
Tek rotasyon	O(1)
Bellek	O(n)

AVL ağacının yüksekliği en fazla yaklaşık 1,44 · log2(n)'dir; bu yüzden tüm işlemler en kötü durumda bile O(log n) sürer. Red-black ağacından daha sıkı dengelidir: aramalar biraz daha hızlı, eklemeler biraz daha fazla rotasyon ister. Gerçek uygulamalarda yükseklik her düğümde saklanır; animasyon her adımda yeniden hesaplar.

#Ne zaman kullanılır?

Okumanın yazmadan çok daha sık olduğu, en kötü durumda bile hızlı arama gereken yerlerde AVL iyi bir seçimdir: bellek içi indeksler, sözlükler, sıralı küme ve haritalar. Sık ekleme/silme varsa red-black ağacı genellikle daha az iş yapar.