Löschen

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

Das Löschen erfolgt wie das BST-Löschen mit derselben Rebalancing-Gewohnheit wie beim Einfügen. Drei Fälle sind für den zu entfernenden Knoten zu behandeln: keine Kinder (einfach entfernen), ein Kind (durch dieses Kind ersetzen) oder zwei Kinder, der knifflige Fall, bei dem man den Wert des Knotens durch seinen In-Order-Nachfolger (den kleinsten Wert in seinem rechten Teilbaum) ersetzt und dann stattdessen diesen Nachfolger aus dem rechten Teilbaum löscht.

Genau wie beim Einfügen berechnet jeder Vorfahre auf dem Rückweg nach oben seine Höhe und seinen Balance-Faktor neu und wendet den jeweils passenden Rotationsfall an, falls er unbalanciert wird. Die Rebalancing-Logik ist identisch mit der beim Einfügen, nur die Bedingung für die Auswahl des Falls betrachtet nun den Balance-Faktor des schwereren Kindes, anstatt darauf zu schauen, wo ein neuer Wert gelandet ist.

Aufgabe

Mittel

Schreiben Sie eine Methode delete(value) für AVLTree (ein rekursiver Helfer eignet sich gut). Entfernen Sie value unter Verwendung des Standard-BST-Löschvorgangs: Ersetzen Sie bei einem Knoten mit zwei Kindern seinen Wert durch den kleinsten Wert in seinem rechten Teilbaum und löschen Sie diesen Wert anschließend aus dem rechten Teilbaum. Tun Sie nichts, wenn value nicht gefunden wird. Berechnen Sie auf dem Rückweg nach oben die Höhen neu und rebalancieren Sie den Baum genau so, wie es insert tut.

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, "delete") == 0) {
            AVLTree_delete(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
        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");
        }
    }
    return 0;
}