Binary search trees · Árvores binárias de busca
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
Á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.
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger.
- This one rule is what lets you find a value by going left or right — never both.
A regra da BST
- Para todo nó: tudo em seu subárvore esquerda é menor, tudo em sua direita é maior.
- 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
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
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
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
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
In-order traversal gives sorted order
- In-order traversal visits: the left subtree, then the node, then the right subtree.
- Because of the BST rule, this visits the values in sorted order — for free.
- It is naturally recursive: traverse left, take the value, traverse right.
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]
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
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).
Common mistakes
- In a binary search tree: left child < node < right child.
- An unbalanced tree loses the speed advantage.
Erros comuns
- Em uma árvore de busca binária: filho esquerdo < nó < filho direito.
- Uma árvore desbalanceada perde a vantagem de velocidade.
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
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.
Searching a BST · Buscando em uma BST
Left is smaller, right is bigger — so each step skips half the tree. · Esquerda é menor, direita é maior — então a cada passo pula metade da árvore.
The · A Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · 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 [].
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Node and a working insert are provided. Write contains(root, value) that returns True if · se value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left · para a esquerda, otherwise search right · correta; an empty branch (None) means it is not there. · 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á.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.