AVL-дерево
Последнее обновление
AVL-дерево - это самобалансирующееся двоичное дерево поиска. Оно работает как обычное BST, но после каждой вставки проверяет коэффициент баланса каждого предка - разницу высот между его левым и правым поддеревьями - и если какой-либо узел становится несбалансированным (разница больше 1), выполняет повороты для восстановления баланса. Нажмите воспроизведение выше, чтобы увидеть, как вставляются значения и дерево поворачивается обратно в форму.
Поскольку оно никогда не позволяет дереву перекоситься больше чем слегка, AVL-дерево гарантирует высоту O(log n), поэтому поиск, вставка и удаление всегда O(log n) - даже для отсортированного ввода, который разрушил бы обычное BST. Ценой этого являются дополнительные повороты и учёт высоты при каждой вставке.
Временная и пространственная сложность
| Операция | Сложность | Примечания |
|---|---|---|
| Поиск | O(log n) | Высота всегда ~1.44 log n |
| Вставка | O(log n) | Плюс O(1) поворотов |
| Удаление | O(log n) | Плюс O(log n) поворотов |
| Память | O(n) | Одно поле высоты на узел |
Четыре случая поворота
| Случай | Дисбаланс | Исправление |
|---|---|---|
| Лево-Лево | Перевес слева у левого потомка | Один правый поворот |
| Право-Право | Перевес справа у правого потомка | Один левый поворот |
| Лево-Право | Перевес справа у левого потомка | Левый, затем правый поворот |
| Право-Лево | Перевес слева у правого потомка | Правый, затем левый поворот |
Разобранный пример
Вставка [10, 20, 30, 40, 50, 25] по одному значению:
| Шаг | Структура | Действие |
|---|---|---|
Вставить 10 | 10 | Первый узел становится корнем; сбалансировано |
Вставить 20 | 10(_, 20) | Идёт вправо от 10; всё ещё сбалансировано |
Вставить 30 | 20(10, 30) | Право-Право в 10, поэтому один левый поворот поднимает 20 в корень |
Вставить 40 | 20(10, 30(_, 40)) | Идёт вправо от 30; все коэффициенты баланса остаются в пределах ±1 |
Вставить 50 | 20(10, 40(30, 50)) | Право-Право в 30, поэтому левый поворот в 30 поднимает 40 |
Вставить 25 | 30(20(10, 25), 40(_, 50)) | Право-Лево в 20: повернуть вправо поддерево 40, затем повернуть влево 20 |
Когда использовать AVL-дерево
| Используйте, когда | Избегайте, когда |
|---|---|
| Поисков намного больше, чем вставок, и вам нужна максимально компактная высота | Вставки и удаления преобладают - дополнительные повороты и перебалансировка обходятся дороже, чем у красно-чёрного дерева |
Вам нужен гарантированный худший случай O(log n), даже для враждебного или отсортированного ввода | Достаточно обычной хеш-таблицы - вам не нужен упорядоченный обход или запросы по диапазону |
| Вам нужны упорядоченные операции: обход в порядке возрастания, предшественник/преемник, запросы по диапазону | Набор данных крошечный - обычное BST или отсортированный массив проще и достаточно быстры |
| Данные могут поступать уже отсортированными, что превратило бы несбалансированное BST в связный список | Вы не можете позволить себе дополнительную память поля высоты на узел в очень ограниченном объёме |
Код AVL Tree
Чистая, готовая к запуску реализация AVL Tree на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код AVL Tree на Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Код AVL Tree на JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Код AVL Tree на Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Код AVL Tree на C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Код AVL Tree на C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}Часто задаваемые вопросы об AVL-дереве
Что такое коэффициент баланса в AVL-дереве?
Коэффициент баланса узла - это высота его левого поддерева минус высота его правого поддерева. AVL-дерево удерживает коэффициент баланса каждого узла на уровне -1, 0 или +1; если вставка выводит его за пределы этого диапазона, поворот восстанавливает баланс.
В чём разница между AVL-деревом и красно-чёрным деревом?
Оба являются самобалансирующимися BST с операциями
O(log n). AVL-деревья сбалансированы строже, поэтому поиск немного быстрее, но при вставке/удалении они могут выполнять больше поворотов. Красно-чёрные деревья сбалансированы более свободно, отдавая предпочтение меньшему числу поворотов - вот почему многие стандартные библиотеки используют их для отображений и множеств.Зачем использовать AVL-дерево вместо обычного двоичного дерева поиска?
Обычное BST может деградировать до операций
O(n), если значения поступают в отсортированном порядке, образуя перекошенную цепочку. AVL-дерево поворачивается, чтобы оставаться сбалансированным, гарантируя высоту и операции O(log n) независимо от порядка вставки.Лучше ли AVL-дерево, чем красно-чёрное дерево, для индекса базы данных?
Это зависит от нагрузки. AVL-деревья сбалансированы жёстче, поэтому они выигрывают, когда преобладают чтения и вам нужны кратчайшие возможные пути поиска. Но большинство баз данных и библиотек языков выбирают красно-чёрные деревья (или B-деревья), потому что они перебалансируются с меньшим числом поворотов при нагрузках с частой записью, что важнее, когда вставки и удаления происходят часто.
Сколько поворотов требуется для одной вставки в AVL-дерево?
Для перебалансировки дерева после вставки одного значения требуется не более одного поворота - либо одинарного, либо двойного (двухшагового). Это потому, что вставка увеличивает высоту поддерева не более чем на единицу, поэтому достаточно одного исправления у самого нижнего несбалансированного предка. Удаление другое: оно может потребовать до
O(log n) поворотов, по мере того как перебалансировка распространяется к корню.Нужно ли обновлять высоты узлов после каждого поворота?
Да - распространённая ошибка - правильно повернуть указатели, но забыть пересчитать высоту двух задействованных узлов. После каждого поворота нужно сначала обновить высоту понижаемого узла, а затем повышаемого, потому что высота повышаемого узла зависит от его новых потомков. Пропуск этого оставляет устаревшие коэффициенты баланса, которые нарушают будущие решения о перебалансировке.
Связанные ресурсы
Больше визуализаций
