«1. Введение

В этом руководстве мы познакомимся с деревом AVL и рассмотрим алгоритмы вставки, удаления и поиска значений.

2. Что такое дерево AVL?

Дерево AVL, названное в честь его изобретателей Адельсона-Вельского и Лэндиса, представляет собой самобалансирующееся двоичное дерево поиска (BST).

Самобалансирующееся дерево — это бинарное дерево поиска, которое уравновешивает высоту после вставки и удаления в соответствии с некоторыми правилами балансировки.

Временная сложность BST в наихудшем случае зависит от высоты дерева. В частности, самый длинный путь от корня дерева к узлу. Предположим, что для BST с N узлами у каждого узла есть только ноль или один дочерний элемент. Следовательно, его высота равна N, а время поиска в худшем случае равно O(N). Таким образом, наша главная цель в BST — сохранить максимальную высоту близкой к log(N).

Фактор баланса узла N равен высоте (справа (N)) – высоте (слева (N)). В дереве AVL коэффициент баланса узла может принимать только одно из значений 1, 0 или -1.

Давайте определим объект Node для нашего дерева: 

public class Node {
    int key;
    int height;
    Node left;
    Node right;
    ...
}

Далее, давайте определим AVLTree: 

public class AVLTree {

    private Node root;

    void updateHeight(Node n) {
        n.height = 1 + Math.max(height(n.left), height(n.right));
    }

    int height(Node n) {
        return n == null ? -1 : n.height;
    }

    int getBalance(Node n) {
        return (n == null) ? 0 : height(n.right) - height(n.left);
    }

    ...
}

3. Как сбалансировать дерево AVL?

Дерево AVL проверяет коэффициент баланса своих узлов после вставки или удаления узла. Если коэффициент баланса узла больше единицы или меньше -1, дерево перебалансируется.

Есть две операции по перебалансировке дерева:

    правое вращение и левое вращение.

3.1. Правое вращение

Давайте начнем с правильного вращения.

Предположим, у нас есть BST с именем T1, с Y в качестве корневого узла, X в качестве левого потомка Y и Z в качестве правого потомка X. Учитывая характеристики BST, мы знаем, что X \u003c Z \u003c Y .

После правого поворота Y у нас есть дерево с именем T2 с X в качестве корня и Y в качестве правого потомка X и Z в качестве левого потомка Y. T2 по-прежнему является BST, потому что он сохраняет порядок X \u003c Z \u003c Y.

Давайте посмотрим на правильную операцию поворота для нашего AVLTree: 

Node rotateRight(Node y) {
    Node x = y.left;
    Node z = x.right;
    x.right = y;
    y.left = z;
    updateHeight(y);
    updateHeight(x);
    return x;
}

3.2. Операция левого вращения

У нас также есть операция левого вращения.

Предположим, что BST называется T1, с Y в качестве корневого узла, X в качестве правого потомка Y и Z в качестве левого потомка X. Учитывая это, мы знаем, что Y \u003c Z \u003c X.

После левое вращение Y, у нас есть дерево с именем T2 с X в качестве корня и Y в качестве левого дочернего элемента X и Z в качестве правого дочернего элемента Y. T2 по-прежнему является BST, потому что он сохраняет порядок Y \u003c Z \u003c X. ~ ~~ Давайте посмотрим на операцию поворота влево для нашего AVLTree:

3.3. Методы перебалансировки 

Node rotateLeft(Node y) {
    Node x = y.right;
    Node z = x.left;
    x.left = y;
    y.right = z;
    updateHeight(y);
    updateHeight(x);
    return x;
}

Мы можем использовать операции вращения вправо и влево в более сложных комбинациях, чтобы сохранить баланс дерева AVL после любых изменений в его узлах. В несбалансированной структуре хотя бы один узел имеет коэффициент баланса, равный 2 или -2. Давайте посмотрим, как мы можем сбалансировать дерево в этих ситуациях.

Когда коэффициент баланса узла Z равен 2, поддерево с Z в качестве корня находится в одном из этих двух состояний, считая Y правым дочерним элементом Z.

В первом случае высота справа дочерний элемент Y (X) больше, чем высота левого дочернего элемента (T2). Мы можем легко сбалансировать дерево, повернув Z влево.

Во втором случае высота правого потомка Y (T4) меньше высоты левого потомка (X). В этой ситуации требуется комбинация операций вращения.

В этом случае мы сначала поворачиваем Y вправо, поэтому дерево принимает ту же форму, что и в предыдущем случае. Затем мы можем сбалансировать дерево, повернув Z влево.

Кроме того, когда фактор баланса узла Z равен -2, его поддерево находится в одном из этих двух состояний, поэтому мы рассматриваем Z как корень, а Y как его левый ребенок.

Высота левого дочернего элемента Y больше высоты его правого дочернего элемента, поэтому мы уравновешиваем дерево правым вращением Z.

Или во втором случае правый дочерний элемент Y имеет большую высоту чем его левый ребенок.

Итак, прежде всего, мы преобразуем его в прежнюю форму с левым вращением Y, затем балансируем дерево с правым вращением Z.

Давайте посмотрим на операцию ребалансировки для нашего AVLTree:

«

Node rebalance(Node z) {
    updateHeight(z);
    int balance = getBalance(z);
    if (balance > 1) {
        if (height(z.right.right) > height(z.right.left)) {
            z = rotateLeft(z);
        } else {
            z.right = rotateRight(z.right);
            z = rotateLeft(z);
        }
    } else if (balance < -1) {
        if (height(z.left.left) > height(z.left.right))
            z = rotateRight(z);
        else {
            z.left = rotateLeft(z.left);
            z = rotateRight(z);
        }
    }
    return z;
}

«Мы будем использовать перебалансировку после вставки или удаления узла для всех узлов на пути от измененного узла к корню.

4. Вставка узла

Когда мы собираемся вставить ключ в дерево, мы должны найти его правильное положение, чтобы пройти правила BST. Итак, мы начинаем с корня и сравниваем его значение с новым ключом. Если ключ больше, продолжаем вправо, иначе переходим к левому дочернему элементу.

Как только мы найдем правильный родительский узел, мы добавим новый ключ в качестве узла слева или справа, в зависимости от значения.

После вставки узла у нас есть BST, но это может быть не дерево AVL. Поэтому мы проверяем факторы баланса и перебалансируем BST для всех узлов на пути от нового узла к корню.

Давайте посмотрим на операцию вставки: 

Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key);
    } else if (node.key > key) {
        node.left = insert(node.left, key);
    } else if (node.key < key) {
        node.right = insert(node.right, key);
    } else {
        throw new RuntimeException("duplicate Key!");
    }
    return rebalance(node);
}

Важно помнить, что ключ уникален в дереве — никакие два узла не имеют одного и того же ключа.

Временная сложность алгоритма вставки зависит от высоты. Поскольку наше дерево сбалансировано, мы можем предположить, что временная сложность в худшем случае равна O(log(N)).

5. Удаление узла

Чтобы удалить ключ из дерева, мы сначала должны найти его в BST.

После того, как мы нашли узел (называемый Z), мы должны ввести нового кандидата, который будет его заменой в дереве. Если Z — лист, кандидат пуст. Если у Z есть только один ребенок, этот ребенок является кандидатом, но если у Z есть два ребенка, процесс немного сложнее.

Предположим, что правый потомок Z называется Y. Сначала мы находим самый левый узел Y и называем его X. Затем мы устанавливаем новое значение Z равным значению X и продолжаем удалять X из Y.

Наконец, мы вызываем метод перебалансировки в конце, чтобы сохранить BST в виде дерева AVL.

Вот наш метод удаления: 

Node delete(Node node, int key) {
    if (node == null) {
        return node;
    } else if (node.key > key) {
        node.left = delete(node.left, key);
    } else if (node.key < key) {
        node.right = delete(node.right, key);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left == null) ? node.right : node.left;
        } else {
            Node mostLeftChild = mostLeftChild(node.right);
            node.key = mostLeftChild.key;
            node.right = delete(node.right, node.key);
        }
    }
    if (node != null) {
        node = rebalance(node);
    }
    return node;
}

Временная сложность алгоритма удаления является функцией высоты дерева. Подобно методу вставки, мы можем предположить, что временная сложность в худшем случае равна O(log(N)).

6. Поиск узла

Поиск узла в дереве AVL такой же, как и в любом BST.

Начните с корня дерева и сравните ключ со значением узла. Если ключ равен значению, вернуть узел. Если ключ больше, ищите от правого дочернего элемента, в противном случае продолжайте поиск от левого дочернего элемента.

Временная сложность поиска зависит от высоты. Можно предположить, что временная сложность в худшем случае равна O(log(N)).

Давайте посмотрим пример кода: 

Node find(int key) {
    Node current = root;
    while (current != null) {
        if (current.key == key) {
            break;
        }
        current = current.key < key ? current.right : current.left;
    }
    return current;
}

7. Заключение

В этом руководстве мы реализовали дерево AVL с операциями вставки, удаления и поиска.

Как всегда, вы можете найти код на Github.