Árvore 2-3-4

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Em ciência da computação, uma árvore 2-3-4 (também chamada árvore 2-4) é uma estrutura de dados auto-balanceada, comumente usada para implementar dicionários.[carece de fontes?] Os números significam uma árvore onde cada pai (nó interno) tem dois, três, ou quatro nós filhos:

  • um 2-nó tem um elemento de dados, e seus nós internos tem dois nós filhos;
  • um 3-nó tem dois elementos de dados, e seus nós internos tem três nós filhos;
  • um 4-nó possui três elementos de dados, e seus nós internos tem quatro nós filhos.

Árvores 2-3-4 são árvores B de ordem 4;[1] assim como árvores B em geral, eles podem pesquisar, inserir e excluir em tempo O(log n). Uma propriedade de uma árvore 2-3-4 é que todos os nós externos estão na mesma profundidade.

Árvores 2-3-4 são uma isometria de árvores rubro-negras, o que significa que eles são estruturas de dados equivalentes. Em outras palavras, para cada árvore 2-3-4, existe pelo menos uma árvore rubro-negra com elementos na mesma ordem. Além disso, as inserções e exclusões em árvores 2-3-4 que causam expansões, splits e merges são equivalentes as rotações baseadas em cores das árvores rubro-negras. Introduções ás árvores rubro-negras geralmente usam árvores 2-3-4 primeiro, porque eles são conceitualmente mais simples. Árvores 2-3-4, no entanto, podem ser difíceis de implementar na maioria das linguagens de programação, devido ao grande número de casos especiais envolvidos nas operações desta árvore. Árvores rubro-negras são mais simples de implementar,[2] por isso tendem a ser usadas em vez disso.

Propriedades[editar | editar código-fonte]

  • Cada nó (folha ou nó interno) é um 2-nó, 3-nó ou um 4-nó, e detém um, dois, ou três elementos de dados, respectivamente.
  • Todas as folhas estão na mesma profundidade (nível mais baixo).
  • Todos os dados são mantidos de forma ordenada.

Inserção[editar | editar código-fonte]

Para inserir um valor, começamos da raiz da árvore 2-3-4:

  1. Se o nó atual é um 4-nó:
    • Remova e guarde o valor médio para obter um 3-nó.
    • Realize o split nos 3-nó restantes para um par de 2-nós (o valor médio restante é tratado na próxima etapa).
    • Se este é o nó raiz (que, portanto, não tem pai ou mãe):
      • o valor médio torna-se a nova raiz de 2-nó e a altura da árvore aumenta em 1. Suba para raiz.
    • Caso contrário, eleve o valor médio para o nó pai. Suba para o nó pai.
  2. Encontre o filho cujo intervalo contém o valor a ser inserido.
  3. Se esse filho é uma folha, insira o valor no nó filho e termine.
    • Caso contrário, desça para o filho e repita a partir do passo 1.[3][4]

Exemplo[editar | editar código-fonte]

Para inserir o valor "25" para esta árvore 2-3-4:

2-3-4-tree-insertion-stage-1.svg
  • Comece na raiz (10, 20) e desça para o filho à direita (22, 24, 29). (Seu intervalo (20, ∞) contém 25.)
  • O nó (22, 24, 29) é um 4-nó, assim, o seu elemento médio 24 é empurrado para o nó pai.
2-3-4-tree-insertion-stage-2.svg
  • O 3-nó restante (22, 29) é dividido em um par de 2 nós (22) e (29). Suba de volta para o novo pai (10, 20, 24).
  • Desça para o filho próximo a direita (29). (Seu intervalo (24 – 29) contém 25.)
2-3-4-tree-insertion-stage-3.svg
  • O nó (29) não tem filho próximo mais à esquerda. (O filho para o intervalo (24 – 29) está vazio.) Pare por aqui e insira o valor 25 neste nó.
2-3-4-tree-insertion-stage-4.svg

Remoção[editar | editar código-fonte]

Considere a possibilidade de deixar apenas o elemento lá, marcando-o como "excluído", possivelmente para ser reusado em uma futura inserção.

Para remover um valor a partir da árvore 2-3-4:

  1. Encontre o elemento a ser excluído.
    • Se o elemento não está em um nó folha, lembre-se de sua localização e continue a procurar até que uma folha, que conterá o elemento sucessor, for atingida. O sucessor pode ser a maior chave que é menor do que a que será removida, ou a menor chave que é maior do que o a ser removida. É mais simples fazer ajustes na árvore utilizando a abordagem top-down (de cima para baixo), de tal forma que o nó folha encontrado não seja um 2-nó. Dessa forma, após a troca, não haverá nós folha vazios.
    • Se o elemento é uma folha 2-nó, apenas faça os ajustes a seguir.

Faça os seguintes ajustes, quando um 2-nó – exceto o nó raiz – é encontrado no caminho para a folha que desejamos remover:

  1. Se um irmão ou irmã em ambos os lados deste nó for um 3-nó ou 4-nó (tendo assim mais de 1 chave), execute uma rotação com esse irmão:
    • A chave de um outro irmão mais próximo a este nó se move acima até a chave pai, que tem os dois nós.
    • A chave pai move-se para baixo para este nó para formar um 3-nó.
    • O filho que estava originalmente com o irmão rotacionado agora é este nó filho adicional.
  2. Se o pai é um 2-nó e o irmão também é um 2-nó, combine todos os três elementos para formar um novo 4-nó e encurtar a árvore. (Esta regra só pode ser feita se o 2-nó pai é a raiz, já que todos os outros 2-nós ao longo do caminho foram modificadas para não serem 2-nós. É por isso que "encurtar a árvore" aqui preserva o balanceamento; isto também é um pressuposto importante para a operação de fusão.)
  3. Se o pai é um 3-nó ou um 4-nó e todos os irmãos adjacentes são 2-nós, faça uma operação de fusão com o pai e um irmão adjacente:
    • O irmão adjacente e o pai com os dois nós irmãos se juntam para formar um 4-nó.
    • Transfira os filhos irmãos para este nó.

Uma vez que o valor procurado é atingido, ele pode agora ser colocado na entrada do local removido sem nenhum problema, porque garante-se que o nó folha tenha mais que 1 chave.

Remoção em uma árvore 2-3-4 é O(n log n), supondo que a transferência e fusão executam em tempo constante O(1).[5]

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Knuth, Donald (1998). Sorting and Searching. Col: The Art of Computer Programming. Volume 3 Second ed. [S.l.]: Addison–Wesley. ISBN 0-201-89685-0 
  2. «Left-Leaning Red-Black Trees» (PDF). Left-Leaning Red-Black Trees 
  3. Ford, William; Topp, William (2002), Data Structures with C++ Using STL, ISBN 0-13-085850-1 2nd ed. , New Jersey: Prentice Hall 
  4. Goodrich, Michael T; Tamassia, Roberto; Mount, David M (2002), Data Structures and Algorithms in C++, ISBN 0-471-20208-8, Wiley 
  5. «(2,4) Trees» (PDF). CS251: Data Structures Lecture Notes 

Links externos[editar | editar código-fonte]