Árvore de Busca Binária

Conceito

Uma BST é uma 1. Árvore Binária com um invariante:

Para todo nó n: tudo na subárvore esquerda é menor que n, e tudo na subárvore direita é maior.

      5
     / \
    3   8
   / \
  1   7      <- 7 > 5, mas está na subárvore ESQUERDA de 5

Por que a busca é O(log n): em cada nó você compara uma vez e desce para um lado só — descartando a outra subárvore inteira. Se a árvore é balanceada, cada passo elimina metade dos candidatos. É 1. Busca Binária sobre uma estrutura ligada.

Como degenera para O(n): inserindo em ordem crescente. 1,2,3,4,5 numa BST simples produz uma cadeia à direita — uma lista ligada. E dados do mundo real chegam ordenados com uma frequência incômoda (ids, timestamps, importações). É exatamente por isso que árvores auto-balanceadas existem.

Remoção, o único caso não trivial. Três situações:

O sucessor in-order é a escolha certa porque ele é, por definição, o menor valor maior que o nó — o único que pode ocupar aquele lugar sem quebrar o invariante. E ele tem no máximo um filho, o que reduz o caso difícil a um caso fácil.

BST vs 6. Hash Map — a decisão real:

Se você só busca por chave, hash. Se você precisa de ordem, árvore.

Em Go

Não há BST na stdlib, e isso te obriga a escolher entre duas respostas idiomáticas:

1. map + slices.Sort na hora de precisar de ordem — funciona bem quando as consultas ordenadas são raras em relação às escritas.
2. slice mantido ordenado + slices.BinarySearch — busca O(log n), inserção O(n) pelo deslocamento, mas com localidade perfeita. Para coleções de até alguns milhares de elementos, isso bate uma BST de ponteiros na prática.

BST à mão só quando você realmente precisa de inserção e consulta ordenada intercaladas em volume. E aí a advertência importa: a sua BST não se rebalanceia. Sem rotações, entrada ordenada te dá O(n).

A validação correta em Go usa limites como ponteiros (*T), porque nil expressa "sem limite" sem precisar de valores sentinela como math.MinInt:

func valida(n *No, min, max *int) bool

Respostas às perguntas-guia

1. Qual é o invariante da BST, e o que quebra se você violá-lo?

Conceito: toda a subárvore esquerda < nó < toda a subárvore direita. Violado, a busca fica incorreta — ela desce para um lado e o valor estava no outro. Não fica lenta: fica errada, devolvendo "não existe" para algo que existe.

Em Go: nada específico, exceto que ninguém valida isso para você — não há tipo BST na stdlib que garanta o invariante por construção.

2. Por que busca é O(log n) — e como ela degenera para O(n)?

Conceito: cada comparação descarta uma subárvore. Degenera quando a árvore é degenerada, tipicamente por inserção ordenada.

Em Go: como não há auto-balanceamento na stdlib, degenerar é o caso provável, não o excepcional. É o principal argumento a favor de usar slice ordenado.

3. Como remover um nó com dois filhos sem quebrar o invariante?

Conceito: substituir pelo sucessor in-order (menor da subárvore direita) e remover o sucessor. Ele é o único valor que serve, e tem no máximo um filho.

Em Go: a recursão fica limpa devolvendo o novo nó — func remove(n *No, v int) *No — em vez de manipular o ponteiro do pai. Esse estilo "devolva a subárvore reconstruída" elimina toda a contabilidade de ponteiros.

4. Quando você preferiria uma BST a um 6. Hash Map?

Conceito: quando precisa de ordem — mínimo, máximo, sucessor, faixa, iteração ordenada.

Em Go: quase nunca escrevendo uma BST. Faixa e ordem costumam ser resolvidas por slice ordenado + slices.BinarySearch, e quando o volume justifica, por github.com/google/btree. Se a consulta por faixa é o coração do sistema, provavelmente ela pertence ao banco de dados (que já é uma B-tree — ver 5. Índices).

Trade-offs

Do conceito:

• BST compra ordem e cobra altura: sem balanceamento, a garantia evapora.
• Auto-balanceamento compra O(log n) garantido e cobra rotações em cada escrita.
• Hash compra O(1) e cobra a perda total de ordem.

Em Go:

• Slice ordenado + BinarySearch compra localidade e simplicidade; cobra O(n) na inserção. Para n pequeno ou médio, esse O(n) com memmove perde de nada.
• BST de ponteiros cobra uma alocação por nó e cache miss por nível.
• Não ter BST na stdlib é bom para a simplicidade da linguagem e é a fonte de uma pergunta recorrente de quem vem de Java.

Exemplo prático

package main

import "fmt"

type No struct {
	Val      int
	Esq, Dir *No
}

// Estilo "devolva a subárvore": elimina a contabilidade de ponteiros do pai.
func insere(n *No, v int) *No {
	if n == nil {
		return &No{Val: v}
	}
	switch {
	case v < n.Val:
		n.Esq = insere(n.Esq, v)
	case v > n.Val:
		n.Dir = insere(n.Dir, v)
	}
	return n
}

func busca(n *No, v int) bool {
	for n != nil { // iterativo: nao precisa de pilha
		switch {
		case v == n.Val:
			return true
		case v < n.Val:
			n = n.Esq
		default:
			n = n.Dir
		}
	}
	return false
}

func remove(n *No, v int) *No {
	if n == nil {
		return nil
	}
	switch {
	case v < n.Val:
		n.Esq = remove(n.Esq, v)
	case v > n.Val:
		n.Dir = remove(n.Dir, v)
	default:
		if n.Esq == nil {
			return n.Dir
		}
		if n.Dir == nil {
			return n.Esq
		}
		s := n.Dir // sucessor in-order: menor da subarvore direita
		for s.Esq != nil {
			s = s.Esq
		}
		n.Val = s.Val
		n.Dir = remove(n.Dir, s.Val)
	}
	return n
}

// A validação CORRETA: propaga limites. nil = sem limite.
func valida(n *No, min, max *int) bool {
	if n == nil {
		return true
	}
	if min != nil && n.Val <= *min {
		return false
	}
	if max != nil && n.Val >= *max {
		return false
	}
	return valida(n.Esq, min, &n.Val) && valida(n.Dir, &n.Val, max)
}

// A validação ERRADA, que quase todo mundo escreve primeiro:
func validaErrado(n *No) bool {
	if n == nil {
		return true
	}
	if n.Esq != nil && n.Esq.Val >= n.Val {
		return false
	}
	if n.Dir != nil && n.Dir.Val <= n.Val {
		return false
	}
	return validaErrado(n.Esq) && validaErrado(n.Dir)
}

func emOrdem(n *No, out *[]int) {
	if n == nil {
		return
	}
	emOrdem(n.Esq, out)
	*out = append(*out, n.Val)
	emOrdem(n.Dir, out)
}

func altura(n *No) int {
	if n == nil {
		return 0
	}
	e, d := altura(n.Esq), altura(n.Dir)
	if e > d {
		return e + 1
	}
	return d + 1
}

func main() {
	var t *No
	for _, v := range []int{5, 3, 8, 1, 4, 7, 9} {
		t = insere(t, v)
	}
	var ord []int
	emOrdem(t, &ord)
	fmt.Println("in-order sai ordenado:", ord)
	fmt.Println("busca(4):", busca(t, 4), " busca(6):", busca(t, 6))

	t = remove(t, 8) // nó com dois filhos
	ord = nil
	emOrdem(t, &ord)
	fmt.Println("apos remover 8:      ", ord)

	// entrada ORDENADA degenera a arvore
	var deg *No
	for i := 1; i <= 7; i++ {
		deg = insere(deg, i)
	}
	fmt.Printf("balanceada altura=%d | degenerada altura=%d\n", altura(t), altura(deg))

	// a arvore invalida que engana a validacao ingenua
	ruim := &No{5, &No{3, &No{Val: 1}, &No{Val: 7}}, &No{Val: 8}}
	fmt.Println("validaErrado diz:", validaErrado(ruim), "| valida diz:", valida(ruim, nil, nil))
}

Relacionado

• 1. Árvore Binária — a estrutura, sem o invariante
• 3. Travessias de Árvore — por que in-order sai ordenado
• 6. Hash Map — semana 2, o concorrente direto
• 1. Busca Binária — semana 4, o mesmo descarte pela metade, sobre array
• 5. Índices — semana 9, a B-tree do banco é esta ideia em disco

Parte de Semana 03 - Estruturas de Dados II e Recursão · 00 - MOC Fundamentos de Programação