삽입

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 9번째.

insert는 일반적인 이진 탐색 트리 삽입으로 시작합니다. 값을 비교하며 내려가서, 왼쪽이나 오른쪽으로 이동한 뒤 null 슬롯이 발견된 위치에 새 노드를 배치합니다(중복은 무시합니다). AVL 부분은 다시 위로 올라가는 과정에서 발생합니다. 노드를 배치한 후, 경로상의 모든 조상 노드는 자신의 height를 다시 계산하고 균형 인수를 확인합니다.

노드의 균형이 깨지면, 어느 쪽이 무거운지 그리고 새 값이 어디에 위치했는지에 따라 네 가지 경우 중 어느 것이 적용될지 결정됩니다. **left-left**와 **right-right**는 단일 회전이 필요하며, **left-right**와 **right-left**는 지그재그를 펴기 위한 내부 회전과 그 뒤를 잇는 외부 회전까지 총 두 번의 회전이 필요합니다.

챌린지

중급

AVLTree에 insert(value) 메서드를 작성하세요 (재귀적 헬퍼 함수를 사용하는 것이 가장 깔끔합니다). value를 일반적인 BST처럼 삽입하되, 이미 존재한다면 무시합니다. 재귀 호출이 반환되는 과정에서 각 노드의 높이와 균형 인수(balance factor)를 다시 계산하고, 노드가 불균형 상태라면 호출 스택을 따라 올라가기 전에 해당되는 회전(또는 한 쌍의 회전)을 적용하세요.

직접 해보기

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