1. введение
В этом уроке мы представим дерево AVL и рассмотрим алгоритмы вставки, удаления и поиска значений.
2. Что Такое Дерево AVL?
Дерево AVL, названное в честь его изобретателей Адельсона-Вельского и Ландиса, представляет собой самобалансирующееся бинарное дерево поиска (BST).
Самобалансирующееся дерево-это двоичное дерево поиска, которое балансирует высоту после вставки и удаления в соответствии с некоторыми правилами балансировки.
Наихудшая временная сложность BST является функцией высоты дерева. В частности, самый длинный путь от корня дерева до узла. Для BST с N узлами предположим, что каждый узел имеет только ноль или один дочерний элемент. Поэтому его высота равна N, а время поиска в худшем случае равно O(N). Таким образом, наша главная цель в BST-сохранить максимальную высоту близко к log(N).
Коэффициент баланса узла N равен height(right(N)) – height(left(N)) . В дереве AVL коэффициент баланса узла может быть только одним из значений 1, 0 или -1.
Давайте определим объект Node для нашего дерева:
public class Node {
int key;
int height;
Node left;
Node right;
...
}Далее давайте определим дерево AVL :
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 called T1, с корневым узлом, X как левый ребенок У, и Z как правый ребенок X. Given the characteristics of BST, мы знаем, что X < Z < Y.
После правого поворота у нас есть дерево, названное T2 с X как корень и как правый ребенок X и Z как левый ребенок Y. T2 все еще BST, потому что он держит порядок X < Z < Y.
Давайте рассмотрим правильную операцию вращения для нашего дерева AVL :
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 < Z < X.
После левого поворота Y у нас есть дерево под названием T2 с X в качестве корня и Y в качестве левого потомка X и Z в качестве правого потомка Y. T2 все еще является BST, потому что он сохраняет порядок Y < Z < X.
Давайте взглянем на операцию поворота влево для нашего дерева AVL :
Node rotateLeft(Node y) {
Node x = y.right;
Node z = x.left;
x.left = y;
y.right = z;
updateHeight(y);
updateHeight(x);
return x;
}3.3. Методы восстановления баланса
Мы можем использовать операции поворота вправо и поворота влево в более сложных комбинациях, чтобы сохранить дерево 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.
Давайте взглянем на операцию перебалансировки для нашего дерева AVL :
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. Удалите узел
Чтобы удалить ключ из дерева, мы сначала должны найти его в ЛУЧШЕМ.
После того, как мы найдем узел (называемый Z), мы должны ввести нового кандидата, чтобы заменить его в дереве. Если Z-лист, то кандидат пуст. Если у Z есть только один ребенок, этот ребенок является кандидатом, но если у Z есть два ребенка, процесс немного сложнее.
Предположим, что правый дочерний элемент Z называется Y. Сначала мы находим крайний левый узел Y и называем его X. Затем мы устанавливаем новое значение Z равным значению X и продолжаем удалять X из Y.
Наконец, мы вызываем метод баланса в конце, чтобы сохранить ЛУЧШЕЕ дерево 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 .