AVL ağacları

İkili axtarış ağacı yalnız balanslı qaldıqca sürətlidir. Açarlar sıralı gələndə hər yeni açar eyni tərəfə düşür və ağac axtarışı O(n) olan bağlı siyahıya çevrilir. AVL ağacı (Adelson-Velsky və Landis, 1962) hər əlavədən sonra özünü fırlanmalarla düzəldən BST-dir, ona görə hündürlüyü həmişə O(log n) olur.

Problem: degenerə olmuş BST

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.h = 1

def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    else:
        root.right = bst_insert(root.right, key)
    return root

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = None
for key in range(1, 8):
    root = bst_insert(root, key)
print("height of the BST for 1..7:", height(root))

height of the BST for 1..7: 7

Yeddi açar mümkün 3 əvəzinə 7 hündürlük verir. Bir milyon sıralı açar üçün adi BST axtarışa bir milyon addım sərf edir.

Balans faktoru

Hər düyün öz alt-ağacının hündürlüyünü saxlayır. Balans faktoru h(left) - h(right)-dir. AVL invariantı: hər düyündə o -1, 0 və ya 1 olmalıdır. n düyünlü belə ağacın hündürlüyü təxminən 1.44 · log2(n)-dən çox deyil.

Fırlanmalar

Fırlanma bir neçə göstəricini O(1)-də dəyişir və inorder açar sırasını saxlayır, ona görə ağac düzgün BST olaraq qalır. rotate_right(y) sol uşaq x-i yuxarı qaldırır; rotate_left onun güzgü əksidir.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.h = 1          # height of the subtree rooted here