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. Á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: 308x308px 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. 274x274px 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.) 300x300px 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ó. 349x349px
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).
Exemplo de código fonte public class TwoThreeFourTree { private Node root;
private class Node { private int[] keys = new int; private Node[] children = new Node; private int numKeys;
public int getNumKeys() { return numKeys;
public int getKey(int index) { return keys[index];
public Node getChild(int index) { return children[index];
public void setChild(int index, Node child) { children[index] = child;
public boolean isLeaf() { return children == null;
public void insertNonFull(int key) { int i = numKeys - 1; if (isLeaf()) { while (i >= 0 && keys[i] > key) { keys[i + 1] = keys[i]; i--;
keys[i + 1] = key; numKeys++; } else { while (i >= 0 && keys[i] > key) { i--;
if (children[i + 1].getNumKeys() == 3) { splitChild(i + 1, children[i + 1]); if (keys[i + 1] < key) { i++;
children[i + 1].insertNonFull(key);
public void splitChild(int index, Node node) { Node newNode = new Node(); newNode.numKeys = 1; newNode.keys = node.keys; newNode.children = node.children; newNode.children = node.children;
node.numKeys = 1; for (int j = numKeys; j >= index + 1; j--) { children[j + 1] = children[j]; keys[j] = keys[j - 1];
children[index + 1] = newNode; keys[index] = node.keys; numKeys++;
public Node search(int key) { int i = 0; while (i < numKeys && key > keys[i]) { i++;
if (keys[i] == key) { return this;
if (isLeaf()) { return null;
return children[i].search(key);
public void traverse() { for (int i = 0; i < numKeys; i++) { if (!isLeaf()) { children[i].traverse();
System.out.print(keys[i] + " ");
if (!isLeaf()) { children[numKeys].traverse();
public TwoThreeFourTree() { root = new Node();
public Node search(int key) { return root.search(key);
public void insert(int key) { if (root.getNumKeys() == 3) { Node newRoot = new Node(); newRoot.children = root; root = newRoot; newRoot.splitChild(0, root); newRoot.insertNonFull(key); } else { root.insertNonFull(key);
public void traverse() { root.traverse();
public static void main(String[] args) { Tree234<Integer> tree = new Tree234<Integer>();
// Inserção de valores na árvore tree.insert(50); tree.insert(25); tree.insert(75); tree.insert(12); tree.insert(37); tree.insert(62); tree.insert(87); tree.insert(6); tree.insert(18); tree.insert(31); tree.insert(43); tree.insert(56); tree.insert(68); tree.insert(81); tree.insert(93);
// Impressão dos valores na ordem da árvore System.out.println("Valores na ordem da árvore: "); tree.displayTree();
// Busca de valores na árvore int key = 43; Node<Integer> found = tree.find(key); if (found != null) { System.out.println("Valor " + key + " encontrado na árvore."); } else { System.out.println("Valor " + key + " não encontrado na árvore.");
key = 100; found = tree.find(key); if (found != null) { System.out.println("Valor " + key + " encontrado na árvore."); } else { System.out.println("Valor " + key + " não encontrado na árvore.");
// Remoção de valores da árvore key = 75; boolean removed = tree.remove(key); if (removed) { System.out.println("Valor " + key + " removido da árvore."); System.out.println("Valores na ordem da árvore após remoção: "); tree.displayTree(); } else { System.out.println("Valor " + key + " não encontrado na árvore.");
key = 100; removed = tree.remove(key); if (removed) { System.out.println("Valor " + key + " removido da árvore."); System.out.println("Valores na ordem da árvore após remoção: "); tree.displayTree(); } else { System.out.println("Valor " + key + " não encontrado na árvore.");
Ver também Árvore 2-3 Árvore rubro-negra Árvore B
Ligações externas Algorithms In Action, with 2–3–4 Tree animation Animation of a 2–3–4 Tree Java Applet showing a 2–3–4 Tree Left-leaning Red–Black Trees – Princeton University, 2008 Open Data Structures – Section 9.1 – 2–4 Trees
Categoria:Estruturas de dados