균형 탐색 트리 (AVL)에 대하여

이번 포스트에서는 이전 포스트의 이진탐색트리의 보완버전인 균형탐색트리 (AVL)에 대하여 포스트 하도록 하겠습니다.

 

균형탐색트리(AVL Tree)

AVL 트리는 각 노드의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 이진탐색트리입니다.

삽입과 삭제 과정에서 높이차가 1 이상인 경우가 발생하면, 트리 회전을 통해 균형을 맞추는 동작을 수행합니다.

 

이 과정에서 각 노드의 높이 차를 저장하기 위해 각 노드는 균형 인자를 가집니다.

균형인자는 노드의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값을 가집니다. 공백 트리의 경우에는 -1로 정의됩니다. 따라서, AVL 트리는 균형인자가 -1, 0, 1 중 하나의 값을 가져야 합니다.

 

트리의 불균형

AVL 트리에서 불균형은 다음 4가지로 분류할 수 있습니다.

1. LL 불균형
2. RR 불균형
3. LR 불균형
4. RL 불균형

먼저 LL 불균형은 균형인자가 -1 ~ 1 을 벗어난 값을 가진 노드를 기준으로 균형인자가 양수이고, 왼쪽, 왼쪽 노드가 존재한다면 LL 불균형입니다. 이 경우 왼쪽으로 치우친 트리를 오른쪽으로 회전하여 균형을 맞추어 줍니다.

 

다음으로 RR 불균형은 균형인자가 -1 ~ 1 을 벗어난 값을 가진 노드를 기준으로 균형인자가 음수이고, 오른쪽, 오른쪽 노드가 존재한다면 RR 불균형입니다. 이 경우 오른쪽으로 치우친 트리를 왼쪽으로 회전하여 균형을 맞추어 줍니다.

 

세번째로 LR 불균형입니다. 마찬가지로 균형인자가 -1 ~ 1 을 벗어난 값을 가진 노드를 기준으로 균형인자가 양수이고, 왼쪽, 오른쪽 노드가 존재한다면 LR 불균형입니다. 이 경우에는 균형인자가 비정상인 노드의 왼쪽 자식노드를 왼쪽으로 회전하고, 균형인자가 비정상인 노드를 오른쪽으로 회전하여 균형을 맞추어 줍니다.

 

마지막으로 RL 불균형입니다. 균형인자가 -1 ~ 1 을 벗어난 값을 가진 노드를 기준으로 균형인자가 음수이고, 오른쪽, 왼쪽 노드가 존재한다면 RL 불균형입니다. 이 경우 균형인자가 비정상인 노드의 오른쪽 자식노드를 오른쪽으로 회전하고, 균형인자가 비정상인 노드를 왼쪽으로 회전하여 균형을 맞추어 줍니다.

 

트리 회전 구현

먼저 오른쪽 회전입니다.

균형인자가 비정상인 노드를 p, 그 노드의 왼쪽 자식노드를 c라고 할 때, 오른쪽 회전을 하게 되므로, p의 왼쪽 자식은 c의 오른쪽 자식으로 변경됩니다. 그리고 c의 오른쪽 자식은 p가 됩니다.

 

그리고 높이가 변경되었으므로 p와 c의 높이를 재계산해줍니다.

 

왼쪽 회전의 경우, p의 오른쪽 자식은 c의 왼쪽 자식으로 변경됩니다. 그리고 c의 왼쪽 자식은 p가 됩니다.

왼쪽 회전도 마찬가지로 p와 c의 높이를 재계산해줍니다.

 

typedef struct Node {
    int key, height;
    struct Node* left, *right;
} Node;
 
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
int height(Node* p) {
    if(p == nullptr)    return -1;
    return p->height;
}
 
Node* right(Node* p) {
    Node* c = p->left;
    p->left = c->right;
    c->right = p;
    p->height = 1 + max(height(p->left), height(p->right));
    c->height = 1 + max(height(c->left), height(c->right));
    return c;
}
 
Node* left(Node* p) {
    Node* c = p->right;
    p->right = c->left;
    c->left = p;
    p->height = 1 + max(height(p->left), height(p->right));
    c->height = 1 + max(height(c->left), height(c->right));
    return c;
}

AVL 트리의 삽입 및 삭제

먼저 AVL 트리의 삽입연산입니다.

이전 포스트에서 설명했던 이진탐색트리의 삽입연산에서 서브트리들의 높이 계산과 균형인자, 그에따른 불균형여부를 파악해 회전하는 코드가 추가됩니다.

 

Node* createNode(int key) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->key = key;
    p->height = 0;
    p->left = p->right = nullptr;
    return p;
}
 
Node* insert(Node* p, int key) {
    if(p == nullptr)    return createNode(key);                    //노드가 삽입될 위치를 찾음.
    if(key < p->key)    p->left = insert(p->left, key);            //키값이 현재 노드 키값보다 작기때문에 왼쪽 자식노드에서 삽입연산 시도
    else if(key > p->key)    p->right = insert(p->right, key);    //키값이 현재 노드 키값보다 크기때문에 오른쪽 자식노드에서 삽입연산 시도
    else return p;                                                //중복
 
    p->height = 1 + max(height(p->left), height(p->right));
    int bf = height(p->left) - height(p->right);
 
    if(bf > 1 && key < p->left->key)    return right(p);                //LL 불균형. 입력받은 key가 왼쪽 노드보다 작기때문에 왼쪽, 왼쪽으로 노드가 있음을 만족
    else if(bf < -1 && key > p->right->key)    return left(p);                //RR 불균형.
    else if(bf > 1 && key > p->left->key) {                                //LR 불균형.
        p->left = left(p->left);
        return right(p);
    }
    else if(bf < -1 && key < p->right->key) {                            //RL 불균형
        p->right = right(p->right);
        return left(p);
    }
    else return p;                                                        //균형이 맞음.
}

삭제연산도 마찬가지로 이진탐색트리의 삭제 연산을 거치고 균형이 맞는지 확인하고, 회전하는 코드가 추가됩니다.

 

Node* remove(Node* p, int key) {
    if(p == nullptr)    return nullptr;
    if(key < p->key) {
        p->left = remove(p->left, key);
        return p;
    }
    if(key > p->key) {
        p->right = remove(p->right, key);
        return p;
    }
    if(p->left == nullptr) {
        Node* t = p->right;
        free(p);
        return t;
    }
    if(p->right == nullptr) {
        Node* t = p->left;
        free(p);
        return t;
    }
    Node* next = p->right;
    while(next->left != nullptr)    next = next->left;
    p->key = next->key;
    p->right = remove(p->right, next->key);
    return p;
 
    p->height = 1 + max(height(p->left), height(p->right));
    int bf = height(p->left) - height(p->right);
 
    if (bf > 1 && key < p->left->key)    return right(p);
    else if (bf < -1 && key > p->right->key)    return left(p);
    else if (bf > 1 && key > p->left->key) {
        p->left = left(p->left);
        return right(p);
    }
    else if (bf < -1 && key < p->right->key) {
        p->right = right(p->right);
        return left(p);
    }
    else
        return p;
}

여기까지 균형탐색트리에 대하여 포스팅 해보았습니다.

 

다음은 이진 힙에 대한 내용을 포스트하도록 하겠습니다.