Einfügen

Lektion 9 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

insert beginnt wie ein gewöhnliches Einfügen in einen binären Suchbaum: Gehen Sie nach unten, vergleichen Sie die Werte, gehen Sie nach links oder rechts und platzieren Sie den neuen Knoten dort, wo ein Null-Slot gefunden wird (Duplikate ignorieren). Der AVL-Teil geschieht auf dem Rückweg nach oben: Nach dem Platzieren des Knotens berechnet jeder Vorfahre auf dem Pfad seine height neu und prüft seinen Balance-Faktor.

Wenn ein Knoten unbalanciert wird, entscheiden die schwere Seite und die Position, an der der neue Wert gelandet ist, welcher der vier Fälle zutrifft: left-left und right-right erfordern eine einfache Rotation, während left-right und right-left zwei erfordern, eine innere Rotation, um den Zickzack zu begradigen, gefolgt von der äußeren.

Aufgabe

Mittel

Schreiben Sie eine Methode insert(value) für AVLTree (ein rekursiver Helfer ist der sauberste Weg). Fügen Sie value wie in einem normalen BST ein und ignorieren Sie ihn, falls er bereits vorhanden ist. Berechnen Sie auf dem Rückweg nach oben die Höhe und den Balance-Faktor jedes Knotens neu. Wenn ein Knoten unbalanciert ist, wenden Sie die entsprechende Rotation (oder das Paar von Rotationen) an, bevor Sie im Aufrufstapel weiter nach oben zurückkehren.

Probier es selbst

#include <stdio.h>
#include <string.h>
#include "avltree.h"

static void preorderValues(Node* node, int* vals, int* count) {
    if (node == NULL) {
        return;
    }
    vals[(*count)++] = node->value;
    preorderValues(node->left, vals, count);
    preorderValues(node->right, vals, count);
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
            int vals[10000];
            int count = 0;
            preorderValues(tree->root, vals, &count);
            for (int i = 0; i < count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%d", vals[i]);
            }
            printf("\n");
        }
        if (parsed >= 1 && strcmp(cmd, "height") == 0) {
            printf("%d\n", AVLTree_getHeight(tree, tree->root));
        }
    }
    return 0;
}