A bináris keresési fa egy bináris fa, amelyhez rendezési invariáns tartozik : minden csomópontra igaz, hogy a bal részfában lévő összes kulcs kisebb, és a jobb részfában lévő összes kulcs nagyobb. Ez lehetővé teszi, hogy az adatokat úgy keresse, hogy minden lépésben felezi a problémát.
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
| Operáció | Kiegyensúlyozott | Legrosszabb (degenerált) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
A legrosszabb eset akkor fordul elő, amikor a kulcsokat rendezés szerinti sorrendben szúrjuk be — a fa egy n magasságú összekapcsolt listává degenerálódik.
A BST-k rendezett, dinamikus adatokat biztosítanak logaritmusos műveletek segítségével — az adatbázisindexek és rendezett térképek elméleti előfutárai.
A degenerációs probléma az önelosztó fákat motiválja, amely kulcsfontosságú téma az interjúk követéséhez.