삭제

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

삭제는 삽입과 동일한 재균형 습관을 가진 BST 삭제입니다. 제거되는 노드에 대해 처리해야 할 세 가지 형태가 있습니다: 자식이 없는 경우(그냥 제거), 자식이 하나인 경우(해당 자식으로 교체), 또는 까다로운 경우인 자식이 둘인 경우로, 노드의 값을 중위 후속자(in-order successor)(오른쪽 서브트리에서 가장 작은 값)로 교체한 다음 오른쪽 서브트리에서 해당 후속자를 대신 삭제합니다.

삽입과 마찬가지로, 다시 올라가는 경로에 있는 모든 조상 노드는 높이와 균형 인수(balance factor)를 다시 계산하며, 불균형해질 경우 적절한 회전 케이스를 적용합니다. 재균형 로직은 삽입과 동일하지만, 어떤 케이스를 선택할지 결정하는 조건이 이제 새로운 값이 위치한 곳 대신 무거운 자식(heavy child)의 균형 인수를 확인한다는 점만 다릅니다.

챌린지

중급

AVLTree에 delete(value) 메서드를 작성하세요 (재귀적 헬퍼 함수를 사용하는 것이 좋습니다). 표준 BST 삭제 방식을 사용하여 value를 제거합니다: 자식이 둘인 노드의 경우, 해당 노드의 값을 오른쪽 서브트리에서 가장 작은 값으로 대체한 다음, 오른쪽 서브트리에서 그 값을 삭제합니다. 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;
}