Et binært søgetræ er et binært træ med en orderings-invariant: for hver knude er alle nøgler i dets venstre undertræ mindre, og alle nøgler i dets højre undertræ er større. Dette lader dig søge ved at halvere problemet ved hvert trin.
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 | Balanceret | Værste tilfælde (degenereret) |
|---|---|---|
| søgning | O(log n) | O(n) |
| indsættelse | O(log n) | O(n) |
| sletning | O(log n) | O(n) |
Det værste tilfælde opstår, når nøgler indsættes i sorteret rækkefølge — træet degenereres til en linkede liste med højde n.
BST'er giver dig sorterede, dynamiske data med logaritmiske operationer — den konceptuelle forfader til databaseindekser og sorterede kort.
Degeneringingsproblemet motiverer selv-balancerende træer, et vigtig opfølgende emne i interviews.