AVL и Red-Black деревья

Зачем нужна балансировка?

Обычное BST может деградировать до связного списка (O(n) на операцию). Самобалансирующиеся деревья гарантируют O(log n) для всех операций.

Обычное BST (вставка 1,2,3,4,5):     AVL (те же данные):

1                                         2
 \                                       / \
  2                                     1   4
   \                                       / \
    3                                     3   5
     \
      4        h = 4, O(n)           h = 2, O(log n)
       \
        5

AVL-дерево

Изобретено Адельсоном-Вельским и Ландисом в 1962 году.

Инвариант AVL: для каждого узла разница высот левого и правого поддеревьев (balance factor) не превышает 1.

Balance factor = height(left) - height(right)

Допустимые: -1, 0, +1
Недопустимые: -2, +2 (нужна ротация)

      4 (bf=1)      Сбалансировано
     / \
    2   5 (bf=0)
   / \
  1   3

Ротации

Правая ротация (Right Rotation)

Применяется при left-left (LL) дисбалансе.

Дисбаланс (bf=2):      После правой ротации:
       z                      y
      / \                   /   \
     y   T4                x     z
    / \          ->       / \   / \
   x   T3               T1 T2 T3 T4
  / \
 T1  T2

<?php
declare(strict_types=1);

function rightRotate(AVLNode $z): AVLNode
{
    $y = $z->left;
    $t3 = $y->right;

    $y->right = $z;
    $z->left = $t3;

    // Update heights
    $z->height = 1 + max(height($z->left), height($z->right));
    $y->height = 1 + max(height($y->left), height($y->right));

    return $y; // New root
}

func rightRotate(z *AVLNode) *AVLNode {
	y := z.Left
	t3 := y.Right

	y.Right = z
	z.Left = t3

	// Update heights
	z.Height = 1 + max(height(z.Left), height(z.Right))
	y.Height = 1 + max(height(y.Left), height(y.Right))

	return y // new root
}

static AVLNode RightRotate(AVLNode z)
{
    AVLNode y = z.Left!;
    AVLNode? t3 = y.Right;

    y.Right = z;
    z.Left = t3;

    // Update heights
    z.Height = 1 + Math.Max(Height(z.Left), Height(z.Right));
    y.Height = 1 + Math.Max(Height(y.Left), Height(y.Right));

    return y; // new root
}

def right_rotate(z: AVLNode) -> AVLNode:
    y = z.left
    assert y is not None  # LL imbalance guarantees a left child
    t3 = y.right

    y.right = z
    z.left = t3

    # Update heights
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))

    return y  # new root

#### Левая ротация (Left Rotation)

Применяется при right-right (RR) дисбалансе.

Дисбаланс (bf=-2):     После левой ротации:
     z                       y
    / \                    /   \
   T1  y                  z     x
      / \       ->       / \   / \
     T2  x              T1 T2 T3 T4
        / \
       T3  T4

LR и RL ротации

LR дисбаланс:          Сначала левая ротация y:    Затем правая ротация z:
     z                       z                           x
    / \                     / \                         /   \
   y   T4                  x   T4                     y     z
  / \           ->        / \            ->          / \   / \
 T1  x                   y   T3                     T1 T2 T3 T4
    / \                  / \
   T2  T3               T1  T2

 RL дисбаланс — зеркальное отражение.

Вставка в AVL

<?php
declare(strict_types=1);

class AVLNode
{
    public function __construct(
        public int $val,
        public ?AVLNode $left = null,
        public ?AVLNode $right = null,
        public int $height = 1,
    ) {}
}

function height(?AVLNode $node): int
{
    return $node?->height ?? 0;
}

function balanceFactor(?AVLNode $node): int
{
    return $node !== null ? height($node->left) - height($node->right) : 0;
}

function insertAvl(?AVLNode $root, int $val): AVLNode
{
    // Standard BST insertion
    if ($root === null) {
        return new AVLNode($val);
    }

    if ($val < $root->val) {
        $root->left = insertAvl($root->left, $val);
    } elseif ($val > $root->val) {
        $root->right = insertAvl($root->right, $val);
    } else {
        return $root; // Duplicate
    }

    // Update height
    $root->height = 1 + max(height($root->left), height($root->right));

    // Check balance
    $bf = balanceFactor($root);

    // LL
    if ($bf > 1 && $val < $root->left->val) {
        return rightRotate($root);
    }

    // RR
    if ($bf < -1 && $val > $root->right->val) {
        return leftRotate($root);
    }

    // LR
    if ($bf > 1 && $val > $root->left->val) {
        $root->left = leftRotate($root->left);
        return rightRotate($root);
    }

    // RL
    if ($bf < -1 && $val < $root->right->val) {
        $root->right = rightRotate($root->right);
        return leftRotate($root);
    }

    return $root;
}

// AVLNode represents a node in an AVL tree.
type AVLNode struct {
	Val    int
	Left   *AVLNode
	Right  *AVLNode
	Height int
}

func height(node *AVLNode) int {
	if node == nil {
		return 0
	}
	return node.Height
}

func balanceFactor(node *AVLNode) int {
	if node == nil {
		return 0
	}
	return height(node.Left) - height(node.Right)
}

func insertAvl(root *AVLNode, val int) *AVLNode {
	// Standard BST insertion
	if root == nil {
		return &AVLNode{Val: val, Height: 1}
	}

	if val < root.Val {
		root.Left = insertAvl(root.Left, val)
	} else if val > root.Val {
		root.Right = insertAvl(root.Right, val)
	} else {
		return root // duplicate
	}

	// Update height
	root.Height = 1 + max(height(root.Left), height(root.Right))

	// Check balance
	bf := balanceFactor(root)

	// LL
	if bf > 1 && val < root.Left.Val {
		return rightRotate(root)
	}

	// RR
	if bf < -1 && val > root.Right.Val {
		return leftRotate(root)
	}

	// LR
	if bf > 1 && val > root.Left.Val {
		root.Left = leftRotate(root.Left)
		return rightRotate(root)
	}

	// RL
	if bf < -1 && val < root.Right.Val {
		root.Right = rightRotate(root.Right)
		return leftRotate(root)
	}

	return root
}

// AVLNode represents a node in an AVL tree.
sealed class AVLNode(int val)
{
    public int Val { get; set; } = val;
    public AVLNode? Left { get; set; }
    public AVLNode? Right { get; set; }
    public int Height { get; set; } = 1;
}

static int Height(AVLNode? node) => node?.Height ?? 0;

static int BalanceFactor(AVLNode? node) =>
    node is null ? 0 : Height(node.Left) - Height(node.Right);

static AVLNode InsertAvl(AVLNode? root, int val)
{
    // Standard BST insertion
    if (root is null)
    {
        return new AVLNode(val);
    }

    if (val < root.Val)
    {
        root.Left = InsertAvl(root.Left, val);
    }
    else if (val > root.Val)
    {
        root.Right = InsertAvl(root.Right, val);
    }
    else
    {
        return root; // duplicate
    }

    // Update height
    root.Height = 1 + Math.Max(Height(root.Left), Height(root.Right));

    // Check balance
    int bf = BalanceFactor(root);

    // LL
    if (bf > 1 && val < root.Left!.Val)
    {
        return RightRotate(root);
    }

    // RR
    if (bf < -1 && val > root.Right!.Val)
    {
        return LeftRotate(root);
    }

    // LR
    if (bf > 1 && val > root.Left!.Val)
    {
        root.Left = LeftRotate(root.Left);
        return RightRotate(root);
    }

    // RL
    if (bf < -1 && val < root.Right!.Val)
    {
        root.Right = RightRotate(root.Right);
        return LeftRotate(root);
    }

    return root;
}

from dataclasses import dataclass

@dataclass
class AVLNode:
    """A node in an AVL tree."""

    val: int
    left: "AVLNode | None" = None
    right: "AVLNode | None" = None
    height: int = 1

def height(node: AVLNode | None) -> int:
    return node.height if node is not None else 0

def balance_factor(node: AVLNode | None) -> int:
    return height(node.left) - height(node.right) if node is not None else 0

def insert_avl(root: AVLNode | None, val: int) -> AVLNode:
    # Standard BST insertion
    if root is None:
        return AVLNode(val)

    if val < root.val:
        root.left = insert_avl(root.left, val)
    elif val > root.val:
        root.right = insert_avl(root.right, val)
    else:
        return root  # duplicate

    # Update height
    root.height = 1 + max(height(root.left), height(root.right))

    # Check balance
    bf = balance_factor(root)

    # LL
    if bf > 1 and root.left is not None and val < root.left.val:
        return right_rotate(root)

    # RR
    if bf < -1 and root.right is not None and val > root.right.val:
        return left_rotate(root)

    # LR
    if bf > 1 and root.left is not None and val > root.left.val:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    # RL
    if bf < -1 and root.right is not None and val < root.right.val:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

## Red-Black дерево

Менее строго сбалансированное, но быстрее на вставке/удалении (меньше ротаций).

Правила Red-Black

Каждый узел красный или чёрный
Корень всегда чёрный
Все листья (NIL) чёрные
У красного узла оба потомка чёрные (нет двух красных подряд)
Любой путь от узла до листа содержит одинаковое количество чёрных узлов

         8(B)
        /    \
      4(R)   12(R)
      / \    /  \
    2(B) 6(B) 10(B) 14(B)

B = чёрный, R = красный

Гарантия высоты

Из правил следует: высота Red-Black дерева <= 2 * log2(n+1). Это не так строго, как AVL (1.44 * log2(n)), но всё равно O(log n).

Вставка в Red-Black (упрощённо)

Вставляем как в обычное BST
Красим новый узел в красный
Исправляем нарушения:
- Дядя красный — перекрашиваем
- Дядя чёрный, зигзаг — ротация + перекрашивание
- Дядя чёрный, линия — ротация + перекрашивание

Случай 1 (дядя красный): перекрашиваем

     G(B)              G(R)
    / \               / \
   P(R) U(R)  ->    P(B) U(B)
  /                /
 X(R)             X(R)

Случай 3 (дядя чёрный, линия): ротация

     G(B)              P(B)
    / \               / \
   P(R) U(B)  ->    X(R) G(R)
  /                        \
 X(R)                      U(B)

Сравнение AVL vs Red-Black

Свойство	AVL	Red-Black
Строгость баланса	Очень строгий (bf<=1)	Менее строгий
Макс. высота	1.44 * log(n)	2 * log(n)
Скорость поиска	Быстрее (ниже высота)	Чуть медленнее
Скорость вставки/удаления	Медленнее (больше ротаций)	Быстрее
Ротаций при вставке	До 2	До 2
Ротаций при удалении	До O(log n)	До 3
Применение	Частые поиски	Частые вставки/удаления

Применение в стандартных библиотеках

Язык	Структура	Реализация
Java	TreeMap, TreeSet	Red-Black
C++	std::map, std::set	Red-Black
.NET	SortedDictionary	Red-Black
Linux	CFS scheduler	Red-Black
Go	-	Нет в stdlib
Python	-	Нет в stdlib

Go и Python не имеют сбалансированных деревьев в stdlib, используют HashMap/dict.

Когда нужны сбалансированные деревья

Упорядоченные данные — итерация в отсортированном порядке
Range queries — все элементы в диапазоне [a, b]
Floor/Ceiling — ближайший меньший/больший элемент
Rank — позиция элемента в отсортированном порядке
Persistent data structures — версионирование

Когда хватит HashMap

Не нужен порядок
Только точечные запросы (get/put/delete)
Нет range queries

B-деревья (бонус)

Обобщение BST для дисковых хранилищ. Каждый узел содержит множество ключей и потомков.

B-дерево порядка 3:

        [10, 20]
       /    |    \
  [1,5]  [12,15] [25,30]

Используется в:

Базы данных (PostgreSQL, MySQL) — индексы
Файловые системы (NTFS, ext4)
Оптимизированы для минимизации дисковых операций

Запомни: AVL — строгий баланс, быстрый поиск. Red-Black — мягче баланс, быстрее модификации. На интервью редко просят реализацию, но важно знать: зачем нужна балансировка (O(log n) гарантия), какие ротации бывают (одинарные и двойные), где используются (TreeMap в Java, std::map в C++). B-деревья — для баз данных.

Итоги

AVL: |bf| <= 1, строгий баланс, высота 1.44*log(n)
Red-Black: 5 правил, мягче баланс, высота 2*log(n)
Ротации: одинарные (LL, RR) и двойные (LR, RL)
AVL для чтения, Red-Black для записи
Java TreeMap, C++ std::map = Red-Black
B-деревья = для баз данных и файловых систем