Ich bin auf die folgende Art von Problem gestoßen. Es ist notwendig, einen Datenspeichercontainer zu implementieren, der die folgende Funktionalität bietet:
- neues Element einfügen
- Element anhand der Seriennummer entfernen
- Element anhand der Ordnungszahl ermitteln
- Die Daten werden in sortierter Form gespeichert
Daten werden ständig hinzugefügt und entfernt, die Struktur muss eine schnelle Betriebsgeschwindigkeit gewährleisten. Zuerst habe ich versucht, so etwas mit Standardcontainern von zu implementieren std. Dieser Weg war nicht von Erfolg gekrönt und es kam die Einsicht, dass ich selbst etwas umsetzen musste. Das Einzige, was mir in den Sinn kam, war die Verwendung eines binären Suchbaums. Denn es erfüllt die Anforderungen an schnelles Einfügen, Löschen und sortiertes Speichern von Daten. Jetzt müssen Sie nur noch herausfinden, wie Sie alle Elemente indizieren und die Indizes neu berechnen, wenn sich der Baum ändert.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Der Artikel enthält mehr Bilder und Theorie als Code. Der Code kann unter dem untenstehenden Link eingesehen werden.
Gewicht
Um dies zu erreichen, wurde der Baum leicht modifiziert und zusätzliche Informationen hinzugefügt Gewicht Knoten. Das Knotengewicht beträgt Anzahl der Nachkommen dieses Knotens + 1 (Gewicht eines einzelnen Elements).
Funktion zum Ermitteln des Knotengewichts:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Das Gewicht des Blattes ist entsprechend gleich 0.
Kommen wir als Nächstes zu einer visuellen Darstellung eines Beispiels eines solchen Baums. Schwarz der Knotenschlüssel wird farbig dargestellt (der Wert wird nicht angezeigt, da dies nicht notwendig ist), rot — Knotengewicht, grün — Knotenindex.
Wenn unser Baum leer ist, beträgt sein Gewicht 0. Fügen wir ihm ein Wurzelelement hinzu:
Das Gewicht des Baums wird 1, das Gewicht des Wurzelelements wird 1. Das Gewicht des Wurzelelements ist das Gewicht des Baums.
Fügen wir noch ein paar Elemente hinzu:
Jedes Mal, wenn ein neues Element hinzugefügt wird, gehen wir die Knoten nach unten und erhöhen den Gewichtszähler jedes übergebenen Knotens. Wenn ein neuer Knoten erstellt wird, wird ihm eine Gewichtung zugewiesen 1. Wenn ein Knoten mit einem solchen Schlüssel bereits existiert, überschreiben wir den Wert und gehen zurück zur Wurzel, wobei wir die Änderungen in den Gewichten aller Knoten, die wir passiert haben, rückgängig machen.
Wenn ein Knoten entfernt wird, gehen wir nach unten und dekrementieren die Gewichte der übergebenen Knoten.
Indizes
Kommen wir nun zur Indizierung von Knoten. Knoten speichern ihren Index nicht explizit, er wird basierend auf der Gewichtung der Knoten berechnet. Wenn sie ihren Index speichern würden, wäre dieser erforderlich O (n) Zeit, die Indizes aller Knoten nach jeder Änderung im Baum zu aktualisieren.
Kommen wir zur visuellen Darstellung. Unser Baum ist leer. Fügen wir ihm den ersten Knoten hinzu:
Der erste Knoten hat einen Index 0, und jetzt sind 2 Fälle möglich. Im ersten Fall ändert sich der Index des Wurzelelements, im zweiten nicht.
An der Wurzel wiegt der linke Teilbaum 1.
Zweiter Fall:
Der Index der Wurzel änderte sich nicht, da das Gewicht ihres linken Teilbaums 0 blieb.
Der Index eines Knotens wird als Gewicht seines linken Teilbaums + der vom übergeordneten Knoten übergebenen Zahl berechnet. Was ist diese Zahl? Dies ist der Indexzähler, der zunächst gleich ist 0, Weil Die Wurzel hat kein übergeordnetes Element. Dann hängt alles davon ab, wohin wir zum linken oder rechten Kind gehen. Wenn nach links, wird dem Zähler nichts hinzugefügt. Wenn wir den Index des aktuellen Knotens zum rechten hinzufügen.
Beispielsweise, wie der Index eines Elements mit Schlüssel 8 (dem rechten untergeordneten Element der Wurzel) berechnet wird. Dies ist „Wurzelindex“ + „Gewicht des linken Teilbaums des Knotens mit Schlüssel 8“ + „1“ == 3 + 2 + 1 == 6
Der Index des Elements mit Schlüssel 6 ist „Root Index“ + 1 == 3 + 1 == 4
Dementsprechend dauert es einige Zeit, ein Element anhand des Index abzurufen und zu löschen O (log n), denn um das gewünschte Element zu erhalten, müssen wir es zuerst finden (von der Wurzel zu diesem Element hinuntergehen).
Tiefe
Anhand des Gewichts können Sie auch die Tiefe des Baumes berechnen. Notwendig zum Ausbalancieren.
Dazu muss das Gewicht des aktuellen Knotens auf die erste Zahl hoch 2 gerundet werden, die größer oder gleich dem angegebenen Gewicht ist, und daraus der binäre Logarithmus gebildet werden. Dies gibt uns die Tiefe des Baumes, vorausgesetzt, er ist ausgewogen. Der Baum wird nach dem Einfügen eines neuen Elements ausgeglichen. Ich werde keine Theorie darüber abgeben, wie man Bäume ausbalanciert. Die Quellcodes bieten eine ausgleichende Funktion.
Code zur Umrechnung von Gewicht in Tiefe.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
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));
}Ergebnisse
- Das Einfügen eines neuen Elements erfolgt in O (log n)
- Das Löschen eines Elements anhand der Seriennummer erfolgt in O (log n)
- Das Erhalten eines Elements anhand der Seriennummer erfolgt in O (log n)
Geschwindigkeit O (log n) Wir zahlen dafür, dass alle Daten sortiert gespeichert werden.
Ich weiß nicht, wo eine solche Struktur nützlich sein könnte. Nur ein Rätsel, 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 Betriebsgeschwindigkeit. Der Baum füllt sich 1000000 Elemente. Und es gibt ein sequentielles Löschen, Einfügen und Abrufen von Elementen 1000000 einmal. Also 3000000 Operationen. Das Ergebnis fiel recht gut aus ~ 8 Sekunden.
Source: habr.com