[WEEK06] AVL 트리

Krafton Jungle/2. Keywords

[WEEK06] AVL 트리

munsik22 2025. 4. 21. 15:19

AVL 트리

AVL 트리Adelson-Velsky and Landis Tree는 이진 탐색 트리의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 1 이하가 되도록 자동으로 균형을 맞추는 구조다.

🎯 핵심 포인트: 삽입이나 삭제 이후 트리의 균형이 깨지면, 회전Rotation을 통해 다시 균형을 맞춘다.

균형 인수 (Balance Factor)

각 노드의 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
가능한 균형 인수: -1, 0, 1
이 범위를 벗어나는 경우 불균형 상태이며, 회전이 필요하다.

회전 (Rotation)

불균형 유형	해결 방법
LL (Left-Left)	오른쪽 회전 (Right Rotation)
RR (Right-Right)	왼쪽 회전 (Left Rotation)
LR (Left-Right)	왼쪽 회전 후 오른쪽 회전 (Left-Right Rotation)
RL (Right-Left)	오른쪽 회전 후 왼쪽 회전 (Right-Left Rotation)

각 회전의 목적은 불균형 노드를 루트로 하는 서브트리의 균형을 되찾는 것이다.

삽입

기본적으로는 BST의 삽입과 같으나, 항상 balance factor에 유의해야 한다.

삭제

마찬가지로 BST의 삭제와 같으나, 항상 balance factor에 유의해야 한다.

시간 복잡도

AVL 트리는 항상 균형을 유지하므로, 다음과 같은 시간 복잡도를 보장한다.

탐색: O(log n)
삽입: O(log n)
삭제: O(log n)

BST는 최악의 경우 선형 구조로 퇴화(O(n))할 수 있지만, AVL 트리는 그럴 위험이 없다는 장점이 있다.

💻 AVL 트리 구현 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int key;
    int height;
    int count; // 중복 개수
    struct node* left;
    struct node* right;
} node;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(node* n) {
    if (n == NULL) return 0;
    return n->height;
}

node* create_node(int key) {
    node* new_node = (node*)malloc(sizeof(node));
    new_node->key = key;
    new_node->height = 1;
    new_node->count = 1; // 초기 중복 count
    new_node->left = new_node->right = NULL;
    return new_node;
}

node* rotate_right(node* y) {
    node* x = y->left;
    node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

node* rotate_left(node* x) {
    node* y = x->right;
    node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int get_balance(node* n) {
    if (n == NULL) return 0;
    return height(n->left) - height(n->right);
}

// 중복 허용 삽입
node* insert(node* n, int key) {
    if (n == NULL) return create_node(key);

    if (key < n->key)
        n->left = insert(n->left, key);
    else if (key > n->key)
        n->right = insert(n->right, key);
    else {
        n->count += 1; // 중복 key
        return n;
    }

    n->height = 1 + max(height(n->left), height(n->right));
    int balance = get_balance(n);

    // LL
    if (balance > 1 && key < n->left->key)
        return rotate_right(n);

    // RR
    if (balance < -1 && key > n->right->key)
        return rotate_left(n);

    // LR
    if (balance > 1 && key > n->left->key) {
        n->left = rotate_left(n->left);
        return rotate_right(n);
    }

    // RL
    if (balance < -1 && key < n->right->key) {
        n->right = rotate_right(n->right);
        return rotate_left(n);
    }

    return n;
}

// 최소값 노드 찾기
node* min_value_node(node* n) {
    node* current = n;
    while (current->left != NULL)
        current = current->left;
    return current;
}

// 삭제 함수
node* delete_node(node* root, int key) {
    if (root == NULL) return root;

    if (key < root->key)
        root->left = delete_node(root->left, key);
    else if (key > root->key)
        root->right = delete_node(root->right, key);
    else {
        if (root->count > 1) {
            root->count -= 1;
            return root;
        }

        if (root->left == NULL || root->right == NULL) {
            node* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            free(temp);
        } else {
            node* temp = min_value_node(root->right);
            root->key = temp->key;
            root->count = temp->count;
            temp->count = 1; // 삭제 대상만 줄이기
            root->right = delete_node(root->right, temp->key);
        }
    }

    if (root == NULL) return root;

    root->height = 1 + max(height(root->left), height(root->right));
    int balance = get_balance(root);

    // 회전 케이스
    if (balance > 1 && get_balance(root->left) >= 0)
        return rotate_right(root);

    if (balance > 1 && get_balance(root->left) < 0) {
        root->left = rotate_left(root->left);
        return rotate_right(root);
    }

    if (balance < -1 && get_balance(root->right) <= 0)
        return rotate_left(root);

    if (balance < -1 && get_balance(root->right) > 0) {
        root->right = rotate_right(root->right);
        return rotate_left(root);
    }

    return root;
}

// 검색 함수
node* search(node* root, int key) {
    if (root == NULL || root->key == key)
        return root;
    if (key < root->key)
        return search(root->left, key);
    return search(root->right, key);
}

// 중위 순회
void inorder(node* root) {
    if (root != NULL) {
        inorder(root->left);
        for (int i = 0; i < root->count; i++)
            printf("%d ", root->key);
        inorder(root->right);
    }
}

// 동적 메모리 해제
void free_tree(node* root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main() {
    node* root = NULL;
    int keys[] = {10, 20, 10, 30, 20, 20, 40, 25};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        root = insert(root, keys[i]);
    }

    printf("중위 순회 결과: ");
    inorder(root);
    printf("\n");

    int search_key = 20;
    node* found = search(root, search_key);
    if (found)
        printf("키 %d 존재 (개수: %d)\n", search_key, found->count);
    else
        printf("키 %d 없음\n", search_key);

    // 삭제 테스트
    root = delete_node(root, 20);
    printf("20 삭제 후: ");
    inorder(root);
    printf("\n");

    root = delete_node(root, 20);
    root = delete_node(root, 20);
    printf("20 완전 삭제 후: ");
    inorder(root);
    printf("\n");

    free_tree(root);
    return 0;
}

AVL 트리 vs RB 트리

AVL 트리와 레드-블랙 트리는 자기 균형 이진 탐색 트리Self-Balancing BST라는 공통점을 가지지만, 균형을 유지하는 방식과 그로 인한 성능 특성에는 차이점이 있다.

항목	AVL 트리	레드-블랙 트리
균형 조건	모든 노드의 왼쪽, 오른쪽 서브트리 높이 차이가 ≤ 1	색상 규칙(레드/블랙) 기반의 완화된 균형
균형 정도	더 엄격하게 균형을 유지	덜 엄격하게 균형을 유지
회전 횟수	삽입/삭제 시 회전이 더 자주 발생	상대적으로 회전이 적음
탐색 성능	더 균형 잡혀 있어 탐색 속도 우수	AVL보다는 약간 느릴 수 있음
삽입/삭제 성능	삭제 연산이 느릴 수 있음 (재균형이 복잡)	삽입/삭제 성능이 상대적으로 더 일정함
사용 사례	읽기/탐색이 많은 시스템에 유리 (ex. 데이터베이스 색인)	쓰기/수정이 많은 시스템에 유리 (ex. OS의 map/set 구현)
구현 복잡도	더 복잡 (높이 계산 + 다양한 회전 케이스)	상대적으로 간단 (색상 규칙 중심)
노드 속성	키, 높이 (또는 균형 인수)	키, 색상(Red/Black)

AVL 트리는 빠른 탐색이 중요한 상황에서 유리하다. (검색 위주의 시스템, 데이터베이스 색인 구조 등에서 사용)
레드-블랙 트리는 삽입/삭제가 빈번한 경우에 더 효율적이다. (STL의 map, set, Java의 TreeMap, Linux 커널 등에서 사용)

[참고자료]

AVL 트리를 알아보자

AVL Tree를 알아보자

일반적인 이진검색트리에서는 트리구조가 한 쪽으로 치우쳐지는 경우가 발생할 수 있습니다. 이진검색트리의 평균 검색속도는 O(logN)이지만 한 쪽으로 치우쳐진 경우에는 검색속도가 O(N)까지

velog.io

균형을 빡세게 유지하는 AVL 트리는 이진탐색트리의 단점을 어떻게 극복했을까요? AVL 트리의 동작방식과 장단점을 살펴봅니다 :)

'Krafton Jungle > 2. Keywords' 카테고리의 다른 글

[WEEK07] 묵시적 가용 리스트 (0)	2025.04.25
[WEEK07] 동적 메모리 할당 (0)	2025.04.25
[WEEK06] 메모리 누수 (0)	2025.04.18
[WEEK06] 레드 블랙 트리 (Red-Black Tree) (0)	2025.04.17
[WEEK06] 균형 탐색 트리 (0)	2025.04.16

현재글[WEEK06] AVL 트리

MUNSIK BLOG

munsik22 님의 블로그 입니다.

문식이, NextJS, 크래프톤정글, webproxy, 합격후기, malloc, springboot, csapp, C++, 프로그래머스, pintos, 오답노트, 정보처리기사, 레드블랙트리, C, 백준, 나만무,

Today :
Yesterday :

[Munsik] MUNSIK BLOG [Munsik]