Laboratório de árvores

Árvore

Um grafo conexo e sem ciclos simples. Com n vértices, tem exatamente n − 1 arestas, e entre dois vértices quaisquer há um único caminho simples.

Árvore livre e enraizada

Na árvore livre, nenhum vértice é especial. Ao escolher uma raiz, cada aresta passa a ligar um pai a um filho, do lado da raiz para longe dela. Toda árvore enraizada tem uma raiz, menos a árvore vazia, que não tem nenhum nó.

Pai, filho e irmão

Todo nó, menos a raiz, tem um único pai: o vizinho dele no caminho até a raiz. Os outros vizinhos são os filhos. Irmãos são filhos do mesmo pai.

Ancestral e descendente

Os ancestrais de um nó são o pai, o pai do pai e assim por diante, até a raiz. Os descendentes são os filhos, os filhos dos filhos e assim por diante, até as folhas.

Folha e nó interno

Folha é um nó sem filhos. Nó interno é qualquer nó que não seja folha. Numa árvore de um nó só, a raiz é uma folha.

Subárvore

Cada nó, junto com todos os seus descendentes, forma uma árvore com raiz nele: a subárvore daquele nó. As subárvores dos filhos de um nó não têm nó em comum, e tudo o que vale para árvores vale para cada subárvore.

Menor ancestral comum

Entre os ancestrais comuns de dois nós u e v, o menor ancestral comum é o mais fundo, o mais distante da raiz. Aqui, cada nó também conta como ancestral de si mesmo: se u é ancestral de v, o menor ancestral comum é o próprio u. O único caminho entre u e v sobe de u até ele e depois desce até v.

Aridade

A aridade de uma árvore enraizada é o maior número de filhos de um nó. Uma árvore em que cada nó tem no máximo m filhos é m-ária; a árvore binária é a 2-ária. A aridade depende da raiz escolhida: no laboratório, trocar a raiz pode mudá-la.

Profundidade

A profundidade de um nó é o número de arestas no caminho da raiz até ele. A raiz tem profundidade 0, os filhos dela, 1, e assim por diante.

Nível

O nível k reúne os nós de profundidade k (alguns livros começam a contar do 1). Nós do mesmo nível não são necessariamente irmãos; quando os pais são diferentes, a Leitura 08 sugere chamá-los de primos.

Altura da árvore

A altura é da árvore, não do nó: a maior profundidade entre os seus nós, isto é, o número do último nível. Uma árvore de um nó só tem altura 0; a árvore vazia, −1.

Centro da árvore

O centro de uma árvore reúne os vértices que ficam mais perto de todos os outros: os que tornam menor a distância até o vértice mais longe. Escolhido como raiz, um vértice do centro deixa a árvore com a menor altura possível. Toda árvore tem um centro com um ou dois vértices.

Pré-ordem

Anota a raiz da subárvore; depois percorre a subárvore esquerda e, por fim, a direita: raiz, esquerda, direita.

In-ordem (em ordem)

Percorre a subárvore esquerda, anota a raiz e depois percorre a direita: esquerda, raiz, direita. Numa árvore de busca binária, dá as chaves em ordem crescente.

Pós-ordem

Percorre a subárvore esquerda, depois a direita, e só então anota a raiz: esquerda, direita, raiz.

Árvore binária

Árvore enraizada em que cada nó tem no máximo dois filhos, chamados esquerdo e direito. A subárvore esquerda de um nó é a subárvore do filho esquerdo dele; a direita, a do filho direito.

Estrita

Todo nó tem 0 ou 2 filhos. Numa árvore estrita, o número de folhas é sempre o número de nós internos mais 1.

Completa

Todos os níveis estão cheios, menos talvez o último, que se enche da esquerda para a direita. Dito de outro modo: lendo as casas nível por nível, cada nível da esquerda para a direita, nenhuma casa vazia aparece antes de um nó.

Perfeita

Todos os níveis estão cheios. Com altura h, a árvore tem 2^h+1 − 1 nós, e 2^h deles são folhas.

Degenerada

Árvore binária em que cada nó tem no máximo um filho: ela é um caminho, e a altura chega a n − 1, a maior possível com n nós. É o que acontece com a árvore de busca quando as chaves entram em ordem crescente, como no capítulo 4: uma busca pode precisar de n comparações, como numa lista.

Árvore completa num vetor

Uma árvore completa cabe num vetor sem casas vazias: lendo os nós nível por nível, a partir da posição 1, o nó da posição i tem os filhos nas posições 2i e 2i + 1 e o pai na posição ⌊i/2⌋. Assim, não é preciso guardar ponteiros. É desse jeito que se guarda um heap, a estrutura das filas de prioridade.

Árvore de busca binária

Árvore binária com uma chave em cada nó, maior que todas as chaves da subárvore esquerda e menor que (ou igual a) todas as da direita: chaves iguais vão para a direita. A in-ordem lista as chaves em ordem crescente.

Busca

Começa na raiz e, a cada nó, compara: chave menor desce para a esquerda; maior, para a direita. Para ao achar a chave ou ao cair numa casa vazia, depois de no máximo altura + 1 comparações.

Inserção

Desce como na busca, com as chaves iguais seguindo para a direita, e põe a chave nova na casa vazia onde a descida parou: ela sempre entra como folha.

Remoção

Primeiro a busca acha o nó; o que vem depois depende de quantos filhos ele tem. Folha: sai direto. Um filho: o filho sobe para o lugar dele. Dois filhos: o nó recebe a chave do sucessor, o descendente mais à esquerda da subárvore direita, que então sai do lugar antigo. Use “Anterior” e “Próximo” para ver os três casos; em cada um, o botão embaixo do desenho muda os ponteiros, um passo por vez.

Altura das subárvores

Cada nó é a raiz de uma subárvore, e a altura dela sai das alturas das subárvores dos filhos, com −1 para a subárvore vazia. Como cada nó precisa das alturas dos filhos, o cálculo segue a pós-ordem: primeiro as folhas, por último a raiz. Muitas implementações da árvore AVL guardam essa altura em cada nó e a atualizam a cada inserção ou remoção; assim, o fator de balanceamento sai na hora, sem percorrer a subárvore de novo.

def altura(no):
    if no is None:
        return -1
    return 1 + max(altura(no.esq), altura(no.dir))

Fator de balanceamento

O fator de balanceamento de um nó é a altura da subárvore esquerda menos a altura da subárvore direita; a subárvore vazia tem altura −1. Fator positivo: o nó pende para a esquerda; negativo, para a direita. Quando todo fator é −1, 0 ou 1, a altura da árvore fica perto de log₂ n, onde n é a quantidade de nós na árvore, e a busca é rápida.

Rotação

Uma rotação troca um nó de lugar com um dos filhos sem estragar a ordem das chaves. Na rotação à direita em no, o filho esquerdo, f = no.esq, sobe e no desce para a direita: no.esq passa a ser f.dir, f.dir passa a ser no, e quem apontava para no passa a apontar para f. Na rotação à esquerda, é o filho direito que sobe. Só esses três ponteiros mudam, e a in-ordem continua a mesma: a árvore continua sendo de busca. O botão embaixo do desenho roda o código uma linha por vez.

Balanceamento por rotações

Quando um nó fica com fator +2 ou −2, uma ou duas rotações perto dele deixam todos os fatores de novo entre −1 e 1, sem mudar a in-ordem. A árvore AVL faz essas rotações sempre que uma inserção ou remoção deixa algum nó com fator menor que −1 ou maior que 1; assim, a altura fica sempre perto de log₂ n, onde n é a quantidade de nós. As árvores rubro-negras também giram, mas seguem outra regra, com cores nos nós.

Balanceamento pela mediana

A outra forma da Leitura 08: de tempos em tempos, refazer a árvore do zero. Com as chaves em ordem crescente, que é a in-ordem, insere primeiro a do meio, que vira a raiz, e depois, do mesmo jeito, as do meio de cada metade. Diferente das rotações, que consertam a árvore aos poucos, no lugar, aqui a árvore inteira é construída de novo.