C 언어로 AVL 트리 구현하기: 균형 잡힌 탐색의 비결

AVL 트리는 데이터의 삽입과 삭제가 이루어질 때도 항상 균형 상태를 유지하는 이진 탐색 트리입니다. 이 균형 속성 덕분에 평균 및 최악의 경우에도 O(log n)의 탐색 시간 복잡도를 보장합니다. 본 기사에서는 C 언어로 AVL 트리를 구현하는 방법과 이를 활용한 균형 잡힌 탐색의 핵심을 자세히 살펴봅니다.

AVL 트리란 무엇인가

AVL 트리는 이진 탐색 트리의 한 종류로, 삽입과 삭제 시 항상 균형을 유지하도록 설계된 데이터 구조입니다. 균형을 유지하기 위해 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1을 넘지 않아야 합니다.

AVL 트리의 주요 특성

높이 균형 속성: 모든 노드에서 서브트리 높이 차이가 -1, 0, 1 사이를 유지합니다.
탐색 성능: 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)으로 일정합니다.
회전 연산: 균형이 깨졌을 때 LL, RR, LR, RL 회전으로 트리를 재구성합니다.

AVL 트리의 역사

AVL 트리는 1962년 Georgy Adelson-Velsky와 Evgenii Landis가 개발했으며, 이들의 이름에서 앞 글자를 따 AVL 트리라고 명명되었습니다.

AVL 트리는 균형 잡힌 구조 덕분에 데이터 검색 속도를 유지하면서 삽입 및 삭제 연산을 효율적으로 처리하는 데 적합한 데이터 구조입니다.

AVL 트리에서 균형을 유지하는 방법

AVL 트리는 삽입 및 삭제 연산 후에도 항상 높이 균형 속성을 유지합니다. 이를 위해 균형 인수(Balance Factor)를 계산하고, 균형이 깨진 경우 적절한 회전 연산을 수행합니다.

균형 인수(Balance Factor)

균형 인수는 노드의 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값입니다.

균형 상태: -1, 0, 1
불균형 상태: 균형 인수가 -1보다 작거나 1보다 크면 불균형 상태로 간주됩니다.

회전 연산의 종류

AVL 트리는 불균형 상태를 해소하기 위해 다음 네 가지 회전 연산을 수행합니다.

LL 회전 (왼쪽-왼쪽)

왼쪽 서브트리의 왼쪽 노드 삽입으로 불균형이 발생했을 때 수행합니다. 트리를 오른쪽으로 회전시켜 균형을 복원합니다.

RR 회전 (오른쪽-오른쪽)

오른쪽 서브트리의 오른쪽 노드 삽입으로 불균형이 발생했을 때 수행합니다. 트리를 왼쪽으로 회전시켜 균형을 복원합니다.

LR 회전 (왼쪽-오른쪽)

왼쪽 서브트리의 오른쪽 노드 삽입으로 불균형이 발생했을 때 수행합니다. 먼저 왼쪽 서브트리를 왼쪽으로 회전한 뒤, LL 회전을 수행합니다.

RL 회전 (오른쪽-왼쪽)

오른쪽 서브트리의 왼쪽 노드 삽입으로 불균형이 발생했을 때 수행합니다. 먼저 오른쪽 서브트리를 오른쪽으로 회전한 뒤, RR 회전을 수행합니다.

균형 유지 과정

삽입/삭제 후 높이 계산: 삽입 또는 삭제 연산 후 각 노드의 높이를 업데이트합니다.
균형 인수 확인: 각 노드의 균형 인수를 계산합니다.
회전 수행: 균형 인수가 -1보다 작거나 1보다 큰 경우 적절한 회전 연산으로 균형을 복원합니다.

이러한 과정을 통해 AVL 트리는 항상 효율적인 탐색이 가능하도록 균형 상태를 유지합니다.

C 언어에서 AVL 트리의 노드 정의

AVL 트리의 노드는 각 데이터와 함께 높이 정보 및 왼쪽, 오른쪽 자식을 가리키는 포인터를 포함합니다. 이를 통해 높이 균형 속성을 계산하고 트리를 관리할 수 있습니다. 아래는 C 언어로 AVL 트리 노드를 정의하는 방법입니다.

AVL 트리 노드 구조

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

// AVL 트리 노드 정의
typedef struct AVLNode {
    int key; // 노드의 값
    struct AVLNode* left; // 왼쪽 자식 포인터
    struct AVLNode* right; // 오른쪽 자식 포인터
    int height; // 노드의 높이
} AVLNode;

노드 생성 함수

AVL 트리 노드를 동적으로 생성하는 함수를 작성합니다.

// 새로운 AVL 노드 생성 함수
AVLNode* createNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode)); // 메모리 할당
    node->key = key; // 값 설정
    node->left = NULL; // 왼쪽 자식 초기화
    node->right = NULL; // 오른쪽 자식 초기화
    node->height = 1; // 새 노드의 초기 높이 설정
    return node;
}

노드 높이 계산 함수

각 노드의 높이를 계산하는 함수는 균형 인수를 계산하거나 회전 연산을 수행할 때 필요합니다.

// 노드의 높이 반환 함수
int getHeight(AVLNode* node) {
    if (node == NULL) {
        return 0; // 노드가 없으면 높이는 0
    }
    return node->height;
}

노드의 핵심 역할

key: 데이터를 저장하며 트리의 탐색 및 삽입 기준이 됩니다.
left, right: 자식 노드를 가리키며 트리의 구조를 형성합니다.
height: 트리의 균형을 유지하기 위해 사용됩니다.

이 노드 정의를 바탕으로 AVL 트리의 삽입, 삭제, 탐색 기능을 구현할 수 있습니다.

AVL 트리 삽입 연산

AVL 트리에서 데이터를 삽입할 때, 일반적인 이진 탐색 트리(BST)의 삽입 과정을 따르며 삽입 후 높이 균형 속성을 유지하기 위해 필요한 경우 회전 연산을 수행합니다.

삽입 연산의 단계

BST 삽입: 데이터가 들어갈 올바른 위치를 찾아 삽입합니다.
높이 갱신: 삽입된 노드부터 루트까지 모든 노드의 높이를 갱신합니다.
균형 검사: 각 노드의 균형 인수(Balance Factor)를 계산합니다.
회전 수행: 균형이 깨진 노드에서 적절한 회전을 수행해 트리를 재구성합니다.

삽입 함수 구현

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

// AVL 노드 높이 업데이트 함수
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 노드의 균형 인수 계산 함수
int getBalance(AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 오른쪽 회전 연산
AVLNode* rotateRight(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // 회전 수행
    x->right = y;
    y->left = T2;

    // 높이 갱신
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;
}

// 왼쪽 회전 연산
AVLNode* rotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // 회전 수행
    y->left = x;
    x->right = T2;

    // 높이 갱신
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

// AVL 트리 삽입 함수
AVLNode* insertNode(AVLNode* node, int key) {
    // 기본 BST 삽입
    if (node == NULL) {
        return createNode(key);
    }
    if (key < node->key) {
        node->left = insertNode(node->left, key);
    } else if (key > node->key) {
        node->right = insertNode(node->right, key);
    } else {
        return node; // 중복 키는 허용하지 않음
    }

    // 높이 갱신
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));

    // 균형 인수 계산
    int balance = getBalance(node);

    // LL 회전
    if (balance > 1 && key < node->left->key) {
        return rotateRight(node);
    }
    // RR 회전
    if (balance < -1 && key > node->right->key) {
        return rotateLeft(node);
    }
    // LR 회전
    if (balance > 1 && key > node->left->key) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    // RL 회전
    if (balance < -1 && key < node->right->key) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node; // 변경된 루트 반환
}

삽입 연산의 주요 특징

균형 상태를 유지하며 삽입 연산을 완료합니다.
LL, RR, LR, RL 회전을 통해 트리의 구조를 자동으로 조정합니다.
모든 연산은 O(log n)의 시간 복잡도를 가집니다.

이 삽입 함수는 AVL 트리의 핵심인 균형 유지 메커니즘을 잘 반영하며, 효율적인 탐색 및 데이터 관리를 지원합니다.

AVL 트리 삭제 연산

AVL 트리에서 노드를 삭제할 때, 기본적으로 이진 탐색 트리(BST)의 삭제 연산을 수행한 후 균형 상태를 유지하기 위해 필요하면 회전 연산을 수행합니다.

삭제 연산의 단계

BST 삭제: 삭제하려는 노드를 찾아 제거합니다.
높이 갱신: 삭제된 노드부터 루트까지 모든 노드의 높이를 갱신합니다.
균형 검사: 각 노드의 균형 인수(Balance Factor)를 계산합니다.
회전 수행: 균형이 깨진 노드에서 적절한 회전을 수행해 트리를 재구성합니다.

삭제 함수 구현

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

// 최소값 노드를 찾는 함수
AVLNode* findMinValueNode(AVLNode* node) {
    AVLNode* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

// AVL 트리 삭제 함수
AVLNode* deleteNode(AVLNode* root, int key) {
    // 기본 BST 삭제
    if (root == NULL) {
        return root;
    }

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        // 삭제할 노드 발견
        if ((root->left == NULL) || (root->right == NULL)) {
            AVLNode* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                // 자식이 없는 경우
                temp = root;
                root = NULL;
            } else {
                // 자식이 하나인 경우
                *root = *temp;
            }
            free(temp);
        } else {
            // 자식이 둘인 경우
            AVLNode* temp = findMinValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL) {
        return root;
    }

    // 높이 갱신
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    // 균형 인수 계산
    int balance = getBalance(root);

    // LL 회전
    if (balance > 1 && getBalance(root->left) >= 0) {
        return rotateRight(root);
    }
    // LR 회전
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    // RR 회전
    if (balance < -1 && getBalance(root->right) <= 0) {
        return rotateLeft(root);
    }
    // RL 회전
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

삭제 연산의 주요 특징

기본적으로 BST 삭제를 수행하며, 높이 균형을 유지하기 위해 회전을 추가합니다.
LL, RR, LR, RL 회전을 통해 트리의 구조를 조정합니다.
연산의 시간 복잡도는 O(log n)입니다.

삭제 연산 후 균형 복원

삭제로 인해 트리의 균형이 깨졌을 경우, 각 노드의 균형 인수를 계산하고 적절한 회전 연산을 통해 트리를 재구성합니다.
균형 상태를 유지함으로써 탐색, 삽입, 삭제 연산의 성능을 지속적으로 보장합니다.

이 삭제 함수는 AVL 트리의 효율적이고 안정적인 데이터 관리에 중요한 역할을 합니다.

AVL 트리에서 탐색 구현

AVL 트리에서 탐색 연산은 일반적인 이진 탐색 트리(BST)의 탐색 방식과 동일합니다. AVL 트리가 균형을 유지하므로, 탐색의 시간 복잡도는 항상 O(log n)으로 유지됩니다.

탐색 연산의 단계

루트 노드에서 시작: 탐색을 트리의 루트 노드에서 시작합니다.
값 비교: 탐색하려는 값과 현재 노드의 키 값을 비교합니다.

찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동합니다.
찾고자 하는 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동합니다.
값이 일치하면 탐색 성공입니다.

재귀 또는 반복: 트리의 끝에 도달하거나 값을 찾을 때까지 이 과정을 반복합니다.

탐색 함수 구현

아래는 C 언어로 AVL 트리에서 탐색 연산을 구현한 코드입니다.

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

// AVL 트리에서 특정 값을 탐색하는 함수
AVLNode* searchNode(AVLNode* root, int key) {
    // 트리가 비어 있거나 값을 찾은 경우
    if (root == NULL || root->key == key) {
        return root;
    }

    // 찾고자 하는 값이 현재 노드보다 작으면 왼쪽으로 이동
    if (key < root->key) {
        return searchNode(root->left, key);
    }

    // 찾고자 하는 값이 현재 노드보다 크면 오른쪽으로 이동
    return searchNode(root->right, key);
}

탐색 연산의 시간 복잡도

AVL 트리는 균형 잡힌 구조를 유지하므로, 트리의 높이는 항상 O(log n) 이내로 유지됩니다.
따라서 탐색 연산의 시간 복잡도는 최악의 경우에도 O(log n) 입니다.

탐색 예시

트리에 다음과 같은 값들이 포함되어 있다고 가정합니다.

       30
      /  \
    20    40
   /  \     \
  10   25    50

탐색하려는 값이 25인 경우:

루트 노드(30)와 비교 → 25 < 30 → 왼쪽으로 이동
20과 비교 → 25 > 20 → 오른쪽으로 이동
25와 비교 → 값이 일치 → 탐색 성공

탐색 연산의 주요 특징

AVL 트리는 균형 상태를 유지하므로 탐색 성능이 일정합니다.
트리의 구조에 관계없이 항상 O(log n) 시간 안에 탐색이 완료됩니다.
데이터가 정렬되어 있어 이진 탐색 트리의 장점을 그대로 활용할 수 있습니다.

이 탐색 함수는 AVL 트리의 효율적인 데이터 검색을 지원하며, 다양한 응용 분야에서 유용하게 사용됩니다.

응용 예시: AVL 트리로 데이터 정렬

AVL 트리는 균형 잡힌 구조를 유지하면서 데이터를 삽입하므로, 정렬되지 않은 데이터를 AVL 트리에 삽입한 뒤 중위 순회를 수행하면 데이터를 오름차순으로 정렬된 형태로 얻을 수 있습니다.

AVL 트리 정렬 과정

데이터 삽입: 정렬하려는 데이터를 AVL 트리에 삽입합니다. AVL 트리는 자동으로 균형을 유지합니다.
중위 순회(In-order Traversal): 중위 순회를 수행하면 트리 노드들이 오름차순으로 방문됩니다.
결과 출력: 방문한 노드의 키 값을 출력하면 정렬된 데이터를 얻을 수 있습니다.

중위 순회 함수 구현

아래는 C 언어로 중위 순회를 구현한 코드입니다.

#include <stdio.h>

// 중위 순회 함수
void inOrderTraversal(AVLNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left); // 왼쪽 서브트리 방문
        printf("%d ", root->key);    // 현재 노드 출력
        inOrderTraversal(root->right); // 오른쪽 서브트리 방문
    }
}

정렬 예시

정렬하려는 데이터: {50, 20, 40, 70, 60, 10, 30}

AVL 트리에 삽입
트리에 데이터를 삽입하면 다음과 같은 구조가 생성됩니다.

       40
      /  \
    20    60
   /  \   /  \
  10  30 50   70

중위 순회 수행
중위 순회 결과: 10, 20, 30, 40, 50, 60, 70

정렬 알고리즘으로서 AVL 트리의 장점

시간 복잡도: 삽입 연산이 O(log n)으로 수행되므로 정렬 알고리즘으로 사용 시 O(n log n)의 시간 복잡도를 가집니다.
동적 데이터 처리: AVL 트리는 동적으로 데이터를 추가하거나 삭제하면서도 항상 정렬 상태를 유지합니다.
다양한 응용 가능성: 데이터베이스, 파일 시스템 등 정렬된 데이터가 필요한 다양한 시스템에서 활용 가능합니다.

주의점

AVL 트리는 삽입, 삭제 시 균형 유지 비용이 발생하므로, 정렬만이 목적이라면 단순 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)보다 효율적이지 않을 수 있습니다.
하지만 동적 데이터 환경에서는 AVL 트리가 정렬 유지와 탐색 성능 측면에서 강점을 발휘합니다.

AVL 트리를 활용하면 데이터 정렬 및 탐색 작업을 효율적으로 수행할 수 있으며, 이를 다양한 실제 응용에서 활용할 수 있습니다.

AVL 트리 관련 연습 문제

AVL 트리의 삽입, 삭제, 탐색 연산을 이해하고 연습할 수 있는 문제를 제공합니다. 문제를 풀며 AVL 트리의 균형 유지 메커니즘과 작동 원리를 익혀보세요.

문제 1: AVL 트리에 데이터 삽입

다음 데이터를 순서대로 AVL 트리에 삽입하세요. 각 단계에서 트리 구조를 그리고 균형 상태를 확인하십시오.
데이터: {30, 20, 40, 10, 25, 35, 50}

삽입 후 트리의 루트와 각 노드의 높이를 표시하세요.
삽입 과정에서 필요한 회전 연산(LL, RR, LR, RL)을 구체적으로 설명하세요.

문제 2: AVL 트리에서 노드 삭제

다음 트리에서 값을 삭제한 후 트리의 구조를 작성하고 균형 상태를 유지하기 위한 회전 연산을 설명하세요.

초기 트리:

       30
      /  \
    20    40
   /  \      \
  10   25     50

삭제할 값: 20

삭제 후 트리의 루트와 각 노드의 높이를 표시하세요.
삭제로 인해 필요한 회전 연산(LL, RR, LR, RL)을 구체적으로 설명하세요.

문제 3: 탐색 연산

다음 트리에서 값을 탐색하는 과정을 단계별로 설명하세요.

트리 구조:

       50
      /  \
    30    70
   /  \   /  \
  20  40 60   80

탐색할 값: 40, 65

탐색이 성공하는 경우와 실패하는 경우의 차이를 설명하세요.
AVL 트리에서 탐색 시간 복잡도가 O(log n)임을 입증하세요.

문제 4: 중위 순회로 정렬 확인

다음 데이터를 AVL 트리에 삽입한 후 중위 순회를 수행하세요.
데이터: {15, 10, 20, 8, 12, 25, 18}

중위 순회 결과를 오름차순으로 작성하세요.
중위 순회가 항상 정렬된 결과를 반환하는 이유를 설명하세요.

문제 5: 코드 작성 연습

AVL 트리의 주요 연산(삽입, 삭제, 탐색)을 직접 구현하고 다음 질문에 답하세요.

구현한 코드에서 균형 인수 계산이 정확히 작동하는지 테스트하세요.
LL, RR, LR, RL 회전이 올바르게 수행되는지 확인하세요.
트리에 노드를 추가하거나 제거한 후 높이가 항상 올바르게 유지되는지 검증하세요.

도전 과제

AVL 트리에서 특정 값 범위의 데이터를 탐색하는 함수를 구현하세요.

예를 들어, 범위 [15, 25]에 포함된 값을 출력하세요.
효율적인 탐색을 위해 AVL 트리의 균형 상태를 어떻게 활용할 수 있는지 설명하세요.

이 연습 문제를 통해 AVL 트리의 이론적 원리를 이해하고, 이를 실질적으로 구현하며 학습 효과를 높일 수 있습니다.

요약

본 기사에서는 AVL 트리의 개념과 균형 유지 메커니즘을 이해하고, C 언어로 AVL 트리를 구현하는 방법을 단계적으로 설명했습니다. AVL 트리는 삽입, 삭제, 탐색 연산에서 항상 O(log n)의 성능을 보장하며, 데이터 정렬 및 검색에 적합한 효율적인 데이터 구조입니다. 회전 연산(LL, RR, LR, RL)을 통해 균형 상태를 유지하고, 다양한 응용 사례에서 활용할 수 있음을 확인했습니다. AVL 트리는 특히 동적으로 변화하는 데이터 환경에서 뛰어난 성능을 발휘합니다.