Soongle's Morgorithm

AVL 트리 본문

Data Structure/Tree

AVL 트리

Soongle 2019. 6. 13. 17:50

AVL 트리란, George Adelson-Velsky와 Evgenii Landis가 발표한 최초의 균형잡힌 이진트리(balanced binary tree)이다.

AVL 트리 클래스를 Node구조체를 사용한 링크 표현법으로 구현하였다.

AVL 트리의 가장 핵심적인 기술은 바로 회전(Rotation)이다.

RR, LL, RL, LR 네 가지 경우에서의 회전을 통해 트리 전체의 좌우 균형을 맞추기 때문이다.

이렇게 균형이 맞춰진 트리는 값을 탐색할 때 최악의 경우에도 O(log n)의 시간안에 탐색을 끝낼 수 있다.

각각의 회전을 해야하는 경우는 아래와 같다

  1. RR : 오른쪽, 오른쪽으로 치우친 경우 → 현재 노드 기준으로 왼쪽으로 회전시킨다

  2. LL : 왼쪽, 왼쪽으로 치우친 경우 → 현재 노드 기준으로 오른쪽으로 회전시킨다

  3. RL : 오른쪽, 왼쪽으로 치우친 경우 → 자식노드 기준으로 오른쪽 회전시킨 후, 현재 노드 기준으로 왼쪽 회전시킨다

  4. LR : 왼쪽, 오른쪽으로 치우친 경우 → 자식노드 기준으로 왼쪽 회전시킨 후, 현재 노드 기준으로 오른쪽 회전시킨다

네 가지 회전 소스코드

Node* RR(Node* parent)
{
    Node* child = parent->right;
    parent->right = child->left;
    child->left = parent;
    return child;
}
Node* LL(Node* parent)
{
    Node* child = parent->left;
    parent->left = child->right;
    child->right = parent;
    return child;
}
Node* LR(Node* parent)
{
    Node* child = parent->left;
    parent->left = RR(child);
    return LL(parent);
}
Node* RL(Node* parent)
{
    Node* child = parent->right;
    parent->right = LL(child);
    return RR(parent);
}

회전을 통해 균형을 맞추는 balance 함수

factor 변수는 tmp의 균형인수이다 (왼쪽자식의 높이 - 오른쪽자식의 높이)

void balance(Node* &tmp)
{
    if(tmp != NULL)
    {
        int factor = diff(tmp);
        if(factor > 1)
        {
            if(diff(tmp->left) > 0)
            {
                tmp = LL(tmp);
                cout<<"LL rotation"<<endl;
            }
            else
            {
                tmp = LR(tmp);
                cout<<"LR rotation"<<endl;
            }
        }
        else if(factor < -1)
        {
            if(diff(tmp->right) > 0)
            {
                tmp = RL(tmp);
                cout<<"RL rotation"<<endl;
            }
            else
            {
                tmp = RR(tmp);
                cout<<"RR rotation"<<endl;
            }
        }    
    }
}

삽입과 삭제 연산을 한 뒤 항상 균형을 맞추어 주어야 한다

더보기 
bool recur_insert(Node* &tree, int item)
{
    bool flag;
    if(tree == NULL)
    {
        tree = new Node;
        tree->data = item;
        tree->left = NULL;
        tree->right = NULL;
        return true;
    }
    if(item == tree->data) return false;
    else if(item < tree->data)
    {
        flag = recur_insert(tree->left, item);
        balance(tree);
        return flag;
    }
    else
    {
        flag = recur_insert(tree->right, item);
        balance(tree);
        return flag;
    }
}

bool recur_remove(Node* &tree, int item)
{
    if(tree == NULL) return false;
    if(tree->data == item)
    {
        Node* tmp;
        if(tree->left == NULL)
        {
            tmp = tree;
            tree = tree->right;
            delete tmp;
            balance(tree);
            return true;
        }
        else if(tree->right == NULL)
        {
            tmp = tree;
            tree = tree->left;
            delete tmp;
            balance(tree);
            return true;
        }
        else
        {
            tmp = tree->right;
            while(tmp != NULL)
            {
                tmp = tmp->left;
            }
            tree->data = tmp->data;
            recur_remove(tree->right, tmp->data);
            balance(tree);
            return true;
        }
    }
    else if(tree->data > item) return recur_remove(tree->left, item);
    else return recur_remove(tree->right, item);
}

소스코드

더보기 
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

struct Node
{
    int data;
    Node* left;
    Node* right;
};

class AVL_Tree
{
public:
    AVL_Tree();
    int height();
    bool insert(int item);
    bool remove(int item);
    void display();
    void inorder();
    void preorder();
    void postorder();

private:
    Node* root;
};

AVL_Tree::AVL_Tree()
{
    root = NULL;
}
int recur_height(Node* tree)
{
    if(tree == NULL) return 0;
    return max(recur_height(tree->left), recur_height(tree->right)) + 1;
}
int AVL_Tree::height()
{
    return recur_height(root);
}
int diff(Node* tree)
{
    return recur_height(tree->left) - recur_height(tree->right);
}
Node* RR(Node* parent)
{
    Node* child = parent->right;
    parent->right = child->left;
    child->left = parent;
    return child;
}
Node* LL(Node* parent)
{
    Node* child = parent->left;
    parent->left = child->right;
    child->right = parent;
    return child;
}
Node* LR(Node* parent)
{
    Node* child = parent->left;
    parent->left = RR(child);
    return LL(parent);
}
Node* RL(Node* parent)
{
    Node* child = parent->right;
    parent->right = LL(child);
    return RR(parent);
}
void balance(Node* &tmp)
{
    if(tmp != NULL)
    {
        int factor = diff(tmp);
        if(factor > 1)
        {
            if(diff(tmp->left) > 0)
            {
                tmp = LL(tmp);
                cout<<"LL rotation"<<endl;
            }
            else
            {
                tmp = LR(tmp);
                cout<<"LR rotation"<<endl;
            }
        }
        else if(factor < -1)
        {
            if(diff(tmp->right) > 0)
            {
                tmp = RL(tmp);
                cout<<"RL rotation"<<endl;
            }
            else
            {
                tmp = RR(tmp);
                cout<<"RR rotation"<<endl;
            }
        }    
    }
}
bool recur_insert(Node* &tree, int item)
{
    bool flag;
    if(tree == NULL)
    {
        tree = new Node;
        tree->data = item;
        tree->left = NULL;
        tree->right = NULL;
        return true;
    }
    if(item == tree->data) return false;
    else if(item < tree->data)
    {
        flag = recur_insert(tree->left, item);
        balance(tree);
        return flag;
    }
    else
    {
        flag = recur_insert(tree->right, item);
        balance(tree);
        return flag;
    }
}
bool AVL_Tree::insert(int item)
{
    return recur_insert(root, item);
}
bool recur_remove(Node* &tree, int item)
{
    if(tree == NULL) return false;
    if(tree->data == item)
    {
        Node* tmp;
        if(tree->left == NULL)
        {
            tmp = tree;
            tree = tree->right;
            delete tmp;
            balance(tree);
            return true;
        }
        else if(tree->right == NULL)
        {
            tmp = tree;
            tree = tree->left;
            delete tmp;
            balance(tree);
            return true;
        }
        else
        {
            tmp = tree->right;
            while(tmp != NULL)
            {
                tmp = tmp->left;
            }
            tree->data = tmp->data;
            recur_remove(tree->right, tmp->data);
            balance(tree);
            return true;
        }
    }
    else if(tree->data > item) return recur_remove(tree->left, item);
    else return recur_remove(tree->right, item);
}
bool AVL_Tree::remove(int item)
{
    return recur_remove(root, item);
}

void recur_display(Node* tree)
{
    if(tree != NULL)
    {
        recur_display(tree->left);
        cout<<"<"<<tree->data<<"> ";
        recur_display(tree->right);
    }
}
void AVL_Tree::display()
{
    if(root == NULL) cout<<"Tree is Empty"<<endl;
    else
    {
        recur_display(root);
        cout<<endl;
    }
}
void recur_inorder(Node* tree)
{
    if(tree != NULL)
    {
        recur_inorder(tree->left);
        cout<<tree->data<<" ";
        recur_inorder(tree->right);
    }
}
void AVL_Tree::inorder()
{
    if(root == NULL) cout<<"Tree is Empty"<<endl;
    else
    {
        cout<<" => : ";
        recur_inorder(root);
        cout<<endl;
    }
}
void recur_preorder(Node* tree)
{
    if(tree != NULL)
    {
        cout<<tree->data<<" ";
        recur_preorder(tree->left);
        recur_preorder(tree->right);
    }
}
void AVL_Tree::preorder()
{
    if(root == NULL) cout<<"Tree is Empty"<<endl;
    else
    {
        cout<<" => : ";
        recur_preorder(root);
        cout<<endl;
    }
}
void recur_postorder(Node* tree)
{
    if(tree != NULL)
    {
        recur_postorder(tree->left);
        recur_postorder(tree->right);
        cout<<tree->data<<" ";
    }
}
void AVL_Tree::postorder()
{
    if(root == NULL) cout<<"Tree is Empty"<<endl;
    else
    {
        cout<<" => : ";
        recur_postorder(root);
        cout<<endl;
    }
}

int main()
{
    AVL_Tree avl;
    string command;
    int item;
    while(1)
    {
        cin>>command;
        if(command == "insert")
        {
            cin >> item;
            avl.insert(item);
        }
        if(command == "remove")
        {
            cin >> item;
            avl.remove(item);
        }
        else if(command == "display")
        {
            avl.display();
        }
        else if(command == "inorder")
        {
            avl.inorder();
        }
        else if(command == "preorder")
        {
            avl.preorder();
        }
        else if(command == "postorder")
        {
            avl.postorder();
        }
        else if(command == "exit")
        {
            break;
        }
    }
    return 0;
}

전체 소스코드

저작자표시 (새창열림)

'Data Structure > Tree' 카테고리의 다른 글

이진 탐색 트리(Binary Search Tree)  (1) 2019.06.13
'Data Structure/Tree' Related Articles more
Comments