Pohon pencarian binari yaiku pohon binari karo invariant pesen: kanggo saben simpul, kabeh tombol ing subpohon kiwa luwih cilik, lan kabeh tombol ing subpohon tengen luwih gedhe. Iki ngidini sampeyan nglurug kanthi mateng perong masalah ing saben langkah.
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
| Operasi | Seimbang | Paling parah (degenerasi) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
Kasus paling parah dumadi nalika tombol disisipake kanthi urutan - pohon degenerat dadi daftar tertaut kanthi tinggi n.
BST menehi sampeyan data dinamisyang terurut kanthi operasi logaritmik - leluhur konseptual saka indeks basis data lan peta terurut.
Masalah degenerasi motivasi pohon self-balancing, topik tindak lanjut kunci ing wawancara.