Uma árvore de busca binária é uma árvore binária com um invariante de ordenação: para cada nó, todas as chaves na subárvore esquerda são menores, e todas as chaves na subárvore direita são maiores. Isso permite que você pesquise dividindo o problema pela metade em cada etapa.
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 | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
O pior caso ocorre quando as chaves são inseridas em ordem classificada — a árvore degenera em uma lista vinculada de altura n.
As BSTs oferecem dados ordenados e dinâmicos com operações logarítmicas — o ancestral conceitual de índices de banco de dados e mapas ordenados.
O problema de degeneração motiva self-balancing trees, um tópico de acompanhamento fundamental em entrevistas.