Ich habe folgendes Problem. Es ist erforderlich, einen Datenspeichercontainer zu implementieren, der die folgenden Funktionen bietet:
- Neues Element einfügen
- Artikel nach Seriennummer löschen
- Holen Sie sich den Artikel über die Seriennummer
- Daten werden in sortierter Form gespeichert
Daten werden ständig hinzugefügt und gelöscht, die Struktur sollte eine schnelle Geschwindigkeit bieten. Zuerst habe ich versucht, so etwas mit Standardcontainern von std umzusetzen. Dieser Weg war erfolglos und es stellte sich heraus, dass Sie selbst etwas umsetzen müssen. Das einzige, was mir in den Sinn kam, war die Verwendung eines binären Suchbaums. Da es die Anforderung des schnellen Einfügens, Löschens und Speicherns von Daten in sortierter Form erfüllt. Es bleibt nur herauszufinden, wie alle Elemente indiziert und die Indizes neu berechnet werden, wenn sich der Baum ändert.
struct node_s { data_t data; uint64_t weight;
Der Artikel wird mehr Bilder und Theorie als Code enthalten. Der Code kann unter dem folgenden Link eingesehen werden.
Gewicht
Zu diesem Zweck wurde der Baum leicht modifiziert und es wurden zusätzliche Informationen zum Gewicht des Knotens hinzugefügt. Das Gewicht eines Knotens ist die Anzahl der Nachkommen dieses Knotens + 1 (Gewicht eines einzelnen Elements).
Die Funktion zum Erhalten des Gewichts des Knotens:
uint64_t bntree::get_child_weight(node_t *node) { if (node) { return node->weight; } return 0; }
Das Blatt hat jeweils ein Gewicht von 0 .
Als nächstes wenden wir uns einer visuellen Darstellung eines Beispiels eines solchen Baums zu. Der Knotenschlüssel wird in schwarz angezeigt (der Wert wird nicht angezeigt, da dies nicht erforderlich ist), in rot - das Gewicht des Knotens, in grün - der Index des Knotens.
Wenn der Baum leer ist, ist sein Gewicht 0. Fügen Sie das Wurzelelement hinzu:
Das Gewicht des Baumes wird 1, das Gewicht des Wurzelelements 1. Das Gewicht des Wurzelelements ist das Gewicht des Baumes.
Fügen Sie ein paar weitere Elemente hinzu:
Jedes Mal, wenn ein neues Element hinzugefügt wird, gehen wir die Knoten nach unten und erhöhen den Gewichtszähler für jeden übergebenen Knoten. Wenn Sie einen neuen Knoten erstellen, wird er auf Gewicht 1 gesetzt . Wenn ein Knoten mit einem solchen Schlüssel bereits vorhanden ist, schreiben Sie den Wert neu und kehren Sie zum Stammverzeichnis zurück, um Änderungen in der Gewichtung aller von uns übergebenen Knoten rückgängig zu machen.
Wenn der Knoten entfernt wird, verringern wir die Gewichte der übergebenen Knoten.
Indizes
Fahren wir nun mit der Indizierung der Knoten fort. Die Knoten speichern ihren Index nicht explizit, er wird basierend auf dem Gewicht der Knoten berechnet. Wenn sie ihren Index speichern würden, wäre eine O (n) -Zeit erforderlich, um die Indizes aller Knoten nach jeder Änderung des Baums zu aktualisieren.
Gehen wir zu einer visuellen Darstellung über. Unser Baum ist leer, füge den ersten Knoten hinzu:
Der erste Knoten hat den Index 0 , und jetzt sind 2 Fälle möglich. Im ersten Fall ändert sich der Index des Stammelements, im zweiten Fall nicht.
An der Wurzel wiegt der linke Teilbaum 1.
Zweiter Fall:
Der Stammindex hat sich nicht geändert, da das Gewicht seines linken Teilbaums 0 bleibt.
Wenn der Knotenindex berücksichtigt wird, ist dies das Gewicht des linken Unterbaums + die vom übergeordneten Knoten übergebene Zahl. Was ist diese Zahl? Dies ist ein Indexzähler, anfangs ist es 0 , weil Die Wurzel hat keine Eltern. Dann kommt es darauf an, wohin wir zum linken oder zum rechten Kind gehen. Wenn nach links, dann wird nichts zum Zähler hinzugefügt. Wenn rechts, dann füge den Index des aktuellen Knotens hinzu.
Zum Beispiel, wie man den Index eines Elements mit dem Schlüssel 8 (dem rechten Kind der Wurzel) berechnet. Dies ist das "Root Index" + "Gewicht des linken Teilbaums des Knotens mit der Taste 8" + "1" == 3 + 2 + 1 == 6
Der Index des Elements mit der Taste 6 lautet "Root Index" + 1 == 3 + 1 == 4
Dementsprechend würde es O (log n) dauern, ein Element über den Index abzurufen und zu entfernen, da wir es zuerst finden müssen, um das Element abzurufen (vom Stamm zu diesem Element).
Tiefe
Basierend auf dem Gewicht können Sie auch die Tiefe des Baums berechnen. Notwendig zum Auswuchten.
Dazu muss das Gewicht des aktuellen Knotens auf die erste Zahl in Grad 2 gerundet werden, die größer oder gleich dem angegebenen Gewicht ist, und der binäre Logarithmus daraus abgeleitet werden. So erhalten wir die Tiefe des Baumes, sofern dieser ausgeglichen ist. Der Baum wird nach dem Einfügen eines neuen Elements ausgeglichen. Die Theorie über das Gleichgewicht der Bäume wird nicht führen. Der Quellcode bietet eine Ausgleichsfunktion.
Code, um Gewicht in die Tiefe zu bringen.
uint64_t bntree::cpl2(uint64_t x) { x = x - 1; x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return x + 1; } long bntree::ilog2(long d) { int result; std::frexp(d, &result); return result - 1; } uint64_t bntree::weight_to_depth(node_t *p) { if (p == NULL) { return 0; } if (p->weight == 1) { return 1; } else if (p->weight == 2) { return 2; } return this->ilog2(this->cpl2(p->weight)); }
Zusammenfassung
- das Einfügen eines neuen Elements erfolgt in O (log n)
- Elementlöschung nach Sequenznummer erfolgt in O (log n)
- Das Abrufen eines Elements anhand seiner Seriennummer erfolgt in O (log n).
Mit der Geschwindigkeit von O (log n) bezahlen wir dafür, dass alle Daten sortiert gespeichert sind.
Wo eine solche Struktur nützlich sein kann, weiß ich nicht. Nur eine Aufgabe, um noch einmal zu verstehen, wie Bäume funktionieren. Vielen Dank für Ihre Aufmerksamkeit.
Referenzen
Das Projekt enthält Testdaten zur Überprüfung der Arbeitsgeschwindigkeit. Der Baum ist mit 1.000.000 Elementen gefüllt. Und es erfolgt eine sequentielle Löschung, Einfügung und 1.000.000- fache Entgegennahme von Elementen. Das sind 3.000.000 Operationen. Das Ergebnis war ziemlich gut ~ 8 Sekunden.