Drzewo AVL
Ostatnia aktualizacja
Drzewo AVL to samorównoważące się binarne drzewo poszukiwań. Działa jak zwykłe drzewo BST, ale po każdym wstawieniu sprawdza współczynnik zrównoważenia każdego przodka, czyli różnicę wysokości między jego lewym i prawym poddrzewem. Jeśli któryś węzeł traci równowagę (różnica większa niż 1), drzewo wykonuje rotacje, aby ją przywrócić. Kliknij odtwarzanie powyżej i zobacz, jak wstawiane są wartości, a drzewo samo wraca do właściwego kształtu.
Ponieważ drzewo AVL nigdy nie pozwala na więcej niż niewielkie przechylenie, gwarantuje wysokość O(log n), więc wyszukiwanie, wstawianie i usuwanie zawsze działają w O(log n), nawet dla posortowanych danych, które zrujnowałyby zwykłe drzewo BST. Kosztem są dodatkowe rotacje i aktualizacja wysokości przy każdym wstawieniu.
Złożoność czasowa i pamięciowa
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Wyszukiwanie | O(log n) | Wysokość zawsze wynosi ok. 1,44 log n |
| Wstawianie | O(log n) | Plus O(1) rotacji |
| Usuwanie | O(log n) | Plus O(log n) rotacji |
| Pamięć | O(n) | Jedno pole wysokości na węzeł |
Cztery przypadki rotacji
| Przypadek | Nierównowaga | Naprawa |
|---|---|---|
| Lewo-Lewo | Przeciążone lewe poddrzewo lewego dziecka | Jedna rotacja w prawo |
| Prawo-Prawo | Przeciążone prawe poddrzewo prawego dziecka | Jedna rotacja w lewo |
| Lewo-Prawo | Przeciążone prawe poddrzewo lewego dziecka | Rotacja w lewo, potem w prawo |
| Prawo-Lewo | Przeciążone lewe poddrzewo prawego dziecka | Rotacja w prawo, potem w lewo |
Przykład krok po kroku
Wstawianie [10, 20, 30, 40, 50, 25] po jednej wartości:
| Krok | Struktura | Działanie |
|---|---|---|
Wstaw 10 | 10 | Pierwszy węzeł zostaje korzeniem; drzewo jest zrównoważone |
Wstaw 20 | 10(_, 20) | Trafia na prawo od 10; nadal równowaga |
Wstaw 30 | 20(10, 30) | Prawo-Prawo w 10, więc jedna rotacja w lewo wynosi 20 na korzeń |
Wstaw 40 | 20(10, 30(_, 40)) | Trafia na prawo od 30; każdy współczynnik zrównoważenia mieści się w ±1 |
Wstaw 50 | 20(10, 40(30, 50)) | Prawo-Prawo w 30, więc rotacja w lewo w 30 wynosi 40 wyżej |
Wstaw 25 | 30(20(10, 25), 40(_, 50)) | Prawo-Lewo w 20: rotacja w prawo poddrzewa 40, potem rotacja w lewo w 20 |
Kiedy używać drzewa AVL
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Wyszukiwań jest znacznie więcej niż wstawień i zależy ci na najmniejszej możliwej wysokości | Dominują wstawienia i usunięcia: dodatkowe rotacje i równoważenie kosztują więcej niż w drzewie czerwono-czarnym |
Potrzebujesz gwarantowanego O(log n) w najgorszym przypadku, nawet dla złośliwych lub posortowanych danych | Wystarczy zwykła tablica haszująca: nie potrzebujesz przechodzenia w porządku ani zapytań o zakres |
| Potrzebujesz operacji na uporządkowanych danych: przejścia in-order, poprzednika/następnika, zapytań o zakres | Zbiór danych jest malutki: zwykłe drzewo BST lub posortowana tablica są prostsze i wystarczająco szybkie |
| Dane mogą przychodzić już posortowane, co zamieniłoby niezrównoważone drzewo BST w listę jednokierunkową | Nie możesz sobie pozwolić na dodatkową pamięć na pole wysokości w każdym węźle przy bardzo ciasnych zasobach |
AVL Tree: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu AVL Tree w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
AVL Tree: kod (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: kod (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: kod (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: kod (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: kod (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}Drzewo AVL: najczęstsze pytania
Czym jest współczynnik zrównoważenia w drzewie AVL?
Współczynnik zrównoważenia węzła to wysokość jego lewego poddrzewa minus wysokość prawego poddrzewa. Drzewo AVL utrzymuje współczynnik każdego węzła na poziomie -1, 0 lub +1; jeśli wstawienie wypchnie go poza ten zakres, rotacja przywraca równowagę.
Czym różni się drzewo AVL od drzewa czerwono-czarnego?
Oba są samorównoważącymi się drzewami BST z operacjami w
O(log n). Drzewa AVL są zrównoważone bardziej rygorystycznie, więc wyszukiwanie jest nieco szybsze, ale przy wstawianiu i usuwaniu mogą wykonywać więcej rotacji. Drzewa czerwono-czarne są zrównoważone luźniej i wymagają mniej rotacji, dlatego wiele bibliotek standardowych używa ich do map i zbiorów.Po co używać drzewa AVL zamiast zwykłego binarnego drzewa poszukiwań?
Zwykłe drzewo BST może zdegradować się do operacji w
O(n), jeśli wartości przychodzą w posortowanej kolejności i tworzą przekrzywiony łańcuch. Drzewo AVL wykonuje rotacje, aby pozostać zrównoważone, co gwarantuje wysokość i operacje w O(log n) niezależnie od kolejności wstawiania.Czy drzewo AVL jest lepsze od drzewa czerwono-czarnego do indeksu w bazie danych?
To zależy od obciążenia. Drzewa AVL są zrównoważone sztywniej, więc wygrywają, gdy dominują odczyty i zależy ci na jak najkrótszych ścieżkach wyszukiwania. Większość baz danych i bibliotek językowych wybiera jednak drzewa czerwono-czarne (lub B-drzewa), bo przy intensywnych zapisach równoważą się mniejszą liczbą rotacji, co ma większe znaczenie przy częstych wstawieniach i usunięciach.
Ile rotacji wymaga jedno wstawienie do drzewa AVL?
Najwyżej jednej rotacji, pojedynczej albo podwójnej (dwuetapowej), aby przywrócić równowagę po wstawieniu jednej wartości. Wynika to z tego, że wstawienie zwiększa wysokość poddrzewa co najwyżej o jeden, więc wystarczy jedna naprawa w najniższym niezrównoważonym przodku. Usuwanie działa inaczej: może wymagać nawet
O(log n) rotacji, bo równoważenie propaguje się w stronę korzenia.Czy po każdej rotacji trzeba aktualizować wysokości węzłów?
Tak. Częsty błąd to poprawne przepięcie wskaźników bez ponownego obliczenia wysokości dwóch węzłów biorących udział w rotacji. Po każdej rotacji najpierw zaktualizuj wysokość węzła, który zszedł niżej, a potem węzła, który awansował, bo wysokość awansowanego węzła zależy od jego nowych dzieci. Pominięcie tego kroku zostawia nieaktualne współczynniki zrównoważenia, które psują kolejne decyzje o równoważeniu.
Powiązane materiały
Więcej wizualizacji
