Á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
editar- 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
editarPara 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.
Exemplo
editarPara 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
editarConsidere 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
editarpublic 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
editarReferê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