Siġra ta' tfittxija binarja hija siġra binarja b'invarjant ta' ordnar: għal kull nodu, l-atikli l-istednin tal-kahh tiegħu ċinituri huma isgħar, u l-atikli l-istednin tal-kahh tal-lemin tiegħu huma akbar. Dan jippermettilek tfittex billi tuża nofs il-problema f'kull pass.
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
| Operazzjoni | Bilanċjat | Agħar (deġenerazzjonata) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
L-agħar każ isseħħ meta l-atikli jinsiraw f'ordni sortati — is-siġra tadeġenera f'lista mqabbda ta' għoli n.
BST jagħtik dejta dinamika ordinata b'operazzjonijiet logaritmiki — il-antenatt kunċettwali tal-indiċi tad-databażi u l-mapep ordinati.
Il-problema tal-deġenererazzjoni timmotiva siġar li jibilançjaw waħedhom, suġġett ta' segwitu importanti fl-intervisti.