Á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).[1]

  • 2-node
    2-node
  • 3-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.


Referências

  1. ↑ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. [S.l.]: Prentice Hall. ISBN 84-205-2980-X 

Ligações externas

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