Olá Habr!
Seis meses atrás, pensei em como obter um elemento de uma árvore binária em O (log (N)). A resposta veio muito rapidamente - Propagação Preguiçosa. Mas eu estava com preguiça de implementar isso no código. Agora precisamos fazer o projeto de graduação na universidade, então faço tudo menos isso. Foi assim que me sentei para implementá-lo.
Algumas notas:- A árvore não está equilibrada (até agora, porque o projeto de diploma ainda precisa ser gravado), como resultado do qual a estimativa O (log (N)) é em todo lugar amortizada para dados de entrada aleatórios.
- Não encontrei uma estrutura de dados semelhante, colegas e amigos a quem pedi, também não ofereceram nada semelhante. Se você conhece a implementação dessa ideia, entre em contato.
- Na classe de vértice, pode-se dispensar o campo pai passando o pai aos métodos.
Descrição da ideiaVamos armazenar para cada vértice o número de vértices que estão à esquerda dele, vamos chamar esse campo no vértice countLefter. Mas, se adicionarmos o elemento mais à esquerda à árvore, teremos que mudar countLefter para todos os outros vértices, que podem ser dolorosamente longos e na raiz (oh, esse trocadilho) não se encaixa nos princípios de uma árvore binária. Para evitar isso, vamos inserir um campo de adição para cada vértice, no qual armazenaremos quanto precisamos adicionar ao campo countLefter para cada vértice de sua subárvore, incluindo esse próprio vértice. Assim, adicionando o elemento mais à esquerda na árvore, você só precisa:
- Aumente countLefter ao longo de todo o caminho para o ponto de inserção do novo vértice
- Para todos os vértices que estão à direita do acima, aumente add 1
Agora é lógico introduzir o método push (), que adicionará add ao countLefter do próprio vértice e a ambos os seus descendentes.
Foi assim que surgiu a classe de vértice:public class UNode { UNode parent; int key; int countLefter; int add; UNode left; UNode right; public UNode() { } public UNode(UNode parent, int key, int countLefter, int add, UNode left, UNode right) { this.parent = parent; this.key = key; this.countLefter = countLefter; this.add = add; this.left = left; this.right = right; } public void push() { countLefter += add; if (left != null) left.add += add; if (right != null) right.add += add; add = 0; } @Override public String toString() { return "Node{" + "key=" + key + ", countLefter=" + countLefter + '}'; } }
Ótimo, agora você pode começar a
construir uma árvore!A primeira coisa que fazemos, indo para o topo - chamamos o método push ().
Excluiremos o elemento por exclusão à esquerda (pegamos o mais à direita dos vértices que estão à esquerda do que foi excluído).
Para obter um elemento pelo índice, agimos de maneira bastante óbvia: se index <countLefter do vértice atual, vá para a esquerda. Se os valores forem iguais, encontramos um vértice com um determinado índice. Caso contrário, vamos para a direita.
Excluir e adicionar um elemento, em princípio, não é muito diferente de uma árvore binária comum, exceto para alterar os campos countLefter e add. Se retornarmos ao topo à esquerda após a adição / remoção bem-sucedida, esses campos precisarão ser alterados. Se estiver à direita, não.
Aqui está o código da árvore: import java.util.LinkedList; public class UTree { private UNode root; private int size; public UTree() { } public int size() { return size; } public int get(int index) { return get(index, root); } public boolean add(int key) { if (root == null) { root = new UNode(null, key, 0, 0, null, null); size++; return true; } boolean res = add(key, root); if (res) size++; return res; } public boolean remove(int key) { if (root == null) return false; if (key == this.root.key) { root.push(); removeRoot(); size--; return true; } boolean res = remove(key, root); if (res) size--; return res; } private int get(int index, UNode root) { root.push(); if (index == root.countLefter) return root.key; if (index < root.countLefter) return get(index, root.left); return get(index, root.right); } private boolean add(int key, UNode root) { if (key == root.key) return false; root.push(); if (key < root.key) if (root.left != null) { boolean res = add(key, root.left); if (res) { root.countLefter++; if (root.right != null) root.right.add++; } return res; } else { root.left = new UNode(root, key, root.countLefter, 0, null, null); root.countLefter++; if (root.right != null) root.right.add++; return true; } if (root.right != null) return add(key, root.right); else { root.right = new UNode(root, key, root.countLefter + 1, 0, null, null); return true; } } public boolean removeByIndex(int index) { if(this.root == null) return false; root.push(); if (index == this.root.countLefter) { removeRoot(); return true; } boolean res = removeByIndex(index, root); if (res) size--; return res; } private boolean removeByIndex(int index, UNode root) { if (root == null) return false; root.push(); if (index == root.countLefter) return removeNode(root); if (index < root.countLefter) { boolean res = removeByIndex(index, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return removeByIndex(index, root.right); } private boolean removeNode(UNode root) { if (root.left == root.right) { if (root.parent.left == root) root.parent.left = null; else root.parent.right = null; return true; } if (root.left == null) { if (root.parent.left == root) { root.parent.left = root.right; root.right.add--; } else { root.parent.right = root.right; root.right.add--; } root.right.parent = root.parent; return true; } if (root.right == null) { if (root.parent.left == root) root.parent.left = root.left; else root.parent.right = root.left; root.left.parent = root.parent; return true; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; return true; } private boolean remove(int key, UNode root) { if (root == null) return false; root.push(); if (key == root.key) return removeNode(root); if (key < root.key) { boolean res = remove(key, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return remove(key, root.right); } private void removeRoot() { if (root.left == root.right) { root = null; return; } if (root.left == null) { root = root.right; root.add--; return; } if (root.right == null) { root = root.left; return; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; } private static void cut(UNode node) { if (node.parent.left == node) node.parent.left = node.left; else node.parent.right = node.left; if (node.left != null) node.left.parent = node.parent; } private UNode getRight(UNode root) { root.push(); if (root.right == null) return root; return getRight(root.right); } public void printTree() { printTree(root); } private void printTree(UNode root) { if (root == null) return; root.push(); printTree(root.left); System.out.println(root); printTree(root.right); } public LinkedList<UNode> getAll(){ LinkedList<UNode> res = new LinkedList<>(); getAll(root, res); return res; } private void getAll(UNode root, LinkedList<UNode> res){ if (root == null) return; root.push(); getAll(root.left, res); res.add(root); getAll(root.right, res); } }
→
Aqui o código pode ser encontrado no github.
Vou dar alguns resultados da velocidade do trabalho. Os testes foram realizados em:
Adicionando à árvore:Então, adicionando um milhão de elementos aleatórios no intervalo [0; 1_000):
Cerca de 100 ms. O TreeSet executou essa tarefa em aproximadamente 130 ms.
Adicionando um milhão de elementos aleatórios no intervalo [0; 10_000):
Cerca de 150 ms. O TreeSet executou essa tarefa em cerca de 190 ms.
Adicionando um milhão de elementos aleatórios no intervalo [0; 100_000):
Cerca de 320 ms. O TreeSet executou esta tarefa em aproximadamente 415 ms.
Adicionando um milhão de elementos aleatórios no intervalo [0; 1_000_000):
Cerca de 510 ms. O TreeSet realizou essa tarefa em aproximadamente 700 ms.
Adicionando um milhão de elementos aleatórios no intervalo [0; 10_000_000):
Cerca de 590 ms. O TreeSet realizou essa tarefa em aproximadamente 750 ms.
Remoção agoraAdicione aleatoriamente um milhão de números à árvore. Em seguida, tentamos excluir um número aleatório um milhão de vezes. Nos testes, apenas o tempo necessário para remover é levado em consideração.
O intervalo de adição e remoção de [0; 10_000_000):
Cerca de 740 ms. O TreeSet realizou essa tarefa em aproximadamente 750 ms.
O intervalo de adição e remoção de [0; 1_000_000):
Cerca de 600 ms. O TreeSet concluiu esta tarefa em aproximadamente 800 ms (mais do que no teste anterior).
O intervalo de adição e remoção de [0; 100_000):
Cerca de 130 ms. O TreeSet realizou essa tarefa em cerca de 160 ms.
O intervalo de adição e remoção de [0; 10_000):
Cerca de 45 ms. O TreeSet realizou essa tarefa em cerca de 50 ms.
O intervalo de adição e remoção de [0; 1_000):
Cerca de 30 ms. O TreeSet executou esta tarefa em aproximadamente 37 ms.
Bem, e finalmente, para o qual tudo foi iniciado, acesso por índiceTreeSet não possui essa funcionalidade. Então, eu darei os resultados apenas para o UTree. Novamente, adicionamos um milhão de elementos e obtemos o elemento em um índice aleatório de 0 ao número de elementos na árvore. O tempo é levado em consideração apenas para o acesso pelo índice.
Faixa de adição [0; 1000): 85 ms
Faixa de adição [0; 10_000): 140 ms
Faixa de adição [0; 100_000): 300 ms
Faixa de adição [0; 1_000_000): 655 ms
Espero que alguém ache minha ideia útil, mas talvez para alguém seja uma ocasião para lidar com árvores binárias, se você ainda não o fez :)
PSPlanejo ficar intrigado com o equilíbrio da árvore após o Ano Novo. Se sim, o link para continuar aparecerá aqui.