Indexierbarer binärer Baum

Ich habe eine Aufgabe dieser Art bekommen. Es ist notwendig, einen Datenspeicherkontainer zu implementieren, der die folgenden Funktionen bietet:

• ein neues Element einfügen
• ein Element nach seiner Reihenfolge entfernen
• ein Element nach seiner Reihenfolge abrufen
• Die Daten werden in sortierter Form gespeichert

Daten werden ständig hinzugefügt und entfernt, die Struktur muss eine schnelle Arbeitsgeschwindigkeit gewährleisten. Zuerst versuchte ich, so etwas mit den Standardcontainern aus stdzu realisieren. Dieser Weg war nicht erfolgreich, und mir wurde klar, dass ich etwas selbst implementieren musste. Das Einzige, was mir in den Sinn kam, war die Verwendung eines binären Suchbaums. Da dieser die Anforderungen an schnelles Einfügen, Löschen und die Speicherung der Daten in sortierter Form erfüllt. Es blieb nur zu überlegen, wie man alle Elemente indizieren und die Indizes aktualisieren kann, wenn sich der Baum ändert.

struct node_s {    
    data_t data;

    uint64_t weight; // Gewicht des Knotens

    node_t *left;
    node_t *right;

    node_t *parent;
};

Im Artikel wird es mehr Bilder und Theorie als Code geben. Den Code können Sie über den Link unten einsehen.

Gewicht

Dafür wurde der Baum einer kleinen Modifikation unterzogen, wobei zusätzliche Informationen über das Gewicht des Knotens hinzugefügt wurden. Das Gewicht eines Knotens ist die Anzahl der Nachkommen dieses Knotens + 1 (das Gewicht eines einzelnen Elements).

Funktion zur Ermittlung des Gewichts eines Knotens:

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

    return 0;
}

Ein Blatt hat entsprechend ein Gewicht von 0.

Als Nächstes gehen wir zu einer anschaulichen Darstellung eines solchen Baumes über. In Schwarz wird der Schlüssel des Knotens angezeigt (der Wert wird nicht angezeigt, da dies nicht notwendig ist), in Rot - das Gewicht des Knotens, in Grün - der Index des Knotens.

Wenn der Baum leer ist, beträgt sein Gewicht 0. Fügen wir ihm das Wurzelelement hinzu:

Das Gewicht des Baumes wird 1, das Gewicht des Wurzelelements beträgt 1. Das Gewicht des Wurzelelements ist das Gewicht des Baumes.

Fügen wir noch einige Elemente hinzu:

Jedes Mal, wenn ein neues Element hinzugefügt wird, gehen wir durch die Knoten nach unten und erhöhen den Gewichtszähler jedes durchlaufenen Knotens. Beim Erstellen eines neuen Knotens wird ihm ein Gewicht zugewiesen. 1Wenn ein Knoten mit diesem Schlüssel bereits existiert, wird der Wert überschrieben, und wir gehen rückwärts bis zur Wurzel und machen die Gewichtänderungen aller Knoten, die wir durchlaufen haben, rückgängig.
Wenn ein Knoten gelöscht wird, gehen wir nach unten und dekrementieren die Gewichte der durchlaufenen Knoten.

Indizes

Jetzt kommen wir dazu, wie man die Knoten indiziert. Knoten speichern ihren Index nicht direkt; dieser wird auf Basis des Gewichts der Knoten berechnet. Wenn sie ihren Index speichern würden, wäre das nötig, O(n) an Zeit, um die Indizes aller Knoten nach jeder Änderung des Baums zu aktualisieren.
Lassen Sie uns zu einer anschaulichen Darstellung übergehen. Unser Baum ist leer, fügen wir den ersten Knoten hinzu:

Der erste Knoten hat den Index 0, und jetzt sind zwei Fälle möglich. Im ersten Fall ändert sich der Index des Wurzelelements, im zweiten Fall bleibt er unverändert.

Das linke Teilbaum des Wurzelknotens wiegt 1.

Zweiter Fall:

Der Index des Wurzelknotens hat sich nicht geändert, da das Gewicht seines linken Teilbaums 0 geblieben ist.

Wie der Index eines Knotens berechnet wird, ist das Gewicht seines linken Teilbaums + die von dem Elternteil übergebene Zahl. Was ist das für eine Zahl?, Es ist der Zähler der Indizes, der anfangs gleich 0, da der Wurzelknoten keinen Elternteil hat. Danach hängt alles davon ab, ob wir zum linken Kind oder zum rechten Kind hinabsteigen. Wenn wir zum linken Kinden gehen, wird nichts zum Zähler hinzugefügt. Wenn wir zum rechten gehen, addieren wir den Index des aktuellen Knotens.

Zum Beispiel, wie der Index des Elements mit dem Schlüssel 8 (rechtes Kind des Wurzelknotens) berechnet wird. Das ist "Der Index des Wurzelknotens" + "das Gewicht des linken Teilbaums des Knotens mit dem Schlüssel 8" + "1" == 3 + 2 + 1 == 6
Der Index des Elements mit dem Schlüssel 6 wird sein: "Der Index des Wurzelknotens" + 1 == 3 + 1 == 4

Daher benötigt man, um ein Element nach Index zu bekommen oder zu entfernen, Zeit O(log n), da wir zuerst das benötigte Element finden müssen (vom Wurzelknoten bis zu diesem Element hinabsteigen).

Tiefe

Basierend auf dem Gewicht kann auch die Tiefe des Baumes berechnet werden. Dies ist notwendig für die Balance.
Hierfür muss das Gewicht des aktuellen Knotens auf die nächste Potenz von 2 aufgerundet werden, die größer oder gleich dem gegebenen Gewicht ist, und der Binärlogarithmus davon genommen werden. So erhalten wir die Tiefe des Baumes, vorausgesetzt, er ist balanciert. Der Baum wird nach dem Einfügen eines neuen Elements balanciert. Die Theorie, wie man Bäume balanciert, werde ich nicht erläutern. Im Quellcode ist eine Balancierungsfunktion dargestellt.

Code zur Anpassung des Gewichts an die 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 geschieht in O(log n)
• Das Entfernen eines Elements nach fortlaufender Nummer geschieht in O(log n)
• Das Abrufen eines Elements nach fortlaufender Nummer geschieht in O(log n)

Geschwindigkeit O(log n) zahlen wir dafür, dass alle Daten in sortierter Form gespeichert werden.

Wo eine solche Struktur nützlich sein könnte, weiß ich nicht. Es ist einfach eine Übung, um noch einmal zu verstehen, wie Bäume funktionieren. Danke für Ihre Aufmerksamkeit.

Links

• Quellcode des Baumes

Das Projekt enthält Testdaten zur Überprüfung der Arbeitsgeschwindigkeit. Der Baum wird mit 1000000 Elementen gefüllt. Es erfolgen nacheinander Lösch-, Einfüge- und Abrufoperationen von Elementen. 1000000 Mal. Das heißt, 3000000 Operationen. Das Ergebnis erwies sich als durchaus akzeptabel ~ 8 Sekunden.

Quelle: habr.com