Удаление

Урок 11 из 16 курса AVL-дерево — Серия «Структуры данных» №10 на Coddy.

Удаление — это удаление в BST с тем же принципом ребалансировки, что и при вставке. Существует три случая для удаляемого узла: нет потомков (просто удаляем его), один потомок (заменяем узел этим потомком) или два потомка — сложный случай, когда вы заменяете значение узла его инфиксным преемником (наименьшим значением в его правом поддереве), а затем вместо этого удаляете этот преемник из правого поддерева.

Как и при вставке, каждый предок на обратном пути вверх пересчитывает свою высоту и коэффициент сбалансированности, применяя подходящий тип поворота, если он становится несбалансированным. Логика ребалансировки идентична вставке, только условие выбора конкретного случая теперь основывается на коэффициенте сбалансированности «тяжелого» дочернего узла, а не на том, куда попало новое значение.

Задание

Средне

Напишите метод delete(value) в классе AVLTree (для этого хорошо подойдет вспомогательная рекурсивная функция). Удалите value, используя стандартное удаление из BST: для узла с двумя потомками замените его значение на минимальное значение в его правом поддереве, а затем удалите это значение из правого поддерева. Если value не найдено, ничего не делайте. При возврате по стеку рекурсии пересчитайте высоту и выполните балансировку точно так же, как это делает метод insert.

Попробуйте сами

#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;
}