Hallo habr
Vor sechs Monaten habe ich darüber nachgedacht, wie man ein Element aus einem Binärbaum in O (log (N)) erhält. Die Antwort kam ziemlich schnell - Lazy Propagation. Aber ich war zu faul, um dies in den Code zu implementieren. Jetzt müssen wir das Abschlussprojekt an der Universität machen, also mache ich alles andere als das. So habe ich es umgesetzt.
Einige Anmerkungen:- Der Baum ist nicht ausgeglichen (da das Diplomprojekt noch geschrieben werden muss), wodurch die Schätzung O (log (N)) für zufällige Eingabedaten überall amortisiert wird.
- Ich habe keine ähnliche Datenstruktur gefunden, Kollegen und Freunde, die ich gefragt habe, haben auch nichts Ähnliches angeboten. Wenn Sie die Umsetzung einer solchen Idee kennen, lassen Sie es mich bitte wissen.
- In der Vertex-Klasse kann auf das übergeordnete Feld verzichtet werden, indem das übergeordnete Feld an die Methoden übergeben wird.
Beschreibung der IdeeSpeichern wir für jeden Eckpunkt die Anzahl der Eckpunkte links davon und rufen wir dieses Feld beim Eckpunkt countLefter auf. Wenn wir jedoch das am weitesten links stehende Element zum Baum hinzufügen, müssen wir countLefter für alle anderen Scheitelpunkte ändern, die schmerzhaft lang sein können und an der Wurzel (oh, dieses Wortspiel) nicht den Prinzipien eines binären Baums entsprechen. Um dies zu vermeiden, geben Sie für jeden Scheitelpunkt ein Feld zum Hinzufügen ein, in dem gespeichert wird, wie viel zum countLefter-Feld für jeden Scheitelpunkt seines Unterbaums hinzugefügt werden muss, einschließlich des Scheitelpunkts selbst. Wenn Sie also das am weitesten links stehende Element zum Baum hinzufügen, müssen Sie nur Folgendes tun:
- Erhöhen Sie countLefter auf dem gesamten Pfad, der zum Einfügepunkt des neuen Scheitelpunkts führt
- Erhöhen Sie add um 1 für alle Scheitelpunkte, die sich rechts oben befinden
Jetzt ist es logisch, die push () -Methode einzuführen, die add zum countLefter des Scheitelpunkts selbst und seiner beiden Nachkommen hinzufügt.
So ist die Vertex-Klasse entstanden: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 + '}'; } }
Toll, jetzt kannst du anfangen
, einen Baum zu bauen!Als erstes gehen wir nach oben - wir nennen die push () -Methode.
Wir löschen das Element durch Löschen von links (wir nehmen den rechten Eckpunkt links vom gelöschten Eckpunkt).
Um ein Element nach Index zu erhalten, verfahren wir ganz offensichtlich: Wenn index <countLefter des aktuellen Scheitelpunkts ist, gehen Sie nach links. Wenn die Werte gleich sind, haben wir einen Scheitelpunkt mit einem bestimmten Index gefunden. Ansonsten gehen wir nach rechts.
Das Löschen und Hinzufügen eines Elements unterscheidet sich im Prinzip nicht wesentlich von einem regulären Binärbaum, mit Ausnahme des Änderns des countLefter und des Hinzufügens von Feldern. Wenn wir nach erfolgreicher Hinzufügung / Entfernung nach links oben zurückkehren, müssen diese Felder geändert werden. Wenn rechts, nein.
Hier ist der Baumcode: 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); } }
→
Hier finden Sie den Code auf dem Github.
Ich werde einige Ergebnisse der Arbeitsgeschwindigkeit geben. Die Tests wurden durchgeführt an:
Hinzufügen zum Baum:Hinzufügen einer Million zufälliger Elemente im Bereich [0; 1_000):
Über 100 ms. TreeSet hat diese Aufgabe in ca. 130 ms erledigt.
Hinzufügen einer Million zufälliger Elemente im Bereich [0; 10_000):
Über 150 ms. TreeSet erledigte diese Aufgabe in ca. 190 ms.
Hinzufügen einer Million zufälliger Elemente im Bereich [0; 100_000):
Über 320 ms. TreeSet hat diese Aufgabe in ca. 415 ms erledigt.
Hinzufügen einer Million zufälliger Elemente im Bereich [0; 1_000_000):
Ungefähr 510 ms. TreeSet erledigte diese Aufgabe in ca. 700 ms.
Hinzufügen einer Million zufälliger Elemente im Bereich [0; 10_000_000):
Ungefähr 590 ms. TreeSet hat diese Aufgabe in ca. 750 ms erledigt.
Entfernung jetztFügen Sie dem Baum nach dem Zufallsprinzip eine Million Zahlen hinzu. Dann versuchen wir, eine Zufallszahl millionenfach zu löschen. Bei Tests wird nur die zum Entfernen benötigte Zeit berücksichtigt.
Der Bereich zum Hinzufügen und Entfernen von [0; 10_000_000):
Ungefähr 740 ms. TreeSet hat diese Aufgabe in ca. 750 ms erledigt.
Der Bereich zum Hinzufügen und Entfernen von [0; 1_000_000):
Über 600 ms. TreeSet hat diese Aufgabe in ca. 800 ms erledigt (mehr als im vorherigen Test).
Der Bereich zum Hinzufügen und Entfernen von [0; 100_000):
Über 130 ms. TreeSet hat diese Aufgabe in ca. 160 ms erledigt.
Der Bereich zum Hinzufügen und Entfernen von [0; 10_000):
Über 45 ms. TreeSet hat diese Aufgabe in ca. 50 ms erledigt.
Der Bereich zum Hinzufügen und Entfernen von [0; 1_000):
Ungefähr 30 ms. TreeSet hat diese Aufgabe in ca. 37 ms erledigt.
Nun, und zu guter Letzt, um alles in Gang zu setzen, greifen Sie über den Index zuTreeSet verfügt nicht über diese Funktionalität. Also werde ich die Ergebnisse nur für UTree geben. Wir addieren erneut eine Million Elemente und erhalten dann das Element mit einem zufälligen Index von 0 bis zur Anzahl der Elemente im Baum. Die Zeit wird nur für den Zugriff per Index berücksichtigt.
Additionsbereich [0; 1000): 85 ms
Additionsbereich [0; 10_000): 140 ms
Additionsbereich [0; 100_000): 300 ms
Additionsbereich [0; 1_000_000): 655 ms
Ich hoffe, jemand findet meine Idee nützlich, aber vielleicht ist dies für jemanden eine Gelegenheit, sich mit binären Bäumen zu befassen, wenn Sie dies nicht getan haben :)
PSIch habe vor, mich nach dem Neujahr mit dem Auswuchten des Baumes zu beschäftigen. In diesem Fall wird der Link zum Fortfahren hier angezeigt.