Árvores binárias de busca
Árvores binárias de busca
- Uma árvore binária de busca (BST) armazena valores para que permaneçam ordenados e sejam rápidos de encontrar.
- Cada nó armazena um valor e links para até dois filhos: um
lefte umright. - O nó superior é a raiz. Um nó sem filhos é uma folha.
A regra da BST
- Para todo nó: tudo em seu subárvore esquerdo é menor, tudo em sua direita é maior ou igual (esta lição envia valores iguais à direita).
- Essa única regra é o que permite encontrar um valor indo para a esquerda ou direita — nunca ambas.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
Um nó
- Modelamos um nó como um pequeno objeto com um
value, umlefte umright. - Um nó recém-criado ainda não tem filhos, então
lefterightcomeçam comoNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Inserindo um valor
- Comece na raiz. Se a árvore estiver vazia, o novo valor torna-se a raiz.
- Se o valor for menor que o nó atual, vá para a esquerda; caso contrário, vá para a direita.
- Repita até encontrar um espaço vazio e coloque o novo nó ali.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
Traversal in-order fornece ordem ordenada
- Traversal in-order visita: a subárvore esquerda, depois o nó, depois a subárvore direita.
- Devido à regra da BST, isso visita os valores em ordem ordenada — gratuitamente.
- É naturalmente recursivo: traverse a esquerda, pegue o valor, traverse a direita.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
Buscar é rápido
- Para encontrar um valor, compare-o com o nó, depois vá para a esquerda ou direita — pulando metade da árvore a cada etapa.
- Em uma árvore equilibrada, isso leva cerca de
O(log n)passos, muito mais rápido do que varrer uma lista. - Uma árvore mal formatada (valores inseridos já ordenados) pode se degradar em uma linha —
O(n).
Erros comuns
- Em uma árvore binária de busca: filho esquerdo < nó <= filho direito (valores iguais vão à direita aqui).
- Uma árvore desbalanceada perde a vantagem de velocidade.
Agora você tenta
- Construa as três operações básicas:
insert,in_orderecontains. - A classe
Node(e uminsertfuncional, onde necessário) é fornecida. - Pressione Check answer para testá-lo em várias árvores.
Buscando em uma BST
Esquerda é menor, direita é maior — então a cada passo pula metade da árvore.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
A classe Node é fornecida. Escreva insert(root, value) que adiciona value à BST e retorne a raiz. Se root for None, retorne uma nova Node(value). Se value < root.value for para a esquerda, caso contrário vá para a direita — e reatribua esse filho ao resultado de inserir nele.
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
Node e uma insert funcional são fornecidas. Escreva in_order(root) que retorna uma lista dos valores de um percurso em ordem: subárvore esquerda, depois o valor deste nó, depois a subárvore direita. Graças à regra da BST, a lista vem ordenada. Uma árvore vazia (None) resulta em [].
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
Node e uma insert funcional são fornecidas. Escreva contains(root, value) que retorna True se value estiver na árvore, senão False. Use a regra da BST: se for igual a este nó retorne True; se for menor pesquise à esquerda, caso contrário pesquise à direita; um ramo vazio (None) significa que não está lá.
Clique em Executar para ver a saída aqui.