Uma BST guarda um invariante simples: tudo à esquerda de um nó é menor que ele, tudo à direita é maior. Isso te dá busca por divisão (O(log n), igual à binária) com a vantagem de inserir e remover sem deslocar nada. O problema: a BST pura não se equilibra sozinha. Se os dados chegam em ordem, ela vira uma lista e a busca volta pra O(n). Clica em "inserir em ordem" e vê acontecer.
A altura da árvore é o que manda na busca. Balanceada, a altura fica perto de log₂n e cada busca corta o problema pela metade. Degenerada (uma espinha), a altura vira n e a busca anda nó por nó. A BST binária não garante balanceamento; quem garante são as variantes auto-balanceadas (AVL, red-black) e a B-tree dos bancos.
Operação
Balanceada
Degenerada
Busca
O(log n)
O(n)
Inserção
O(log n)
O(n)
Remoção
O(log n)
O(n)
In-order
O(n)
O(n)
Espaço
O(n)
O(n)
BST em Go
typeNodestruct {
Val int
Left, Right *Node
}
// Insert mantém o invariante esquerda < nó < direita.func (n *Node) Insert(v int) *Node {
if n == nil {
return &Node{Val: v}
}
if v < n.Val {
n.Left = n.Left.Insert(v)
} else if v > n.Val {
n.Right = n.Right.Insert(v)
}
return n // duplicata: ignora
}
func (n *Node) Search(v int) bool {
if n == nil {
returnfalse
}
switch {
case v == n.Val:
returntruecase v < n.Val:
return n.Left.Search(v)
default:
return n.Right.Search(v)
}
}
// InOrder visita em ordem crescente.func (n *Node) InOrder(f func(int)) {
if n == nil {
return
}
n.Left.InOrder(f)
f(n.Val)
n.Right.InOrder(f)
}
🧠 Desafio — Árvores & BSTs
Mexe na árvore aqui de cima antes de responder, principalmente o "inserir em ordem". As duas últimas são de reflexão: escreve a sua e só então revela o modelo.