Indizierter Binärbaum

Ich bin auf ein Problem der folgenden Art gestoßen. Es ist notwendig, einen Datenspeichercontainer zu implementieren, der die folgende Funktionalität bietet:

• neues Element einfügen
• Element nach Ordnungszahl löschen
• Element nach Ordnungszahl abrufen
• Daten werden sortiert gespeichert

Da ständig Daten hinzugefügt und entfernt werden, muss die Struktur eine schnelle Betriebsgeschwindigkeit gewährleisten. Zuerst habe ich versucht, so etwas mit Standardcontainern von std. Dieser Weg war nicht erfolgreich und es kam zu der 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 Anforderung des schnellen Einfügens, Löschens und Speicherns von Daten in sortierter Form. Jetzt muss nur noch herausgefunden werden, wie alle Elemente indiziert und die Indizes neu berechnet werden, 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 folgenden Link eingesehen werden.

Gewicht

Zu diesem Zweck wurde der Baum leicht modifiziert und zusätzliche Informationen hinzugefügt über Gewicht Knoten. Das Gewicht des Knotens beträgt Anzahl der Nachkommen dieses Knotens + 1 (Gewicht eines einzelnen Elements).

Funktion zum Abrufen des Gewichts eines Knotens:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Das Gewicht des Blattes ist dementsprechend gleich 0.

Als Nächstes werden wir mit der visuellen Darstellung eines Beispiels eines solchen Baums fortfahren. Schwarz die Farbe des Knotenschlüssels wird darin angezeigt (der Wert wird nicht angezeigt, da er nicht benötigt wird), rot — Gewicht des Knotens, grün — Knotenindex.

Wenn unser Baum leer ist, beträgt sein Gewicht 0. Fügen wir ihm ein Stammelement hinzu:

Das Gewicht des Baums wird 1, das Gewicht des Wurzelelements ist 1. Das Gewicht des Wurzelelements ist das Gewicht des Baums.

Fügen wir noch ein paar weitere Elemente hinzu:

Jedes Mal, wenn ein neues Element hinzugefügt wird, gehen wir die Knoten hinunter und erhöhen den Gewichtszähler jedes durchlaufenen Knotens. Wenn ein neuer Knoten erstellt wird, wird ihm ein Gewicht zugewiesen. 1. Wenn bereits ein Knoten mit einem solchen Schlüssel vorhanden ist, überschreiben wir den Wert und gehen zurück zur Wurzel nach oben, wobei wir die Änderungen in den Gewichten aller Knoten, die wir passiert haben, rückgängig machen.
Wenn ein Knoten gelöscht wird, gehen wir nach unten und verringern die Gewichte der übergebenen Knoten.

Indizes

Fahren wir nun mit der Indizierung von Knoten fort. Knoten speichern ihren Index nicht explizit, er wird basierend auf dem Gewicht der Knoten berechnet. Wenn sie ihren Index beibehalten würden, wäre dies erforderlich O (n) Zeit, die Indizes aller Knoten nach jeder Änderung im Baum zu aktualisieren.
Kommen wir nun zu einer visuellen Darstellung. Unser Baum ist leer, fügen wir ihm den 1. Knoten hinzu:

Der erste Knoten hat einen Index 0, und jetzt gibt es zwei mögliche Fälle. Im ersten Fall ändert sich der Index des Stammelements, im zweiten Fall bleibt er unverändert.

An der Wurzel hat der linke Teilbaum das Gewicht 1.

Zweiter Fall:

Der Stammindex hat sich nicht geändert, da das Gewicht seines linken Teilbaums 0 bleibt.

Der Index eines Knotens wird als Gewicht seines linken Teilbaums + der vom übergeordneten Knoten übergebenen Zahl berechnet. Was ist das für eine Zahl? Es ist ein Indexzähler, anfänglich ist es gleich 0, weil die Wurzel keinen übergeordneten Knoten hat. Dann hängt alles davon ab, wo wir zum linken oder rechten Kind hinuntergehen. Wenn nach links, wird dem Zähler nichts hinzugefügt. Wenn nach rechts, dann addieren Sie den Index des aktuellen Knotens.

Wie wird beispielsweise der Index eines Elements mit Schlüssel 8 (das rechte Kind der Wurzel) berechnet? Dies ist "Wurzelindex" + "Gewicht des linken Teilbaums des Knotens mit Schlüssel 8" + "1" == 3 + 2 + 1 == 6
Der Index des Elements mit dem Schlüssel 6 ist "Root Index" + 1 == 3 + 1 == 4

Dementsprechend dauert es Zeit, ein Element nach Index zu erhalten oder 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 lässt sich 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 genommen werden. Auf diese Weise erhalten wir die Tiefe des Baums, vorausgesetzt, er ist ausgeglichen. Nach dem Einfügen eines neuen Elements ist der Baum ausgeglichen. Ich werde keine Theorie darüber aufstellen, wie man Bäume im Gleichgewicht hält. Der Quellcode bietet eine Ausgleichsfunktion.

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 nach der Ordnungszahl erfolgt O (log n)
• Das Erhalten eines Elements anhand seiner 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 Problem, um noch einmal zu verstehen, wie Bäume funktionieren. Vielen Dank für Ihre Aufmerksamkeit.

Referenzen

• Tree-Quellcode

Das Projekt enthält Testdaten zur Überprüfung der Betriebsgeschwindigkeit. Der Baum füllt sich 1000000 Elemente. Und es erfolgt ein sequentielles Löschen, Einfügen und Abrufen von Elementen. 1000000 einmal. Das heißt 3000000 Operationen. Das Ergebnis war ziemlich gut: ~ 8 Sekunden.

Source: habr.com