C YC

IT Dev who working in Republic Of Korea

3 minute read

AVL 트리(AVL Tree) 란?

AVL 트리는 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 최대 1인 이진 탐색 트리입니다. 이러한 균형 조건을 통해 트리의 높이가 최소로 유지되어 효율적인 탐색이 가능합니다. 높이 차이를 균형 인수(Balance Factor)라고 하며, 모든 노드의 균형 인수는 -1, 0, 1 중 하나여야 합니다.

균형 인수 = (왼쪽 서브 트리 높이) - (오른쪽 서브 트리 높이)

AVLtree
(이미지출처 geeksforgeeks)

특징

  • 이진 탐색 트리: AVL 트리는 이진 탐색 트리의 모든 속성을 가집니다. 즉, 모든 노드에 대해 왼쪽 서브 트리의 값은 노드 값보다 작고, 오른쪽 서브 트리의 값은 노드 값보다 큽니다. 마치 사전처럼, 데이터가 정렬된 순서로 저장되어 있어 빠르게 원하는 정보를 찾을 수 있습니다.

  • 자가 균형: 삽입 또는 삭제 연산 후 트리의 균형이 깨질 경우, 회전(Rotation) 연산을 통해 자동으로 균형을 맞춥니다. 마치 로봇 청소기처럼, AVL 트리는 스스로 균형을 유지하며 데이터를 정리합니다.

  • 높이 균형: 모든 노드에서 왼쪽과 오른쪽 서브 트리의 높이 차이가 최대 1입니다. 이러한 균형 덕분에 AVL 트리는 항상 최소 높이를 유지하며, 효율적인 탐색이 가능합니다. 마치 고층 건물의 균형처럼, AVL 트리는 높이 균형을 통해 안정적인 데이터 관리를 제공합니다.

  • O(log n) 시간 복잡도: 탐색, 삽입, 삭제 연산 모두 최악의 경우에도 O(log n)의 시간 복잡도를 가집니다. 마치 고속도로처럼, AVL 트리는 데이터의 양에 상관없이 빠른 속도로 원하는 정보를 찾을 수 있습니다.

AVL 트리의 회전 연산

AVL 트리의 핵심 기능인 회전 연산은 트리의 균형이 깨졌을 때 이를 복구하는 역할을 합니다. 4가지 종류의 회전 연산이 존재하며, 각각의 상황에 맞게 적용됩니다.

  • LL 회전 (Single Left Rotation): 새로운 노드가 왼쪽 서브 트리의 왼쪽에 삽입되어 균형이 깨졌을 때 수행합니다. 마치 시계 방향으로 회전하는 것처럼, 트리를 왼쪽으로 기울여 균형을 맞춥니다.

  • RR 회전 (Single Right Rotation): 새로운 노드가 오른쪽 서브 트리의 오른쪽에 삽입되어 균형이 깨졌을 때 수행합니다. 마치 반시계 방향으로 회전하는 것처럼, 트리를 오른쪽으로 기울여 균형을 맞춥니다.

  • LR 회전 (Left-Right Rotation): 새로운 노드가 왼쪽 서브 트리의 오른쪽에 삽입되어 균형이 깨졌을 때 수행합니다. (왼쪽 회전 후 오른쪽 회전) 마치 두 번의 회전을 통해 균형을 맞추는 것처럼, LR 회전은 LL 회전과 RR 회전을 조합하여 복잡한 불균형을 해결합니다.

  • RL 회전 (Right-Left Rotation): 새로운 노드가 오른쪽 서브 트리의 왼쪽에 삽입되어 균형이 깨졌을 때 수행합니다. (오른쪽 회전 후 왼쪽 회전) 마치 두 번의 회전을 통해 균형을 맞추는 것처럼, RL 회전은 RR 회전과 LL 회전을 조합하여 복잡한 불균형을 해결합니다.

장단점

장점

  • 뛰어난 탐색 성능: O(log n)의 시간 복잡도로 매우 빠른 탐색이 가능합니다. 마치 빠른 속도로 달리는 기차처럼, AVL 트리는 데이터를 신속하게 찾을 수 있습니다.
  • 균형 유지: 자동으로 균형을 유지하므로, 최악의 경우에도 성능 저하가 없습니다. 마치 항상 균형을 유지하는 팽이처럼, AVL 트리는 안정적인 데이터 관리를 제공합니다.

단점

  • 구현 복잡: 회전 연산으로 인해 구현이 비교적 복잡합니다. 마치 복잡한 미로처럼, AVL 트리의 구현은 까다로운 과정을 거쳐야 합니다.
  • 삽입/삭제 오버헤드: 삽입/삭제 시 균형을 맞추기 위한 추가적인 연산이 필요합니다. 마치 집을 수리하는 것처럼, AVL 트리는 데이터를 삽입/삭제할 때마다 균형을 조정해야 합니다.

AVL 트리 활용 예시

AVL 트리는 데이터베이스 인덱스, 검색 엔진, 파일 시스템 등 다양한 분야에서 활용됩니다. 특히 빈번한 검색 작업이 필요한 경우 AVL 트리는 매우 유용한 선택입니다.

예제

#include <iostream>
#include <algorithm> // std::max

struct Node {
    int data;
    Node* left;
    Node* right;
    int height; // 높이

    Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

int getBalance(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

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

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

    return x;
}

Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

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

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

    return y;
}

// 삽입 함수 (일부)
Node* insert(Node* node, int data) {
    if (node == nullptr) {
        return new Node(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else {
        return node; // 중복된 값은 삽입하지 않음
    }

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

    // 균형 확인 및 회전
    int balance = getBalance(node);

    // LL
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // RR
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // LR
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    // ...

    return 0;
}


Top

You May Also Enjoy