Ein binärer Suchbaum ist ein binärer Baum mit einer Ordnungsinvariante: Für jeden Knoten sind alle Schlüssel im linken Unterbaum kleiner, und alle Schlüssel im rechten Unterbaum größer. Dies ermöglicht dir, das Problem bei jedem Schritt zu halbieren.
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| Operation | Balanciert | Schlechtester Fall (degeneriert) |
|---|---|---|
| Suche | O(log n) | O(n) |
| Einfügen | O(log n) | O(n) |
| Löschen | O(log n) | O(n) |
Der schlechteste Fall tritt auf, wenn Schlüssel in sortierter Reihenfolge eingefügt werden — der Baum degeneriert zu einer verknüpften Liste der Höhe n.
BST bieten dir sortierte, dynamische Daten mit logarithmischen Operationen — der konzeptionelle Vorläufer von Datenbankindexen und geordneten Maps.
Das Degenerationsproblem motiviert selbstbalancierende Bäume, ein Schlüssel-Folgethema in Interviews.