Árvore 2-3-4
# Árvore 2-3-4

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.$^[$ Os números significam uma árvore onde cada nó 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.
* 2-nó
* 3-nó
* 4-nó
Árvores 2-3-4 são árvores B de ordem 4; 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, por isso tendem a ser usadas em vez disso.

## Propriedades

* 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

Para inserir um valor, começamos da raiz da árvore 2-3-4:
* 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.
* Encontre o filho cujo intervalo contém o valor a ser inserido.
* 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.

### Exemplo

Para inserir o valor "25" para esta árvore 2-3-4:
* 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.
* 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.)
* 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ó.

## Remoção

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:
* 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:
* 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.
* 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.)
* 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).