[C++로 배우는 알고리즘과 자료구조] Day 8: 균형 이진 탐색 트리 (AVL 트리)

균형 이진 탐색 트리 (AVL Tree)

AVL 트리는 자가 균형 이진 탐색 트리의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 합니다. AVL 트리는 삽입, 삭제 연산 후 트리의 균형을 유지하기 위해 회전을 사용합니다.

AVL 트리의 특징:

1. 높이 균형: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하입니다.
2. 높이 제한: AVL 트리의 높이는 (O(\log n))로 제한됩니다.
3. 시간 복잡도: 검색, 삽입, 삭제 연산의 평균 및 최악의 경우 시간 복잡도는 (O(\log n))입니다.

AVL 트리의 주요 연산:

1. 삽입 (Insert)
2. 삭제 (Delete)
3. 검색 (Search)
4. 회전 (Rotation): 트리의 균형을 유지하기 위해 사용됩니다. (단순 회전과 이중 회전)

AVL 트리 구현

AVLTree.h

#ifndef AVLTREE_H
#define AVLTREE_H

#include <iostream>

// AVL 트리의 노드 구조체
struct AVLNode {
    int data; // 데이터
    AVLNode* left; // 왼쪽 자식 노드
    AVLNode* right; // 오른쪽 자식 노드
    int height; // 노드의 높이

    AVLNode(int value) : data(value), left(nullptr), right(nullptr), height(1) {} // 노드 생성자
};

// AVL 트리 클래스
class AVLTree {
public:
    AVLTree() : root(nullptr) {} // 생성자
    ~AVLTree(); // 소멸자

    void insert(int value); // 값 삽입
    void remove(int value); // 값 삭제
    bool search(int value) const; // 값 검색
    void inOrderTraversal() const; // 중위 순회

private:
    AVLNode* root; // 트리의 루트 노드

    AVLNode* insert(AVLNode* node, int value); // 값 삽입 (재귀)
    AVLNode* remove(AVLNode* node, int value); // 값 삭제 (재귀)
    AVLNode* search(AVLNode* node, int value) const; // 값 검색 (재귀)
    void inOrderTraversal(AVLNode* node) const; // 중위 순회 (재귀)
    void destroy(AVLNode* node); // 트리 파괴 (재귀)

    AVLNode* rotateRight(AVLNode* y); // 오른쪽 회전
    AVLNode* rotateLeft(AVLNode* x); // 왼쪽 회전
    int getHeight(AVLNode* node) const; // 노드의 높이 반환
    int getBalance(AVLNode* node) const; // 노드의 균형 인수 반환
    AVLNode* minValueNode(AVLNode* node) const; // 최소값 노드 반환
};

// 소멸자 정의 (메모리 해제)
AVLTree::~AVLTree() {
    destroy(root);
}

// 트리 파괴 함수 정의 (재귀)
void AVLTree::destroy(AVLNode* node) {
    if (node != nullptr) {
        destroy(node->left);
        destroy(node->right);
        delete node; // 노드 메모리 해제
    }
}

// 노드의 높이 반환 함수 정의
int AVLTree::getHeight(AVLNode* node) const {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

// 노드의 균형 인수 반환 함수 정의
int AVLTree::getBalance(AVLNode* node) const {
    if (node == nullptr) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 오른쪽 회전 함수 정의
AVLNode* AVLTree::rotateRight(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

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

    // 높이 업데이트
    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;

    // 새로운 루트 반환
    return x;
}

// 왼쪽 회전 함수 정의
AVLNode* AVLTree::rotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

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

    // 높이 업데이트
    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;

    // 새로운 루트 반환
    return y;
}

// 값 삽입 함수 정의 (재귀)
AVLNode* AVLTree::insert(AVLNode* node, int value) {
    // 이진 탐색 트리 삽입 과정
    if (node == nullptr) {
        return new AVLNode(value);
    }
    if (value < node->data) {
        node->left = insert(node->left, value);
    } else if (value > node->data) {
        node->right = insert(node->right, value);
    } else {
        return node;
    }

    // 높이 업데이트
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));

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

    // 균형을 맞추기 위한 회전
    if (balance > 1 && value < node->left->data) {
        return rotateRight(node);
    }
    if (balance < -1 && value > node->right->data) {
        return rotateLeft(node);
    }
    if (balance > 1 && value > node->left->data) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1 && value < node->right->data) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

// 값 삽입 함수 정의
void AVLTree::insert(int value) {
    root = insert(root, value);
}

// 최소값 노드 반환 함수 정의
AVLNode* AVLTree::minValueNode(AVLNode* node) const {
    AVLNode* current = node;
    while (current->left != nullptr) {
        current = current->left;
    }
    return current;
}

// 값 삭제 함수 정의 (재귀)
AVLNode* AVLTree::remove(AVLNode* node, int value) {
    // 이진 탐색 트리 삭제 과정
    if (node == nullptr) {
        return node;
    }
    if (value < node->data) {
        node->left = remove(node->left, value);
    } else if (value > node->data) {
        node->right = remove(node->right, value);
    } else {
        if (node->left == nullptr || node->right == nullptr) {
            AVLNode* temp = node->left ? node->left : node->right;
            if (temp == nullptr) {
                temp = node;
                node = nullptr;
            } else {
                *node = *temp;
            }
            delete temp;
        } else {
            AVLNode* temp = minValueNode(node->right);
            node->data = temp->data;
            node->right = remove(node->right, temp->data);
        }
    }

    if (node == nullptr) {
        return node;
    }

    // 높이 업데이트
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));

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

    // 균형을 맞추기 위한 회전
    if (balance > 1 && getBalance(node->left) >= 0) {
        return rotateRight(node);
    }
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1 && getBalance(node->right) <= 0) {
        return rotateLeft(node);
    }
    if (balance < -1 && getBalance(node->right) > 0) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

// 값 삭제 함수 정의
void AVLTree::remove(int value) {
    root = remove(root, value);
}

// 값 검색 함수 정의 (재귀)
AVLNode* AVLTree::search(AVLNode* node, int value)

 const {
    if (node == nullptr || node->data == value) {
        return node;
    }
    if (value < node->data) {
        return search(node->left, value);
    }
    return search(node->right, value);
}

// 값 검색 함수 정의
bool AVLTree::search(int value) const {
    return search(root, value) != nullptr;
}

// 중위 순회 함수 정의 (재귀)
void AVLTree::inOrderTraversal(AVLNode* node) const {
    if (node != nullptr) {
        inOrderTraversal(node->left);
        std::cout << node->data << " ";
        inOrderTraversal(node->right);
    }
}

// 중위 순회 함수 정의
void AVLTree::inOrderTraversal() const {
    inOrderTraversal(root);
    std::cout << std::endl;
}

#endif // AVLTREE_H

 

AVL 트리 예제

#include <iostream>
#include "AVLTree.h"

int main() {
    AVLTree tree;
    tree.insert(9);
    tree.insert(5);
    tree.insert(10);
    tree.insert(0);
    tree.insert(6);
    tree.insert(11);
    tree.insert(-1);
    tree.insert(1);
    tree.insert(2);

    std::cout << "중위 순회: ";
    tree.inOrderTraversal(); // 중위 순회 출력

    std::cout << "10 검색: " << (tree.search(10) ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "20 검색: " << (tree.search(20) ? "찾음" : "찾지 못함") << std::endl;

    tree.remove(10);
    std::cout << "10 삭제 후 중위 순회: ";
    tree.inOrderTraversal(); // 중위 순회 출력

    return 0;
}

 

설명

1. AVL 트리 (AVL Tree):
   • AVL 트리는 자가 균형 이진 탐색 트리로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지됩니다.
   • 검색, 삽입, 삭제 연산의 평균 및 최악의 경우 시간 복잡도는 (O(\log n))입니다.
2. AVL 트리의 주요 연산:
   • 삽입 (Insert): 새로운 값을 트리에 삽입합니다. 균형을 맞추기 위해 회전을 수행합니다.
   • 삭제 (Delete): 트리에서 특정 값을 삭제합니다. 균형을 맞추기 위해 회전을 수행합니다.
   • 검색 (Search): 특정 값을 트리에서 검색합니다.
   • 회전 (Rotation): 트리의 균형을 유지하기 위해 사용됩니다.
3. 트리 순회:
   • 중위 순회 (In-order Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문합니다.

이제 균형 이진 탐색 트리(AVL 트리)의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 9: 힙과 우선순위 큐"에 대해 학습하겠습니다.