Binärer Suchbaum (BST)
Zuletzt aktualisiert
Ein binärer Suchbaum hält seine Werte sortiert: Für jeden Knoten sind alle Werte im linken Teilbaum kleiner und alle im rechten Teilbaum größer. Um einen Wert einzufügen oder zu finden, startest du an der Wurzel und gehst je nach Vergleich wiederholt nach links oder rechts, sodass jeder Schritt den Suchraum halbiert. Drücke oben auf Wiedergabe, um zu sehen, wie Werte per Vergleich platziert werden und eine Suche im Baum hinabläuft.
In einem ausgeglichenen Baum laufen diese Operationen in O(log n)-Zeit. Der Haken: Bereits sortierte Daten einzufügen lässt den Baum zu einer verketteten Liste mit O(n)-Operationen entarten - genau deshalb gibt es selbstbalancierende Varianten wie AVL- und Rot-Schwarz-Bäume.
Zeit- und Speicherkomplexität
| Operation | Ausgeglichen | Schlimmster Fall (entartet) |
|---|---|---|
| Suche | O(log n) | O(n) |
| Einfügen | O(log n) | O(n) |
| Löschen | O(log n) | O(n) |
| Speicher | O(n) | O(n) |
Schritt für Schritt (Einfügen)
| Schritt | Was passiert |
|---|---|
| 1 | Ist der Baum leer, wird der neue Wert zur Wurzel. |
| 2 | Andernfalls beginne an der Wurzel. |
| 3 | Ist der Wert kleiner, gehe zum linken Kind; ist er größer, gehe nach rechts. |
| 4 | Wiederhole, bis du eine leere Stelle erreichst. |
| 5 | Hänge den neuen Wert dort als Blatt an. |
Durchgerechnetes Beispiel
Einfügen von [5, 3, 8, 1, 4] in einen leeren Baum, einen Wert nach dem anderen:
| Einfügen | Genommener Pfad | Aktion |
|---|---|---|
5 | - | Der Baum ist leer, also wird 5 zur Wurzel. |
3 | 5 | 3 < 5, gehe nach links; die Stelle ist leer, hänge 3 als linkes Kind von 5 an. |
8 | 5 | 8 > 5, gehe nach rechts; die Stelle ist leer, hänge 8 als rechtes Kind von 5 an. |
1 | 5 -> 3 | 1 < 5 gehe nach links, dann 1 < 3 gehe nach links; hänge 1 als linkes Kind von 3 an. |
4 | 5 -> 3 | 4 < 5 gehe nach links, dann 4 > 3 gehe nach rechts; hänge 4 als rechtes Kind von 3 an. |
Wann ein binärer Suchbaum sinnvoll ist
| Verwende ihn, wenn | Vermeide ihn, wenn |
|---|---|
| Du sortierte Reihenfolge plus schnelle Suchen brauchst und Einfügungen in zufälliger Reihenfolge eintreffen. | Deine Daten bereits sortiert eintreffen: Ein unausgeglichener BST verschlechtert sich auf O(n) pro Operation. |
| Du willst, dass eine In-order-Traversierung die Werte gratis in sortierter Reihenfolge liefert. | Du nur Mitgliedschaftstests ohne Reihenfolge brauchst: Eine Hashtabelle bietet im Mittel O(1)-Suchen. |
| Du Bereichsabfragen oder den Nachfolger/Vorgänger eines Schlüssels brauchst. | Du garantierte O(log n)-Schranken brauchst: Greife stattdessen zu einem selbstbalancierenden AVL- oder Rot-Schwarz-Baum. |
| Der Datensatz sich häufig ändert und das Aktualisieren eines sortierten Arrays teuer wäre. | Der Datensatz fest und nur lesbar ist: Ein sortiertes Array mit binärer Suche ist einfacher und cache-freundlicher. |
Binary Search Tree-Code
Eine saubere, lauffähige Binary Search Tree-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Binary Search Tree-Code in Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Binary Search Tree-Code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Binary Search Tree-Code in Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Binary Search Tree-Code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Binary Search Tree-Code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}FAQ zum binären Suchbaum
Wie ist die Zeitkomplexität eines binären Suchbaums?
Suche, Einfügen und Löschen sind in einem ausgeglichenen Baum
O(log n), weil jeder Vergleich die Hälfte der verbleibenden Knoten verwirft. Im schlimmsten Fall - ein durch sortierte Einfügungen zu einer Kette entarteter Baum - verschlechtern sie sich auf O(n).Was ist der Unterschied zwischen einem Binärbaum und einem binären Suchbaum?
Ein Binärbaum ist jeder Baum, bei dem jeder Knoten höchstens zwei Kinder hat, ohne Ordnungsregel. Ein binärer Suchbaum fügt die Invariante hinzu, dass die Werte des linken Teilbaums kleiner und die des rechten größer als der Knoten sind, was die schnelle Suche ermöglicht.
Warum kann ein binärer Suchbaum langsam werden?
Werden Werte in sortierter (oder umgekehrt sortierter) Reihenfolge eingefügt, geht jeder neue Knoten auf dieselbe Seite und erzeugt einen hohen, entarteten Baum, der sich wie eine verkettete Liste verhält:
O(n) pro Operation. Selbstbalancierende Bäume (AVL, Rot-Schwarz) rotieren Knoten, um das zu verhindern.Was ist der Unterschied zwischen einem binären Suchbaum und einer Hashtabelle?
Eine Hashtabelle bietet im Mittel
O(1)-Suchen, speichert die Schlüssel aber in keiner bestimmten Reihenfolge und kann daher keine Bereichs- oder Nachfolgerabfragen beantworten. Ein binärer Suchbaum ist mit O(log n) etwas langsamer, hält die Schlüssel aber sortiert, sodass du sie geordnet durchlaufen und Nachbarwerte finden kannst. Wähle einen BST, wenn die Reihenfolge zählt, und eine Hashtabelle, wenn du nur Mitgliedschaftstests brauchst.Wann sollte ich einen selbstbalancierenden Baum statt eines einfachen BST verwenden?
Verwende einen selbstbalancierenden Baum (AVL, Rot-Schwarz), wann immer du die Einfügereihenfolge nicht kontrollieren kannst und garantierte
O(log n)-Leistung brauchst. Ein einfacher BST ist gut für die Lehre, für kleine Datensätze oder wenn Schlüssel in zufälliger Reihenfolge eintreffen, bietet aber keinen Schutz gegen den entarteten schlimmsten Fall.Liefert eine In-order-Traversierung eines BST sortierte Werte?
Ja. Zuerst den linken Teilbaum, dann den Knoten, dann den rechten Teilbaum zu besuchen liefert die Schlüssel in aufsteigender Reihenfolge, was direkt aus der BST-Invariante folgt. Ein häufiger Fehler ist, dasselbe von einem einfachen Binärbaum zu erwarten: Ohne Ordnungsregel erzeugt die In-order-Traversierung keine sinnvolle Folge.
Verwandte Ressourcen
Mehr Visualisierungen
