削除

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 11/16。

削除は、挿入時と同じリバランスの習慣を持つBST（二分探索木）の削除です。削除されるノードには、処理すべき3つのパターンがあります：子がない場合（そのまま削除する）、子が1つの場合（その子と置き換える）、または、厄介なケースである子が2つの場合です。この場合、ノードの値をインオーダ・サクセサ（右部分木の中で最小の値）で置き換え、その後、右部分木からそのサクセサを削除します。

挿入と同様に、遡る途中のすべての祖先ノードで高さと平衡係数を再計算し、不均衡になった場合は適切な回転処理を適用します。リバランスのロジックは挿入と同じですが、どのケースを選択するかの条件が、新しい値がどこに配置されたかではなく、重い方の子の平衡係数を確認する点だけが異なります。

チャレンジ

中級

AVLTree にメソッド delete(value) を作成してください（再帰的なヘルパー関数を使用するとうまくいきます）。標準的な BST の削除方法を使用して value を削除します。子が2つあるノードの場合は、その値を右部分木で最小の値に置き換え、その後、右部分木からその値を削除します。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;
}