Árvore Binária

Conceito

Uma árvore é uma estrutura hierárquica e acíclica: cada nó tem um pai (exceto a raiz) e, na árvore binária, no máximo dois filhos.

O vocabulário mínimo: raiz (sem pai), folha (sem filhos), profundidade de um nó (distância até a raiz), altura da árvore (a maior profundidade), subárvore (um nó e tudo abaixo dele).

A definição é recursiva: uma árvore binária é ou vazia, ou um nó com duas árvores binárias. Isso não é curiosidade — é o motivo de recursão ser a ferramenta natural aqui. O código espelha a definição do dado.

Manter o balanceamento sob inserção e remoção é o que árvores auto-balanceadas (AVL, red-black, B-tree) fazem — ao custo de rotações e de mais código.

Dados que são naturalmente árvores: sistema de arquivos, DOM, AST de um compilador, organograma, taxonomia, e o índice de um banco relacional (que é uma B-tree — ver 5. Índices).

Em Go

Não existe árvore na stdlib — nem TreeMap, nem BST. É uma decisão deliberada: o map builtin mais slices.Sort cobre a esmagadora maioria dos casos, e quem precisa de árvore ordenada usa biblioteca externa. O único parente na stdlib é container/heap, que é um heap sobre slice.

A definição idiomática usa generics e nil como árvore vazia — sem nó sentinela:

type No[T any] struct {
	Val         T
	Esq, Dir    *No[T]
}

Métodos com receiver *No[T] que funcionam com receiver nil são idiomáticos em Go, e aqui isso brilha: func (n *No[T]) Altura() int { if n == nil { return 0 } ... }. O caso base da recursão é o ponteiro nil, sem nenhuma verificação extra no chamador.

A árvore sem ponteiros: um heap binário mora num slice, onde os filhos do índice i são 2i+1 e 2i+2. Zero ponteiros, zero alocação por nó, localidade perfeita — é o que container/heap usa. Vale conhecer porque mostra que "árvore" é a relação entre os elementos, não a presença de ponteiros.

Sobre a profundidade da recursão: Go não tem tail-call optimization, mas a stack da goroutine cresce até 1 GB (2. Stack vs Heap). Recursão sobre árvore balanceada nunca estoura — a altura de uma árvore balanceada com um trilhão de nós é ~40. O risco é a árvore degenerada.

Respostas às perguntas-guia

1. O que define uma árvore: nós, arestas, raiz, folha, altura?

Conceito: um grafo conexo e acíclico com uma raiz distinguida. A ausência de ciclo é o que permite recursão sem marcar visitados (ver 4. Grafos).

Em Go: *No[T] com Esq/Dir, e nil representando vazio.

2. Por que a altura é o que determina o custo das operações?

Conceito: porque a operação desce um nível por passo. O número de passos é a altura, não o número de nós.

Em Go: nada de específico — mas é a razão pela qual você mede a altura antes de culpar a implementação por uma busca lenta.

3. O que é uma árvore balanceada e por que isso importa?

Conceito: altura O(log n). Importa porque é a diferença entre O(log n) e O(n) — a mesma estrutura, mesmo código, desempenho de outra ordem.

Em Go: como não há BST auto-balanceada na stdlib, uma árvore que você escreva à mão não se rebalanceia. Se a entrada vier ordenada, você construiu uma lista ligada.

4. Que dados do mundo real são naturalmente árvores?

Conceito: tudo hierárquico com pai único: arquivos, DOM, AST, organograma, categorias.

Em Go: o exemplo mais próximo do seu dia é o pacote go/ast — o compilador de Go representa seu código como uma árvore, e go/parser a produz. Rodar ast.Print(fset, arquivo) num arquivo pequeno é um exercício que vale a semana.

Trade-offs

Do conceito:

• Árvore compra ordem e busca O(log n); cobra ponteiros, alocação por nó e localidade ruim comparada a um array.
• Auto-balanceamento compra a garantia de O(log n); cobra complexidade de implementação e trabalho extra em cada escrita.
• Árvore em array (heap) compra localidade e zero ponteiros; cobra flexibilidade — só funciona se a árvore for (quase) completa.

Em Go:

• Não ter árvore na stdlib mantém a linguagem pequena e te empurra para map + slices.Sort, que é a resposta certa na maioria dos casos e a errada quando você precisa de faixa ou de sucessor.
• Um nó por alocação = pressão de GC proporcional ao número de nós.

Exemplo prático

package main

import "fmt"

type No[T any] struct {
	Val      T
	Esq, Dir *No[T]
}

// Métodos que aceitam receiver nil: o caso base da recursão É o nil.
func (n *No[T]) Altura() int {
	if n == nil {
		return 0
	}
	e, d := n.Esq.Altura(), n.Dir.Altura()
	if e > d {
		return e + 1
	}
	return d + 1
}

func (n *No[T]) Nos() int {
	if n == nil {
		return 0
	}
	return 1 + n.Esq.Nos() + n.Dir.Nos()
}

func (n *No[T]) Folhas() int {
	switch {
	case n == nil:
		return 0
	case n.Esq == nil && n.Dir == nil:
		return 1
	}
	return n.Esq.Folhas() + n.Dir.Folhas()
}

func main() {
	// balanceada: 7 nós, altura 3 = log2(8)
	bal := &No[int]{4,
		&No[int]{2, &No[int]{Val: 1}, &No[int]{Val: 3}},
		&No[int]{6, &No[int]{Val: 5}, &No[int]{Val: 7}}}

	// degenerada: 7 nós, altura 7 — uma lista ligada
	var deg *No[int]
	for i := 7; i >= 1; i-- {
		deg = &No[int]{Val: i, Dir: deg}
	}

	for nome, t := range map[string]*No[int]{"balanceada": bal, "degenerada": deg} {
		fmt.Printf("%-11s nos=%d altura=%d folhas=%d\n",
			nome, t.Nos(), t.Altura(), t.Folhas())
	}

	// a MESMA estrutura, custo de busca de outra ordem:
	fmt.Println("passos para achar o 7: balanceada=3, degenerada=7")
}

Relacionado

• 2. Árvore de Busca Binária — a árvore com um invariante que a torna útil
• 3. Travessias de Árvore — as três ordens de visita
• 5. Recursão — a definição recursiva do dado vira o código
• 4. Grafos — a generalização: sem raiz e com ciclos

---

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