# data[].attributes.body
João Paulo de Melo Bispo
Luis Henrique da Silva
Higor Vinícius de Lima

# data[].attributes.body
Arvores 2-3-4 é uma das estruturas de dados mais eficientes entre as várias existentes. São também chamadas de árvores multivias, pois podem te até quatro filhos e três itens de dados por nó.

Sua estrutura e propriedade permite que possamos realizar inserir, buscar e remover elementos de forma rápida e usando menos recurso computacional, sendo balanceadas e relativamente fáceis de programar.

# data[].attributes.body
A estrutura de uma árvore 2-3-4 é determinada pela seguinte relação:

N° DE ITENS DE DADOS POR NÓ / N° DE FILHOS POR NÓ

1 2
2 3
3 4

Ex1: O nó com 1 chave terá no máximo 2 filhos.
Ex2: O nó com 2 chaves terá no máximo 3 filhos.
Ex3: O nó com 3 chaves terá no máximo 4 filhos.

Os nós folhas não tem filhos e assim seus ponteiros ficam indefinidos (NULL). Uma característica importante da árvore 2-3-4 é que um nó deverá ter no mínimo 2 filhos, a não ser que seja uma folha.

# data[].attributes.body
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ó.

# data[].attributes.body
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.

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.

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.

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.

# data[].attributes.body
As arvores 2-3-4 são arvores multidirecionais, ou seja, cada nó poderá ter um minimo de 2 ou máximo de 3 campos de dados e até quatro filhos.

Os nós situados na última fila são denominados folhas e estão sempre no mesmo nível.

Os números 2,3,4 se referem a quantidade de filhos que um nó poderá ter, como também a quantidade de ponteiros.

Caso qualquer um dos nós ficar com apenas um filho, é necessário que se faça um tratamento para que todas as folhas permaneçam no mesmo nível.

# data[].attributes.body
Buscas em árvores 2-3-4 nunca passam de log n + 1, logo O(log n).

1. A distância da raiz para as folhas são sempre a mesma. Transformações não mudam esta distância, exceto no pior caso em que a transformação divide a raiz e aumenta em 1 a distância de todos os nós para a raiz.

# data[].attributes.body
A implementação de uma arvore 2-3-4 é usada em diversos tipos de aplicações, como: dicionários, auto completar (auto complete) e banco de dados como mecanismo de organização interna de dados.

# data[].attributes.body
Porque uma árvore 2-3-4 não pode ser chamada de árvore 1-2-3-4?

Um nó não pode ter somente um filho, como os nós das árvores binárias. Na verdade um nó com item de dado precisa ter sempre dois links, a menos que seja um nó folha, neste caso ele não possui links.