[c++] AVL 트리 데이터 구조

08 Dec 2023

AVL 트리는 균형 이진 검색 트리로, 각 노드의 두 하위 트리의 높이 차이가 1을 넘지 않도록 유지합니다. 이로 인해 검색, 삽입, 삭제 등의 연산이 항상 O(log n)의 시간 복잡도를 갖게 됩니다.

AVL 트리의 특징

모든 노드는 이진 검색 트리 조건을 만족합니다: 왼쪽 서브트리의 모든 노드는 현재 노드보다 작고, 오른쪽 서브트리의 모든 노드는 현재 노드보다 큽니다.
각 노드의 높이 차이는 -1, 0, 1 중 하나여야 합니다.
노드의 삽입, 삭제 시, 트리가 불균형 상태에 빠지면 회전 연산을 통해 균형을 맞춥니다.

C++에서의 AVL 트리 구현

#include <iostream>

struct Node {
    int key;
    int height;
    Node* left;
    Node* right;
};

class AVLTree {
public:
    Node* root;

    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* rotateRight(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;
    }

    // rotateLeft, rotateLeft, insert, delete 등의 메서드는 비슷한 방식으로 구현됩니다.
};

AVL 트리는 자료 구조 이론에서 중요한 개념으로, 균형 이진 검색 트리의 성능을 보장하는 데 사용됩니다.

참조: GeeksforGeeks - AVL Tree