Árvore 2-3

Em Ciência da Computação, uma Árvore 2-3 é uma árvore onde cada nó com filho (nó interno) tem também 2 filhos (2-node) e 1 elemento de dados (chave) ou 3 filhos (3-nodes) e 2 elementos de dados (chaves). Os nós externos a árvore (nós-folha) não tem filhos e possuem um ou dois elementos de dados (chaves).

• 
  2-node
• 
  3-node

Propriedades

• Cada nó interno tem dois filhos (2-node) se tem uma chave, ou três filhos (3-node) se tem duas chaves;
• Cada nó não-folha tem 2 ou 3 filhos. Se tem 2 filhos tem 1 item de dados e se tem 3 filhos tem 2 itens de dados;
• Todas as folhas estão no mesmo nível;
• Todos os dados são ordenados;
• Cada nó folha tem 1 ou 2 campos.

Nós não-folha

Contém um ou dois campos que indicam o intervalo de valores em suas sub-árvores. Se o nó tem dois filhos, ele terá um campo. Se o nó tem três filhos, ele terá dois campos. Cada nó não-folha irá contar com um valor no campo 1 que é maior que o maior item da sub-árvore a esquerda, mas menor ou igual ao menor item na sub-árvore a direita (ou sub-árvore central, se ela tem três filhos). Se o nó tem três filhos, o campo 2 contém um valor que é maior que o maior valor no centro da sub-árvore, mas menor ou igual ao menor número na sub-árvore direita. O objetivo desses valores é dirigir uma função de busca para a sub-árvore correta e, eventualmente, para o nó de dados correto.

Ligações externas

• Applet Java - Árvore 2-3, com operações de busca, inserção e remoção

ZIVIANI, Nivio. Projeto de Algoritmos: com implementações em Pascal e C. 3. ed. São Paulo: Cengage Learning, 2013. 639 p.