Á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.[carece de fontes?] 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;[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
- 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.[3][4]
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).[5]
Exemplo de código fonte
public class TwoThreeFourTree { private Node root; private class Node { private int[] keys = new int[3]; private Node[] children = new Node[4]; 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[0] == 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[0] = node.keys[2]; newNode.children[0] = node.children[2]; newNode.children[1] = node.children[3]; 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[1]; 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[0] = 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
Referências
- ↑ 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
- ↑ «Left-Leaning Red-Black Trees» (PDF). Left-Leaning Red-Black Trees
- ↑ Ford, William; Topp, William (2002), Data Structures with C++ Using STL, ISBN 0-13-085850-1 2nd ed. , New Jersey: Prentice Hall
- ↑ Goodrich, Michael T; Tamassia, Roberto; Mount, David M (2002), Data Structures and Algorithms in C++, ISBN 0-471-20208-8, Wiley
- ↑ «(2,4) Trees» (PDF). CS251: Data Structures Lecture Notes
Ligações externas
- Algorithms In Action, with 2–3–4 Tree animation[ligação inativa]
- 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