Árvores e Árvores de Busca¶

Uma árvore é um grafo conexo e acíclico. Em uma árvore enraizada, todo nó exceto a raiz possui um pai. A profundidade conta as arestas a partir da raiz; sob a convenção usada aqui, a altura é a maior profundidade restante até uma folha.

Invariante da árvore binária de busca¶

Para cada nó com chave k:

as chaves de sua subárvore esquerda são menores que k;
as chaves de sua subárvore direita são maiores que k;
uma política separada trata as chaves duplicadas.

Busca, inserção e remoção levam tempo O(h) para uma altura h. Uma árvore balanceada tem h = Θ(log n); uma BST comum pode degenerar para h = Θ(n).

graph TD
    A[8] --> B[3]
    A --> C[10]
    B --> D[1]
    B --> E[6]
    E --> F[4]
    E --> G[7]
    C --> H[14]
    H --> I[13]

Um percurso em ordem visita as chaves em ordem crescente. O percurso em pré-ordem é útil para serialização e cópia estrutural; o percurso em pós-ordem processa os filhos antes do pai.

Variantes balanceadas¶

Árvores AVL e rubro-negras mantêm invariantes de balanceamento diferentes por meio de rotações. Ambas garantem altura logarítmica. Árvores B e estruturas relacionadas usam fatores de ramificação elevados para reduzir acessos a páginas de armazenamento.

Exercícios¶

Liste os percursos em ordem, pré-ordem e pós-ordem da árvore acima.
Mostre uma sequência de inserção de chaves que crie uma BST com altura linear.
Explique por que uma rotação local preserva a ordem das chaves.