C++로 구현하는 AVL 트리 판별 프로그램: 주어진 이진 트리가 AVL 트리인지 확인하기

AVL 트리는 자가 균형(self-balancing) 이진 탐색 트리의 한 종류로, 트리 내 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 초과하지 않는 것이 특징입니다. 이러한 균형 속성 덕분에 AVL 트리는 삽입, 삭제, 탐색 연산을 O(log n)의 시간 복잡도로 보장할 수 있습니다.

이 글에서는 주어진 이진 트리가 AVL 트리인지 아닌지를 판별하는 C++ 프로그램을 소개합니다.

알고리즘

AVL 트리 판별은 재귀적으로 해결할 수 있습니다. 각 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이를 계산하고, 그 차이가 1 이하인지 확인합니다. 또한 왼쪽 및 오른쪽 서브트리 역시 재귀적으로 AVL 트리 조건을 만족해야 합니다.

시작
함수 AVL() — 주어진 트리가 AVL 트리이면 true, 아니면 false를 반환한다.
    if(root == NULL)
        return 1
    leftheight = height(root->left)
    rightheight = height(root->right)
    if(abs(leftheight - rightheight) <= 1 && AVL(root->left) && AVL(root->right))
        return 1
    return 0
끝

C++ 예제 코드

아래 코드는 노드 생성, 높이 계산, AVL 여부 판별 함수를 포함한 전체 구현 예제입니다. 두 개의 서로 다른 트리를 만들어 각각 AVL 트리인지 검사합니다.

#include <bits/stdc++.h>
using namespace std;
class nod { //노드 선언
    public:
    int data;
    nod* l;
    nod* r;
};
nod* newNod(int d) { //새 노드 생성
    nod* Nod = new nod();
    Nod->data = d;
    Nod->l = NULL;
    Nod->r = NULL;
    return(Nod);
}
int max(int x, int y) { //두 값 중 큰 값 반환
    return (x >= y)? x: y;
}
int height(nod* node) { //트리의 높이 계산: 루트에서 가장 깊은 리프 노드까지의 경로에 있는 노드 수
    if(node == NULL)
        return 0;
    return 1 + max(height(node->l), height(node->r));
}
bool AVL(nod *root) {
    int lh;
    int rh;
    if(root == NULL)
        return 1;
    lh = height(root->l); //왼쪽 서브트리 높이
    rh = height(root->r); //오른쪽 서브트리 높이
    if(abs(lh-rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1;
    return 0;
}
int main() {
    //첫 번째 트리 구성
    nod *root = newNod(7);
    root->l = newNod(6);
    root->r = newNod(12);
    root->l->l = newNod(4);
    root->l->r = newNod(5);
    root->r->r = newNod(13);
    if(AVL(root))
        cout << "The Tree is AVL Tree"<<endl;
    else
        cout << "The Tree is not AVL Tree "<<endl;
    //두 번째 트리 구성 (균형이 깨진 경우)
    nod *root1 = newNod(7);
    root1->l = newNod(6);
    root1->r = newNod(12);
    root1->l->l = newNod(4);
    root1->l->r = newNod(5);
    root1->r->r = newNod(13);
    root1->r->r->r = newNod(26);
    if(AVL(root1))
        cout << "The Tree is AVL Tree"<<endl;
    else
        cout << "The Tree is not AVL Tree "<<endl;
    return 0;
}

실행 결과

첫 번째 트리는 모든 노드에서 좌우 높이 차이가 1 이하이므로 AVL 트리로 판별됩니다. 반면 두 번째 트리는 노드 12의 오른쪽 자식으로 13이 있고 그 아래 26이 추가되어 높이 차이가 2가 되므로 AVL 트리가 아닙니다.

The Tree is AVL Tree
The Tree is not AVL Tree

정리

이 프로그램은 각 노드에서 서브트리의 높이를 재귀적으로 계산하여 AVL 트리의 균형 조건을 검사합니다. 단순하지만 직관적인 방법으로, 시간 복잡도는 각 노드마다 높이를 다시 계산하므로 O(n²)입니다. 실무에서는 높이를 함께 저장하거나 후위 순회로 한 번에 계산하는 방식(O(n))으로 최적화할 수 있습니다.