AVL-Baum
Zuletzt aktualisiert
Ein AVL-Baum ist ein selbstausgleichender binärer Suchbaum. Er funktioniert wie ein normaler BST, prüft aber nach jeder Einfügung den Balancefaktor jedes Vorfahren - den Höhenunterschied zwischen seinem linken und rechten Teilbaum - und wenn ein Knoten unausgeglichen wird (ein Unterschied größer als 1), führt er Rotationen durch, um das Gleichgewicht wiederherzustellen. Drücken Sie oben auf Wiedergabe, um zu sehen, wie Werte eingefügt werden und sich der Baum wieder in Form dreht.
Da er den Baum nie mehr als nur leicht schief werden lässt, garantiert ein AVL-Baum eine Höhe von O(log n), sodass Suche, Einfügen und Löschen immer O(log n) sind - selbst bei sortierter Eingabe, die einen einfachen BST ruinieren würde. Der Preis dafür sind die zusätzlichen Rotationen und die Höhenverwaltung bei jeder Einfügung.
Zeit- und Speicherkomplexität
| Operation | Komplexität | Hinweise |
|---|---|---|
| Suche | O(log n) | Die Höhe ist immer ~1.44 log n |
| Einfügen | O(log n) | Plus O(1) Rotationen |
| Löschen | O(log n) | Plus O(log n) Rotationen |
| Speicher | O(n) | Ein Höhenfeld pro Knoten |
Die vier Rotationsfälle
| Fall | Ungleichgewicht | Korrektur |
|---|---|---|
| Links-Links | Schwer auf der linken Seite des linken Kindes | Eine Rechtsrotation |
| Rechts-Rechts | Schwer auf der rechten Seite des rechten Kindes | Eine Linksrotation |
| Links-Rechts | Schwer auf der rechten Seite des linken Kindes | Links-, dann Rechtsrotation |
| Rechts-Links | Schwer auf der linken Seite des rechten Kindes | Rechts-, dann Linksrotation |
Durchgerechnetes Beispiel
Einfügen von [10, 20, 30, 40, 50, 25], einen Wert nach dem anderen:
| Schritt | Struktur | Aktion |
|---|---|---|
10 einfügen | 10 | Der erste Knoten wird zur Wurzel; ausgeglichen |
20 einfügen | 10(_, 20) | Geht rechts von 10; weiterhin ausgeglichen |
30 einfügen | 20(10, 30) | Rechts-Rechts bei 10, also hebt eine Linksrotation 20 zur Wurzel |
40 einfügen | 20(10, 30(_, 40)) | Geht rechts von 30; alle Balancefaktoren bleiben innerhalb von ±1 |
50 einfügen | 20(10, 40(30, 50)) | Rechts-Rechts bei 30, also hebt eine Linksrotation bei 30 den Knoten 40 |
25 einfügen | 30(20(10, 25), 40(_, 50)) | Rechts-Links bei 20: Teilbaum von 40 rechtsrotieren, dann 20 linksrotieren |
Wann man einen AVL-Baum verwenden sollte
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Suchvorgänge Einfügungen bei weitem überwiegen und Sie die kompakteste mögliche Höhe wollen | Einfügungen und Löschungen dominieren - die zusätzlichen Rotationen und das Rebalancieren kosten mehr als bei einem Rot-Schwarz-Baum |
Sie garantiert O(log n) im schlimmsten Fall benötigen, selbst bei feindlicher oder sortierter Eingabe | Eine einfache Hash-Tabelle würde genügen - Sie brauchen keine geordnete Traversierung oder Bereichsabfragen |
| Sie geordnete Operationen benötigen: In-Order-Traversierung, Vorgänger/Nachfolger, Bereichsabfragen | Der Datensatz winzig ist - ein einfacher BST oder ein sortiertes Array ist einfacher und schnell genug |
| Daten möglicherweise bereits sortiert ankommen, was einen unausgeglichenen BST in eine verkettete Liste verwandeln würde | Sie sich den zusätzlichen Speicher des Höhenfeldes pro Knoten in einem sehr engen Speicherbudget nicht leisten können |
AVL Tree-Code
Eine saubere, lauffähige AVL Tree-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
AVL Tree-Code in 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-Code in 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-Code in 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-Code in 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-Code in 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-Baum-FAQ
Was ist ein Balancefaktor in einem AVL-Baum?
Der Balancefaktor eines Knotens ist die Höhe seines linken Teilbaums minus die Höhe seines rechten Teilbaums. Ein AVL-Baum hält den Balancefaktor jedes Knotens bei -1, 0 oder +1; wenn eine Einfügung ihn aus diesem Bereich schiebt, stellt eine Rotation das Gleichgewicht wieder her.
Was ist der Unterschied zwischen einem AVL-Baum und einem Rot-Schwarz-Baum?
Beide sind selbstausgleichende BSTs mit
O(log n)-Operationen. AVL-Bäume sind strenger ausgeglichen, sodass Suchvorgänge etwas schneller sind, aber sie führen beim Einfügen/Löschen möglicherweise mehr Rotationen durch. Rot-Schwarz-Bäume sind lockerer ausgeglichen und bevorzugen weniger Rotationen - deshalb verwenden viele Standardbibliotheken sie für Maps und Sets.Warum einen AVL-Baum statt eines einfachen binären Suchbaums verwenden?
Ein einfacher BST kann zu
O(n)-Operationen degenerieren, wenn Werte in sortierter Reihenfolge eintreffen und eine schiefe Kette bilden. Ein AVL-Baum rotiert, um ausgeglichen zu bleiben, und garantiert eine Höhe und Operationen von O(log n) unabhängig von der Einfügereihenfolge.Ist ein AVL-Baum besser als ein Rot-Schwarz-Baum für einen Datenbankindex?
Es hängt von der Arbeitslast ab. AVL-Bäume sind starrer ausgeglichen und gewinnen daher, wenn Lesevorgänge dominieren und Sie die kürzestmöglichen Suchpfade wollen. Aber die meisten Datenbanken und Sprachbibliotheken wählen Rot-Schwarz-Bäume (oder B-Bäume), weil sie sich bei schreiblastigen Arbeitslasten mit weniger Rotationen rebalancieren, was wichtiger ist, wenn Einfügungen und Löschungen häufig sind.
Wie viele Rotationen benötigt eine einzelne AVL-Einfügung?
Höchstens eine Rotation - entweder eine einfache oder eine doppelte (zweistufige) Rotation - wird jemals benötigt, um den Baum nach dem Einfügen eines Wertes neu auszugleichen. Das liegt daran, dass eine Einfügung die Höhe eines Teilbaums um höchstens eins erhöht, sodass eine einzige Korrektur am untersten unausgeglichenen Vorfahren ausreicht. Das Löschen ist anders: Es kann bis zu
O(log n) Rotationen erfordern, wenn sich das Rebalancieren zur Wurzel hin ausbreitet.Muss ich die Knotenhöhen nach jeder Rotation aktualisieren?
Ja - ein häufiger Fehler besteht darin, die Zeiger korrekt zu rotieren, aber zu vergessen, die Höhe der beiden beteiligten Knoten neu zu berechnen. Nach jeder Rotation müssen Sie zuerst die Höhe des herabgestuften Knotens und dann die des beförderten Knotens aktualisieren, da die Höhe des beförderten Knotens von seinen neuen Kindern abhängt. Wird dies ausgelassen, bleiben veraltete Balancefaktoren zurück, die künftige Rebalancierungsentscheidungen zerstören.
Verwandte Ressourcen
Mehr Visualisierungen
