Estruturas de Dados Avançadas

Uma árvore B é uma árvore de busca multiária de grau mínimo t ≥ 2: um interno com k chaves tem k+1 filhos, e todas as folhas estão no mesmo nível. Uma estrutura de conjuntos disjuntos representa uma partição: cada classe tem um representante.

Busca, divisão e fusão deste tópico — e a união de componentes nas árvores geradoras mínimas — partem desses dois invariantes.

As páginas se agrupam em dois blocos. O primeiro restaura o intervalo de ocupação: a busca desce ao filho entre chaves consecutivas, a inserção divide o nó cheio, a remoção conserta o deficitário.

O segundo consulta o representante e funde classes, concatenando listas ou ligando raízes e achatando o caminho.

Contar quantas chaves um nó de grau t pode guardar, e qual chave sobe quando o nó está cheio, está em Árvores B.

Decidir se o irmão empresta via o pai, ou se os dois nós se fundem com a separadora, está em Árvores B.

O teste Find-Set(x) = Find-Set(y) está em Estruturas de Dados para Conjuntos Disjuntos.

Anexar a raiz de menor rank e apontar cada visitado para a raiz está em Estruturas de Dados para Conjuntos Disjuntos.

A árvore com chaves ordenadas e vários filhos por intervalo está em Árvores B. A floresta em que a raiz nomeia a classe está em Estruturas de Dados para Conjuntos Disjuntos.