AVL Ağacı

Ağaçlar O(log n) O(n)

Kendini dengeleyen bir İAA: her eklemeden sonra denge faktörlerini kontrol eder ve yükseklik O(log n) kalsın diye döndürür.

Ekle

1/35

10 yeni bir yaprak olarak ekleniyor.

DeğişmezHer düğümün alt ağaç yükseklikleri en fazla 1 fark eder; bu yüksekliği O(log n) ve arama yolunu kısa tutar.

mevcutkarşılaştıreklesildöndür

avl.c

int height(Node *n) { return n ? n->height : 0; }
int bf(Node *n) {
    return n ? height(n->left) - height(n->right) : 0;
}
 
Node *rotateRight(Node *y) {
    Node *x = y->left;
    y->left = x->right;
    x->right = y;
    fixHeight(y); fixHeight(x);
    return x;
}
 
Node *rotateLeft(Node *x) {
    Node *y = x->right;
    x->right = y->left;
    y->left = x;
    fixHeight(x); fixHeight(y);
    return y;
}
 
Node *insert(Node *n, int key) {
    if (!n) return newNode(key);
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fixHeight(n);
    int b = bf(n);
    if (b > 1 && key < n->left->key)
        return rotateRight(n);
    if (b < -1 && key > n->right->key)
        return rotateLeft(n);
    if (b > 1 && key > n->left->key) {
        n->left = rotateLeft(n->left);
        return rotateRight(n);
    }
    if (b < -1 && key < n->right->key) {
        n->right = rotateRight(n->right);
        return rotateLeft(n);
    }
    return n;
}

AVL Ağacı nasıl çalışır?

Her eklemeden sonra düğümlerin denge faktörünü ölçen ve ±2 eğilmeyi bir-iki döndürmeyle onaran bir İAA. Yükseklik 1.44·log n içinde kalır; yürüyüşler logaritmik kalır.

Ne zaman kullanılır?

Katı O(log n) aramanın ucuz yazmadan önemli olduğu, okuma ağırlıklı sıralı eşlemeler.