🎮 Поиск в сбалансированном дереве — AVL Tree

Проблема: при работе с большими наборами данных обычное бинарное дерево поиска (BST) может деградировать в линейную структуру, что снижает скорость поиска до O(n).

Решение: В книге Algorithms and Data Structures for OOP With C# автор предлагает использовать AVL-дерево — сбалансированное дерево, которое поддерживает балансировку после каждой операции вставки или удаления. Это гарантирует сложность поиска, вставки и удаления за O(log n).

Пример кода:

public class AVLNode
{
    public int Key;
    public AVLNode Left, Right;
    public int Height;

    public AVLNode(int key)
    {
        Key = key;
        Height = 1;
    }
}

public class AVLTree
{
    private AVLNode root;

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

    int BalanceFactor(AVLNode node) => Height(node.Left) - Height(node.Right);

    AVLNode RightRotate(AVLNode y)
    {
        var x = y.Left;
        var T2 = x.Right;

        x.Right = y;
        y.Left = T2;

        y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;
        x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;

        return x;
    }

    AVLNode LeftRotate(AVLNode x)
    {
        var y = x.Right;
        var T2 = y.Left;

        y.Left = x;
        x.Right = T2;

        x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;
        y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;

        return y;
    }

    public AVLNode Insert(AVLNode node, int key)
    {
        if (node == null)
            return new AVLNode(key);

        if (key < node.Key)
            node.Left = Insert(node.Left, key);
        else if (key > node.Key)
            node.Right = Insert(node.Right, key);
        else
            return node;

        node.Height = 1 + Math.Max(Height(node.Left), Height(node.Right));

        int balance = BalanceFactor(node);

        if (balance > 1 && key < node.Left.Key)
            return RightRotate(node);

        if (balance < -1 && key > node.Right.Key)
            return LeftRotate(node);

        if (balance > 1 && key > node.Left.Key)
        {
            node.Left = LeftRotate(node.Left);
            return RightRotate(node);
        }

        if (balance < -1 && key < node.Right.Key)
        {
            node.Right = RightRotate(node.Right);
            return LeftRotate(node);
        }

        return node;
    }
}

Преимущества:
— Обеспечение сбалансированного дерева с высотой O(log n)
— Быстрый поиск и обновление данных
— Подходит для систем, требующих высокопроизводительных операций поиска

➡️ Лучшее из мира IT-книг — у нас в @progbook