Bonjour, Habr!
Il y a six mois, j'ai réfléchi à la façon d'obtenir un élément à partir d'un arbre binaire dans O (log (N)). La réponse est venue assez rapidement - Lazy Propagation. Mais j'étais trop paresseux pour implémenter cela dans le code. Maintenant, nous devons prendre le projet de fin d'études à l'université, donc je fais tout sauf ça. C’est ainsi que je me suis assis pour le mettre en œuvre.
Quelques notes:- L'arbre n'est pas équilibré (jusqu'à présent, car le projet de graduation doit encore être écrit), ce qui fait que l'estimation O (log (N)) est partout amortie pour les données d'entrée aléatoires.
- Je n'ai pas trouvé de structure de données similaire, les collègues et amis à qui j'ai posé la question n'ont pas non plus offert quelque chose de similaire. Si vous connaissez la mise en œuvre d'une telle idée, faites-le moi savoir.
- Dans la classe vertex, on pourrait se passer du champ parent en passant le parent aux méthodes.
Description de l'idéeStockons pour chaque sommet le nombre de sommets qui se trouvent à sa gauche, appelons ce champ au vertex countLefter. Mais ensuite, si nous ajoutons l'élément le plus à gauche à l'arbre, nous devons changer countLefter pour tous les autres sommets, qui peuvent être douloureusement longs et à la racine (oh, ce jeu de mots), ne correspond pas aux principes d'un arbre binaire. Pour éviter cela, saisissons un champ d'ajout pour chaque sommet, dans lequel nous stockons la quantité que nous devons ajouter au champ countLefter pour chaque sommet de sa sous-arborescence, y compris ce sommet lui-même. Ainsi, en ajoutant l'élément le plus à gauche à l'arborescence, il vous suffit de:
- Augmentez countLefter le long du chemin entier jusqu'au point d'insertion du nouveau sommet
- Pour tous les sommets situés à droite de ce qui précède, augmentez ajouter de 1
Il est maintenant logique d'introduire la méthode push (), qui ajoutera add au countLefter du sommet lui-même et de ses deux descendants.
C'est ainsi qu'est née la classe vertex: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 + '}'; } }
Super, vous pouvez maintenant commencer à
construire un arbre!La première chose que nous faisons, aller en haut - nous appelons la méthode push ().
Nous allons supprimer l'élément par suppression à gauche (nous prenons le plus à droite des sommets qui sont à gauche de celui supprimé).
Pour obtenir un élément par index, nous agissons bien évidemment: si index <countLefter du sommet courant, allez à gauche. Si les valeurs sont égales, nous avons trouvé un sommet avec un indice donné. Sinon, nous allons à droite.
La suppression et l'ajout d'un élément, en principe, n'est pas très différent d'un arbre binaire normal, sauf pour changer le countLefter et ajouter des champs. Si nous retournons en haut à gauche après l'ajout / suppression réussi, ces champs devront être modifiés. Si à droite, non.
Voici le code arborescent: 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); } }
→
Ici, le code peut être trouvé sur le github.
Je vais donner quelques résultats de la vitesse de travail. Des tests ont été effectués sur:
Ajout à l'arbre:Donc, en ajoutant un million d'éléments aléatoires dans la plage [0; 1_000):
Environ 100 ms. TreeSet a accompli cette tâche en 130 ms environ.
Ajout d'un million d'éléments aléatoires dans la plage [0; 10_000):
Environ 150 ms. TreeSet a accompli cette tâche en environ 190 ms.
Ajout d'un million d'éléments aléatoires dans la plage [0; 100_000):
Environ 320 ms. TreeSet a accompli cette tâche en 415 ms environ.
Ajout d'un million d'éléments aléatoires dans la plage [0; 1_000_000):
Environ 510 ms. TreeSet a accompli cette tâche en environ 700 ms.
Ajout d'un million d'éléments aléatoires dans la plage [0; 10_000_000):
Environ 590 ms. TreeSet a accompli cette tâche en environ 750 ms.
Suppression maintenantAjoutez au hasard un million de nombres à l'arbre. Ensuite, nous essayons de supprimer un nombre aléatoire un million de fois. Dans les tests, seul le temps de retrait est pris en compte.
La plage d'ajout et de suppression de [0; 10_000_000):
Environ 740 ms. TreeSet a accompli cette tâche en environ 750 ms.
La plage d'ajout et de suppression de [0; 1_000_000):
Environ 600 ms. TreeSet a terminé cette tâche en environ 800 ms (plus que lors du test précédent).
La plage d'ajout et de suppression de [0; 100_000):
Environ 130 ms. TreeSet a accompli cette tâche en environ 160 ms.
La plage d'ajout et de suppression de [0; 10_000):
Environ 45 ms. TreeSet a accompli cette tâche en environ 50 ms.
La plage d'ajout et de suppression de [0; 1_000):
Environ 30 ms. TreeSet a accompli cette tâche en environ 37 ms.
Et enfin, pour le bien de tout a commencé, l'accès par indexTreeSet n'a pas cette fonctionnalité. Je ne donnerai donc les résultats que pour UTree. Encore une fois, nous ajoutons un million d'éléments, puis nous obtenons l'élément à un indice aléatoire de 0 au nombre d'éléments dans l'arbre. Le temps n'est pris en compte que pour l'accès par index.
Plage d'addition [0; 1000): 85 ms
Plage d'addition [0; 10_000): 140 ms
Plage d'addition [0; 100_000): 300 ms
Plage d'addition [0; 1_000_000): 655 ms
J'espère que quelqu'un trouvera mon idée utile, mais peut-être que pour quelqu'un ce sera l'occasion de s'occuper des arbres binaires, si vous ne l'avez pas fait :)
PSJe prévois d'être perplexe avec l'équilibre de l'arbre après le nouvel an. Si je le fais, le lien pour continuer apparaîtra ici.