AVL Tree

AVL Tree란 앞에서 살펴보았던 이진 탐색 트리의 한 종류로, Height-Balanced Tree입니다.
이진 탐색 트리는 데이터의 삽입과 삭제 연산이 이루어지면서 트리의 구조가 비효율적으로 바뀌게 되고, 그에 따라 연산의 속도가 느려질 수 있다는 단점이 있었습니다.
AVL 트리는 그러한 단점을 보완한 트리 구조입니다. 자체적으로 각 노드의 왼쪽 부분 트리와 오른쪽 부분 트리의 높이를 조절하여 전체적으로 트리가 균등해지도록 합니다.

AVL트리는 기본적으로 이진 탐색 트리와 같습니다.
삽입, 삭제, 탐색 연산 모두 이진 탐색 트리와 같습니다.

그러나 AVL 트리의 각 노드에는 Balance Factor, BF 라는 변수가 추가됩니다.
$BF = (왼쪽 부분 트리의 높이) - (오른쪽 부분 트리의 높이)$로, 이 값이 -1, 0, 1의 값을 가져야 하며, 그렇지 않을 경우, 회전이라는 연산을 통해 이 값들을 조정합니다.

루트 노드인 A 노드의 경우, 왼쪽 부분 트리의 높이는 2이고, 오른쪽 부분 트리의 높이는 1이므로, BF의 값은 2 - 1 = 1 입니다.
말단 노드인 D 노드의 경우, 왼쪽 부분 트리와 오른쪽 부분 트리 모두 높이가 0이므로 BF의 값은 0 - 0 = 0이 됩니다.

위 트리의 경우, A 노드의 왼쪽 부분 트리의 높이는 2이고, 오른쪽 부분 트리의 높이는 0으로, BF = 2 - 0 = 2의 값을 가집니다.
AVL 트리는 BF의 값이 0, -1, 1 이 아닌 경우, 트리 구조가 연산에 있어서 비효율적이라고 판단하고, 회전이라는 연산을 통해 모든 노드의 BF 값을 0, -1, 1의 값을 가지게끔 합니다.

회전 연산에는 4가지가 있습니다.

LL

LL 연산의 경우, A의 왼쪽 자식 B의 Bf 값이 1 이상인 경우에 사용됩니다.
간단하게 노드의 연결 방향이 차례대로 두번 왼쪽인 경우를 뜻합니다.
연산은 다음과 같습니다.

A 노드를 B 노드의 오른쪽 자식 노드로 설정
B 노드를 기존 A노드의 부모 노드와 연결

B 노드의 오른쪽 자식 노드가 존재하는 경우, 위와 동일하나, 추가적으로 B 노드의 오른쪽 자식 노드를 A 노드의 왼쪽 자식노드로 옮깁니다.
~~기술력 문제로.. 더 나은 예시를 만들어 보겠습니다..~~

LR

LR 연산의 경우, A의 왼쪽 자식 B의 Bf 값이 -1 이하인 경우에 사용됩니다.
간단하게 노드의 연결 방향이 차례대로 왼쪽, 오른쪽인 경우 입니다.

이 경우 연산은 다음과 같습니다.

A 노드의 왼쪽 자식 노드를 C로 설정
C 노드의 왼쪽 자식 노드를 B로 설정
- 이 과정에서 C 노드의 왼쪽 자식 노드는 B 노드의 자식 노드로 이동

해당 연산을 진행한 뒤에는 LL 연산의 경우와 같은 구조가 되는데, 이때 LL 연산을 진행합니다.

RR, RL 연산 모두 앞서 말씀드린 두 연산에서 방향만 바꾼 것입니다.

AVL 트리는 데이터의 추가, 삭제 후에 각 노드의 bf 값을 확인합니다.
만약 bf 값이 적절하지 않으면 각 상황에 맞는 회전 연산을 통해 전체 트리를 균일하게 유지합니다.

code

#include<iostream>
#include<ostream>

#define inorder 0
#define preorder 1
#define postorder 2

using namespace std;

class Underflow {};

template <typename T>
class Node {
    public:
    T data;
    Node<T> *left, *right;
    Node<T>() : left(nullptr), right(nullptr)  {}
    Node<T>(T value) : data(value), left(nullptr), right(nullptr) {}
};

template <typename T>
class AVLTree {
    public:
    int size;
    Node<T> *root;

    AVLTree<T>() : size(0), root(nullptr) {}
    
    bool search(T value){
        Node<T> *parent = nullptr;
        Node<T> *ptr = returnNodePosition(value, root, parent);
        if(ptr == nullptr)
            return false;
        return true;
    }

    void insert(T value){
        Node<T> *parent = nullptr;
        Node<T> *insertedPosition = returnNodePosition(value, root, parent);
        if(parent == nullptr)
            root = new Node<T>(value);
        else if(parent->data == value){
            cout << value << " already exist.\n";
            return;
        }
        else{
            Node<T> *newNode = new Node<T>(value);
            if(value < parent->data)
                parent->left = newNode;
            else
                parent->right = newNode;
        }
        size++;
        cout << value << " inserted.\n";
        sort();
    }

    void remove(T value){
        try{
            if(size <= 0) throw Underflow();
            Node<T> *parent = nullptr;
            Node<T> *removedPosition = returnNodePosition(value, root, parent);
            if(removedPosition == nullptr){
                cout << value << " does not exist.\n";
                return;
            }
            //자식노드가 없는 경우 : 그냥 제거
            if(removedPosition->left == nullptr && removedPosition->right == nullptr){
                if(parent->data > value)
                    parent->left = nullptr;
                else
                    parent->right = nullptr;
                delete removedPosition;
            }
            //하나만 있는 경우 : 부모 노드와 자식 노드를 연결
            else if(removedPosition->left != nullptr && removedPosition->right == nullptr){
                if(parent->data > value)
                    parent->left = removedPosition->left;
                else
                    parent->right = removedPosition->left;
                delete removedPosition;
            }
            else if(removedPosition->left == nullptr && removedPosition->right != nullptr){
                if(parent->data > value)
                    parent->left = removedPosition->right;
                else
                    parent->right = removedPosition->right;
                delete removedPosition;
            }
            //둘 다 있는 경우 : LeftMost 노드와 교체
            else{
                Node<T> *ptr = removedPosition->left, *parent = removedPosition;
                while(ptr->right != nullptr){
                    parent = ptr;
                    ptr = ptr->right;
                }
                removedPosition->data = ptr->data;
                if(parent == removedPosition)
                    parent->left = nullptr;
                else
                    parent->right = nullptr;
                delete ptr;
            }
            cout << value << " removed\n";
            size--;
            sort();
        }
        catch(Underflow e){
            cout << "Underflow occurs.\n";
            exit(0);
        }
    }

    void print(int N){
        if(N == inorder){
            cout << "inorder : ";
            inOrder(root);
        }
        else if(N == preorder){
            cout << "preorder : ";
            preOrder(root);
        }
        else if(N == postorder){
            cout << "postorder : ";
            postOrder(root);
        }
        cout << '\n';
    }
    private:
    // value 값이 존재하지 않을 경우, 리턴 값 : nullptr, parent 변수 : 해당 위치의 부모 노드
    // value 값이 존재하는 경우, 리턴 값 : 해당 노드, parent 변수 : 해당 노드의 부모 노드
    Node<T> *returnNodePosition(T value, Node<T> *current, Node<T> *&parent){
        Node<T> *child_ptr = current;
        while(child_ptr != nullptr){
            if(child_ptr->data == value){
                return child_ptr;
            }
            parent = child_ptr;
            if(child_ptr->data < value)
                child_ptr = child_ptr->right;
            else
                child_ptr = child_ptr->left;
        }
        return child_ptr;
    }
    
    

    void RR(Node<T> *current, Node<T> *&parrent){
        Node<T> *newCurrent = current->right;
        if(parrent == nullptr)
            root = newCurrent;
        else{
            if(parrent->data > current->data)
                parrent->left = newCurrent;
            else
                parrent->right = newCurrent;
        }
        current->right = newCurrent->left;
        newCurrent->left = current;
    }

    void LL(Node<T> *current, Node<T> *&parrent){
        Node<T> *newCurrent = current->left;
        if(parrent == nullptr)
            root = newCurrent;
        else{
            if(parrent->data > current->data)
                parrent->left = newCurrent;
            else
                parrent->right = newCurrent;
        }
        current->left = newCurrent->right;
        newCurrent->right = current;
    }

    void RL(Node<T> *current, Node<T> *&parrent){
        Node<T> *rightChild = current->right;
        current->right = rightChild->left;
        rightChild->left = current->right->right;
        current->right->right = rightChild;
        RR(current, parrent);
    }

    void LR(Node<T> *current, Node<T> *&parrent){
        Node<T> *leftChild = current->left;
        current->left = leftChild->right;
        leftChild->right = current->left->left;
        current->left->left = leftChild;
        LL(current, parrent);
    }
    int findHieght(Node<T> *current){
        if(current == nullptr)
            return 0;
        int temp1 = 0, temp2 = 0;
        if(current->left != nullptr)
            temp1 = findHieght(current->left);
        if(current->right != nullptr)
            temp2 = findHieght(current->right);
        return 1 + (temp1 > temp2 ? temp1 : temp2);
    }

    int getBf(Node<T> *current){
        int height_L = 0,height_R = 0;
        if(current->left != nullptr)
            height_L = findHieght(current->left);
        if(current->right != nullptr)
            height_R = findHieght(current->right);
        return height_L - height_R;
    }

    void sort(){
        Node<T> *parent = nullptr;
        sortNode(root, parent);
    }
    
    void sortNode(Node<T> *&current, Node<T> *&parent){
        if(current == nullptr || (current->left == nullptr && current->right == nullptr))
            return;
        sortNode(current->left, current);
        sortNode(current->right, current);
        int bf = getBf(current);
        if(bf == 0 || bf == 1 || bf == -1)
            return;
        if(bf > 1){
            if(getBf(current->left) < 0)
                LR(current,parent);
            else
                LL(current,parent);
        }
        else{
            if(getBf(current->right) > 0)
                RL(current, parent);
            else
                RR(current,parent);
        }
    }

    void inOrder(Node<T>* current){
        if(current != nullptr){
            inOrder(current->left);
            cout << "[ " << current->data << " ] ";
            inOrder(current->right);
        }
    }
    void preOrder(Node<T>* current){
        if(current != nullptr){
            cout << "[ " << current->data << " ] ";
            preOrder(current->left);
            preOrder(current->right);
        }
    }
    void postOrder(Node<T>* current){
        if(current != nullptr){
            postOrder(current->left);
            postOrder(current->right);
            cout << "[ " << current->data << " ] ";
        }
    }
};

int main(){
    AVLTree<int> test;
    int a[] = {9,4,3,1,11,15,13,12,14,5,6};
    for(int k : a){
        test.insert(k);
        test.print(preorder);
    }
    test.remove(9);
    test.print(preorder);
    test.remove(12);
    test.print(preorder);
    test.remove(5);
    test.print(preorder);
    return 0;
}

기본적으로 이진 탐색 트리의 코드에 bf값, 회전 연산의 코드만 추가하면 됩니다.
그래서 저번에 올린 이진 탐색 트리 코드를 그대로 가져오면 되는데, 약간의 변경사항이 있습니다.
그래서 변경사항과 회전 연산 코드를 중점으로 살펴보겠습니다.

returnNodePosition

// value 값이 존재하지 않을 경우, 리턴 값 : nullptr, parent 변수 : 해당 위치의 부모 노드
    // value 값이 존재하는 경우, 리턴 값 : 해당 노드, parent 변수 : 해당 노드의 부모 노드
    Node<T> *returnNodePosition(T value, Node<T> *current, Node<T> *&parent){
        Node<T> *child_ptr = current;
        while(child_ptr != nullptr){
            if(child_ptr->data == value){
                return child_ptr;
            }
            parent = child_ptr;
            if(child_ptr->data < value)
                child_ptr = child_ptr->right;
            else
                child_ptr = child_ptr->left;
        }
        return child_ptr;
    }

먼저 삽입, 삭제, 탐색 연산에 공통적으로 사용되는 함수입니다.
이 함수는 특정 값을 가진 노드의 포인터를 반환하고, parent 변수는 해당 노드의 부모 노드가 됩니다.
특정 값이 존재하지 않으면, nullptr를 반환하고, parent 변수는 해당 위치의 부모 노드가 됩니다.

탐색

returnNodePosition 함수의 반환 값이 nullptr이 아닌 경우, true를 리턴합니다.

삽입

returnNodePosition 함수의 반환 값이 nullptr인 경우, parent 노드의 자식 노드로서 value값을 가진 새로운 노드를 추가합니다.

삭제

returnNodePosition 함수의 반환 값이 nullptr이 아닌 경우, 이진 탐색 트리의 삭제 연산과 마찬가지로,

자식 노드가 없는 경우
하나의 자식 노드를 가지는 경우
두 개의 자식 노드를 가지는 경우
각 상황에 따라 알맞은 연산을 진행합니다.

getBF

    int findHieght(Node<T> *current){
            if(current == nullptr)
                return 0;
            int temp1 = 0, temp2 = 0;
            if(current->left != nullptr)
                temp1 = findHieght(current->left);
            if(current->right != nullptr)
                temp2 = findHieght(current->right);
            return 1 + (temp1 > temp2 ? temp1 : temp2);
        }
    int getBf(Node<T> *current){
        int height_L = 0,height_R = 0;
        if(current->left != nullptr)
            height_L = findHieght(current->left);
        if(current->right != nullptr)
            height_R = findHieght(current->right);
        return height_L - height_R;
    }

해당 노드의 bf 값을 반환합니다.

sort

    void sort(){
        Node<T> *parent = nullptr;
        sortNode(root, parent);
    }

루트 노드를 시작으로 sortNode 함수를 실행하는 함수입니다.
적절한 회전 연산을 통해 각 노드의 bf 값을 조절합니다.
삽입, 삭제 연산 과정에서 항상 실행되도록 하였습니다.

sortNode

    //각 노드의 bf 값을 확인하고, 적절하지 않은 경우, 회전 연산 진행
    void sortNode(Node<T> *&current, Node<T> *&parent){
        if(current == nullptr || (current->left == nullptr && current->right == nullptr))
            return;
        sortNode(current->left, current);
        sortNode(current->right, current);
        int bf = getBf(current);
        if(bf == 0 || bf == 1 || bf == -1)
            return;
        if(bf > 1){
            if(getBf(current->left) < 0)
                LR(current,parent);
            else
                LL(current,parent);
        }
        else{
            if(getBf(current->right) > 0)
                RL(current, parent);
            else
                RR(current,parent);
        }
    }

먼저 postorder 순회를 진행합니다.
getBF 함수를 통해서 방문한 노드의 bf 값을 확인합니다.
bf 값이 적절하지 않은 경우, 상황에 알맞게 회전 연산을 진행합니다.
예를 들어 LL 연산과 LR 연산의 구분은 현재 왼쪽 자식 노드의 bf 값을 기준으로 정했습니다.

회전 연산

    void RR(Node<T> *current, Node<T> *&parrent){
        Node<T> *newCurrent = current->right;
        if(parrent == nullptr)
            root = newCurrent;
        else{
            if(parrent->data > current->data)
                parrent->left = newCurrent;
            else
                parrent->right = newCurrent;
        }
        current->right = newCurrent->left;
        newCurrent->left = current;
    }

    void LL(Node<T> *current, Node<T> *&parrent){
        Node<T> *newCurrent = current->left;
        if(parrent == nullptr)
            root = newCurrent;
        else{
            if(parrent->data > current->data)
                parrent->left = newCurrent;
            else
                parrent->right = newCurrent;
        }
        current->left = newCurrent->right;
        newCurrent->right = current;
    }

    void RL(Node<T> *current, Node<T> *&parrent){
        Node<T> *rightChild = current->right;
        current->right = rightChild->left;
        rightChild->left = current->right->right;
        current->right->right = rightChild;
        RR(current, parrent);
    }

    void LR(Node<T> *current, Node<T> *&parrent){
        Node<T> *leftChild = current->left;
        current->left = leftChild->right;
        leftChild->right = current->left->left;
        current->left->left = leftChild;
        LL(current, parrent);
    }

각 회전 연산의 코드입니다.

result

int main(){
    AVLTree<int> test;
    int a[] = {9,4,3,1,11,15,13,12,14,5,6};
    for(int k : a){
        test.insert(k);
        test.print(preorder);
    }
    test.remove(9);
    test.print(preorder);
    test.remove(12);
    test.print(preorder);
    test.remove(5);
    test.print(preorder);
    return 0;
}

9 inserted.
preorder : [ 9 ]
4 inserted.
preorder : [ 9 ] [ 4 ]
3 inserted.
preorder : [ 4 ] [ 3 ] [ 9 ]
1 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 9 ]
11 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 9 ] [ 11 ]
15 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 15 ]
13 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 15 ] [ 13 ]
12 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 13 ] [ 12 ] [ 15 ]
14 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 13 ] [ 11 ] [ 9 ] [ 12 ] [ 15 ] [ 14 ]
5 inserted.
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 9 ] [ 5 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
6 inserted.
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 9 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
9 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
12 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 14 ] [ 13 ] [ 15 ]
5 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 14 ] [ 13 ] [ 15 ] 

9,4,3,1,11,15,13,12,14,5,6 을 순서대로 삽입한 결과 입니다.

9, 12, 5를 순서대로 삭제한 결과입니다.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
AVL 트리의 삽입, 삭제 연산 과정은 이 사이트에서 확인할 수 있습니다.
AVL 트리 뿐만 아니라 다양한 자료구조의 연산을 시각화하여 나타냈기에, 많은 도움이 될 것이라고 생각합니다.

이승준

Contact