挿入

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

insert は、通常の二分探索木の挿入として始まります。値を比較しながら下へと進み、左または右へ移動して、null スロットが見つかった場所に新しいノードを配置します（重複は無視します）。AVL の処理は、戻る際に行われます。ノードを配置した後、パス上のすべての祖先ノードが height を再計算し、平衡係数をチェックします。

ノードが不均衡になった場合、どちらの側が重いかと、新しい値がどこに配置されたかによって、4つのケースのどれが適用されるかが決まります。left-left と right-right は単一回転が必要ですが、left-right と right-left は 2 回の回転が必要です。まずジグザグを解消するための内側の回転を行い、その後に外側の回転を行います。

チャレンジ

中級

AVLTree に insert(value) メソッドを記述してください（再帰的なヘルパー関数を使用するのが最も簡潔な方法です）。value を通常の BST のように挿入し、既に存在する場合は無視します。再帰から戻る際に、各ノードの高さと平衡係数（バランスファクター）を再計算し、ノードが不均衡な場合は、コールスタックを戻る前に対応する回転（または一対の回転）を適用してください。

自分で試してみよう

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