AVL-деревья

Двоичное дерево поиска быстро, пока остаётся сбалансированным. Если ключи приходят по порядку, каждый новый уходит в одну сторону, и дерево превращается в связный список с поиском O(n). AVL-дерево (Адельсон-Вельский и Ландис, 1962) — это BST, которое после каждой вставки чинит себя поворотами, поэтому его высота всегда O(log n).

Проблема: вырожденное 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

Семь ключей дают высоту 7 вместо возможных 3. Для миллиона отсортированных ключей обычное BST тратит на поиск миллион шагов.

Баланс-фактор

Каждый узел хранит высоту своего поддерева. Баланс-фактор — это h(left) - h(right). Инвариант AVL: в каждом узле он равен -1, 0 или 1. Дерево с n узлами тогда имеет высоту не больше примерно 1.44 · log2(n).

Повороты

Поворот переставляет несколько ссылок за O(1) и сохраняет порядок ключей при обходе inorder, поэтому дерево остаётся корректным BST. rotate_right(y) поднимает левого ребёнка x; rotate_left — его зеркало.

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