본문 바로가기
-----ETC-----/C++ 심화 알고리즘과 자료구조 시리즈

[C++로 배우는 알고리즘과 자료구조 심화] Day 5: 균형 이진 탐색 트리 (AVL 트리, Red-Black 트리)

by cogito21_cpp 2024. 8. 1.
반응형

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

AVL 트리는 자가 균형 이진 탐색 트리로, 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다. 이는 트리의 균형을 유지하여 탐색, 삽입, 삭제 연산의 시간 복잡도가 (O(\log n))이 되도록 합니다.

AVL 트리의 주요 특징

  1. 균형 조건: 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다.
  2. 회전 연산: 삽입 및 삭제 후 균형을 유지하기 위해 회전 연산을 사용합니다.

AVL 트리의 기본 연산

  1. 삽입 (Insert): 새로운 노드를 삽입한 후 균형을 유지합니다.
  2. 삭제 (Delete): 특정 키를 가진 노드를 삭제한 후 균형을 유지합니다.
  3. 검색 (Search): 특정 키를 가진 노드를 검색합니다.

AVL 트리의 구현

다음은 C++로 AVL 트리를 구현한 예제입니다. 삽입, 삭제, 검색 연산을 포함합니다.

 

AVL 트리 노드 정의

#include <iostream>

// AVL 트리 노드 구조체 정의
struct AVLNode {
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;

    AVLNode(int key) : key(key), left(nullptr), right(nullptr), height(1) {}
};

 

AVL 트리 클래스 정의

class AVLTree {
public:
    AVLTree();
    AVLNode* insert(AVLNode* node, int key);
    AVLNode* deleteNode(AVLNode* root, int key);
    AVLNode* search(AVLNode* root, int key);
    void inorder(AVLNode* root);

private:
    AVLNode* rightRotate(AVLNode* y);
    AVLNode* leftRotate(AVLNode* x);
    int getHeight(AVLNode* node);
    int getBalance(AVLNode* node);
    AVLNode* minValueNode(AVLNode* node);
};

AVLTree::AVLTree() {}

 

회전 연산 정의

// 오른쪽 회전 함수 정의
AVLNode* AVLTree::rightRotate(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::leftRotate(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;
}

 

노드의 높이 및 균형 계산

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

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

 

삽입 연산 정의

// 삽입 함수 정의
AVLNode* AVLTree::insert(AVLNode* node, int key) {
    if (node == nullptr) {
        return new AVLNode(key);
    }

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        return node;
    }

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

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

    // Left Left Case
    if (balance > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    // Left Right Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

 

삭제 연산 정의

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

// 삭제 함수 정의
AVLNode* AVLTree::deleteNode(AVLNode* root, int key) {
    if (root == nullptr) {
        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 == nullptr) || (root->right == nullptr)) {
            AVLNode* temp = root->left ? root->left : root->right;
            if (temp == nullptr) {
                temp = root;
                root = nullptr;
            } else {
                *root = *temp;
            }
            delete temp;
        } else {
            AVLNode* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

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

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

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

    // Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0) {
        return rightRotate(root);
    }

    // Left Right Case
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0) {
        return leftRotate(root);
    }

    // Right Left Case
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

 

검색 연산 정의

// 검색 함수 정의
AVLNode* AVLTree::search(AVLNode* root, int key) {
    if (root == nullptr || root->key == key) {
        return root;
    }

    if (key < root->key) {
        return search(root->left, key);
    }

    return search(root->right, key);
}

 

중위 순회 정의

// 중위 순회 함수 정의
void AVLTree::inorder(AVLNode* root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

 

사용 예제

int main() {
    AVLTree avl;
    AVLNode* root = nullptr;

    // 노드 삽입
    root = avl.insert(root, 10);
    root = avl.insert(root, 20);
    root = avl.insert(root, 30);
    root = avl.insert(root, 40);
    root = avl.insert(root, 50);
    root = avl.insert(root, 25);

    std::cout << "중위 순회 결과:" << std::endl;
    avl.inorder(root);
    std::cout << std::endl;

    std::cout << "키 20 삭제 후 중위 순회 결과:" <<

 std::endl;
    root = avl.deleteNode(root, 20);
    avl.inorder(root);
    std::cout << std::endl;

    return 0;
}

 

설명

  1. AVL 트리 노드 구조체:
    • key: 노드의 키 값입니다.
    • left, right: 왼쪽 및 오른쪽 자식 노드를 가리킵니다.
    • height: 노드의 높이입니다.
  2. AVL 트리 클래스:
    • insert: 새로운 노드를 삽입한 후 균형을 유지합니다.
    • deleteNode: 특정 키를 가진 노드를 삭제한 후 균형을 유지합니다.
    • search: 특정 키를 가진 노드를 검색합니다.
    • rightRotate, leftRotate: 균형을 유지하기 위해 회전 연산을 수행합니다.
    • getHeight: 노드의 높이를 계산합니다.
    • getBalance: 노드의 균형을 계산합니다.
    • minValueNode: 트리에서 최소값을 가진 노드를 찾습니다.
    • inorder: 트리의 중위 순회를 수행하여 노드를 출력합니다.
  3. 사용 예제:
    • 노드를 삽입하고 중위 순회를 통해 트리 구조를 출력합니다.
    • 노드를 삭제한 후, 중위 순회를 통해 트리 구조가 올바른지 확인합니다.

AVL 트리의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 6: 스플레이 트리(Splay Tree)"에 대해 학습하겠습니다.

반응형

'-----ETC----- > C++ 심화 알고리즘과 자료구조 시리즈' 카테고리의 다른 글

[C++로 배우는 알고리즘과 자료구조 심화] Day 6: 스플레이 트리 (Splay Tree)  (0) 2024.08.01
[C++로 배우는 알고리즘과 자료구조 심화] Day 7: 스킵 리스트 (Skip List)  (0) 2024.08.01
[C++로 배우는 알고리즘과 자료구조 심화] Day 3: 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)  (0) 2024.08.01
[C++로 배우는 알고리즘과 자료구조 심화] Day 4: 이면 탐색 트리 (Treap)  (0) 2024.08.01
[C++로 배우는 알고리즘과 자료구조 심화] Day 2: 세그먼트 트리 (Segment Tree)  (0) 2024.08.01

관련글

티스토리툴바