Binární vyhledávací strom je binární strom s invariantem řazení: pro každý uzel všechny klíče v jeho levém podstromě jsou menší a všechny klíče v jeho pravém podstromě jsou větší. To vám umožňuje hledat halving problém v každém kroku.
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
| Operace | Vyvážené | Nejhorší (degenerovaný) |
|---|---|---|
| hledání | O(log n) | O(n) |
| vkládání | O(log n) | O(n) |
| smazání | O(log n) | O(n) |
Nejhorší případ nastane, když jsou klíče vkládány v seřazeném pořadí — strom se degeneruje do spojového seznamu výšky n.
BST vám poskytuje seřazená, dynamická data s logaritmickými operacemi — koncepční předchůdce databázových indexů a seřazených map.
Problém degenerace motivuje self-balancing stromy, klíčové téma pro navazující otázky v pohovorech.