[자료구조] 균형트리 - AVL Tree(Adelson-Velskii-Landis Tree)

AVL Tree(Adelson-Velskii-Landis Tree)

개념

AVL Tree는 기존의 BST에서 편향된 모양을 최대한 억제한 Tree이다. 음... 그림으로 말하자면,,,

위 그림처럼 입력이 10,20,30,40,50 순으로 입력되었다고 하자 내가 50Node를 탐색하려면 총 4번의 탐색이 필요하다 결국, 저렇게 편향된 BST는 그냥 선형 자료구조와 다름이 없다... 한 마디로 효율이 떨어진다는 것이다. 따라서 저러한 편향된 모양을 최대한 억제한 것이 바로 AVL이다.

균형인수(Balancing-Factor)

AVL은 그렇다면 규형을 어떤식으로 맞춰야 하는가... 바로 균형인수(Balancing-Factor)라는 새로운 자원을 통해 균형을 맞춘다. 균형인수는 특정 노드의 왼쪽 서브트리와 오른쪽 서브트리간의 높이 차이를 말하는 것이다.

 

식으로 표현하면,
BF = height(Node.left) - height(Node.right) 정도가 되겠다.

왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 빼는 것이다. 양수면 왼쪽 서브트리가 더 높이가 높은것이도 양수면 그 반대인 오른쪽 서브트리가 더 높다는 의미이다. 나는 전공수업에서 이 균형인수(BF)가 2 이상일때 즉 높이 차이가 2 이상일때, 균형을 맞춰 주는 것으로 배웠다.

회전

회전은 불균형으로 판명된 서브트리를 다시 균형을 맞추어 AVL Tree형태로 만드는 작업이다.

균형이 깨진 Node는 어떤식으로 다시 균형을 맞출까 4가지의 회전을 통해 해결 할 수 있다.
하나씩 설명을 하자면,,,

LL회전

단순회전으로 한번의 회전이 필요하다. 부모와 자식 Node의 원소의 위치를 교환하는 방법도 있지만, Node의 pointer를 바꾸는 것이 직관적이라 생각한다. 그림을 통해 확인해보면 이렇다...

해당 그림에서 A는 BF가 2로 균형이 깨졌다. 그의 서브 트리를 보아하니 모두 왼쪽으로 치우친 모양이다. 따라서 A에 대해 LL회전을 수행해야하는데, 그림에서 처럼 오른쪽으로 45도 회전한 것 처럼 보이지만, 사실은 pointer를 바꿔준 것이다.

우선 A의 왼쪽 서브트리를 B의 오른쪽 서브트리로 바꿔주고 B의 오른쪽 서브트리를 A로 바꾸어 준다. 이렇게 pointer를 변경해 주면 그림의 오른쪽 처럼 새롭게 균형이 맞아진 Tree 구조를 확인 할 수 있다.

RR회전

RR 회전도 LL회전과 같이 단순회전이다. 그리고 LL회전의 완벽한 대칭이다. 바로 그림을 통해 확인해 보자,,,

그림에서 처럼 A는 오른쪽으로 치우친 모양이다. LL 회전의 대칭이기 때문에 pointer를 바꾸는 것도 반대로 하면 된다.
우선 A의 오른쪽 서브트리를 B의 왼쪽 서브트리로 바꿔주고, B의 왼쪽 서브트리를 A로 바꿔주면 새로운 균형이 맞춰지고 위 그림의 오른쪽 처럼 균형이 맞아진 Tree 구조를 확인 할 수 있다.

LR회전

LR회전은 이중회전이다. 즉 두번의 회전이 필요한다. 단순회전을 적절히 2번 사용한 것이다. 이것도 그림을 보는 것이 빠르다...

LR회전은 2번의 단순회전으로 나뉜다. 우선 B에대해 부분 RR 회전을 수행하고 A에 대해 LL 회전을 수행한다. 아래 그림은 LR 회전을 단계별로 나눈 그림이다.

그림대로 pointer를 바꿔주면 회전이 완성된다.

RL회전

RL 회전도 마찬가지다. LR회전의 완벽한 대칭이다. 바로 그림을 통해서 보면,,,

RL 회전도 LR회전 처럼 두번의 회전을 통해 수행되는데, B에 대해 부분적인 LL회전을 수행하고, A에 대해 RR회전을 수행한다. 아래 그림은 자세한 단계별 회전 그림이다.

LR회전과 대칭이니까 pointer 바꾸는 것에 주의 하면 된다.

AVL의 회전은 LL과 RR회전을 중심으로 잘 이해하고 있다면 4가지 회전에 대해 어렵지 않게 이해할 수 있을 것이다.

설계

Node 설계

AVL Tree의 Node를 설계해 보자. 기존 BST의 전반적인 개념을 그대로 사용하기 때문에 BST의 Node를 그대로 이어가지만, 삽입,삭제마다 균형이 맞춰진 Tree인지 판단해야 하므로 BF(균형인수)라는 멤버 변수가 필요해졌다.

public class Node
{
    int data;
    int bf;
    Node left, right;

    public Node(int data)
    {
        this.data = data;
        this.bf = 0;
        this.left = null;
        this.right = null;
    }
}

나는 위 코드 처럼 Node를 설계했다.

AVL Tree 설계

AVL Tree 설계를 한다. 기본적인 삽입/삭제와 그것을 위한 여러 private 메소드를 설계했다. 아래는 AVL Tree의 스켈레톤 코드이다.

public class AVL
{
    Node root; //최상위 노드 pointer
    Node unbalNode; //밸런스가 깨진 Node를 참조하는 pointer
    Node parents; //unbalNode의 부모 Node를 참조하는 pointer

    public AVL() {} //생성자
    public boolean isEmpty() {} //Tree가 비어있는지를 반환하는 메소드
    public void print() {} //Tree를 inorder로 출력하는 메소드
    public void insert(int data) {} //AVL Tree의 삽입 메소드
    public void delete(int data) {} //AVL Tree의 삭제 메소드

    private void rotateLL() {} // LL회전 메소드
    private void rotateRR() {} // RR회전 메소드
    private void rotateLR() {} // LR회전 메소드
    private void rotateRL() {} // RL회전 메소드

    private Node insertBST(Node temp, int data) {} // BST 삽입 메소드
    private Node deleteBST(Node temp, int data) {} // BST 삭제 메소드

    private void updateBF(int data) {} // 삽입/삭제 후에 경로에 따라 BF를 업데이트 하는 메소드
    private int calcBF(Node temp) {} //매개변수로 들어온 Node의 BF를 계산하는 메소드

    private int getHeight(Node temp) {} //해당하는 Node의 높이를 반환
    private int getNumofNode(Node temp) {} //해당 Node의 하위 Node의 개수를 반환
    private Node findMaxNode(Node temp) {} //해당 노드의 하위노드 중 가장 큰 Node를 반환
    private Node findMinNode(Node temp) {} //해당 노드의 하위노드 중 가장 작은 Node를 반환
    private void inorder(Node temp) {} //중위 순회 메소드
}

이렇게 보니 코드가 상당히 길다...

삽입

AVL Tree의 삽입은 2단계로 나뉜다.

1. BST의 삽입
2. 균형 Tree인지 판단

1단계: AVL Tree는 BST에서 이어져 나온 Tree이기 때문에 BST의 삽입을 그대로 사용한다. 나는 이전에 BST를 구현한 적이 있어서 그 코드를 그대로 이용했다.
https://jsy-coding-blog.tistory.com/23

[자료구조] BST - 이진탐색 트리(Binary Search Tree)

이어서 2단계는 균형을 판단하는 것이다.

public void insert(int data)
{
    unbalNode = null;
    parents = null;

    root = insertBST(root, data);
    updateBF(data); //updateBF 메소드를 수행하면서 unbalNode와 parents노드를 초기화 함

    if(unbalNode == null) {return;} // 균형이 깨진 노드가 없으면 메소드 종료

    if(unbalNode.bf > 1) //균형이 깨진 Node의 왼쪽 부분에 문제가 있을 경우
    {
        if(calcBF(unbalNode.left) >= 0)
        {
            rotateLL(unbalNode, parents);
            return;
        }
        else
        {
            rotateLR(unbalNode, parents);
            return;
        }
    }
    else if(unbalNode.bf < -1) //균형이 깨진 Node의 오른쪽 부분에 문제가 있을 경우
    {
        if(calcBF(unbalNode.right) <= 0)
        {
            rotateRR(unbalNode, parents);
            return;
        }
        else
        {
            rotateRL(unbalNode, parents);
            return;
        }
    }
    else {return;}
}

해당 메소드의 순서는 삽입하고 나서 updateBF 메소드를 통해 균형이 깨진 Node와 그 부모노드를 갱신한다. 그 다음 if문을 따라 어떠한 회전을 할지를 판단하는 순서이다.

삭제

삭제도 마찬가지다. 2가지의 단계를 따르는데,

1. BST의 삭제
2. 균형 Tree 인지 판단

1단계: BST의 삭제 알고리즘도 이전에 구현해 놓았던 것을 그대로 사용하였다.

2단계는 아래 코드이다.

public void delete(int data)
{
    unbalNode = null;
    parents = null;

    root = deleteBST(root, data);
    updateBF(data); //updateBF 메소드를 수행하면서 unbalNode와 parents노드를 초기화 함

    if(unbalNode == null) {return;} // 균형이 깨진 노드가 없으면 메소드 종료

    if(unbalNode.bf > 1)
    {
        if(calcBF(unbalNode.left) >= 0) //균형이 깨진 Node의 왼쪽 부분에 문제가 있을 경우
        {
            rotateLL(unbalNode, parents);
            return;
        }
        else
        {
            rotateLR(unbalNode, parents); 
            return;
        }
    }
    else if(unbalNode.bf < -1)
    {
        if(calcBF(unbalNode.right) <= 0) //균형이 깨진 Node의 오른쪽 부분에 문제가 있을 경우
        {
            rotateRR(unbalNode, parents);
            return;
        }
        else
        {
            rotateRL(unbalNode, parents);
            return;
        }
    }
    else {return;}
}

놀랍게도 insert() 메소드와 완전 똑같다.

그 밖의 메소드

솔직히 삽입 삭제는 그렇게 중요하다고 생각하지 않는다. 나는 updateBF()와 4가지 회전 메소드가 더 중요하다고 생각한다.

회전 메소드

//Node unbal: 균형이 깨진 Node
//Node p: unbal Node의 부모 노드
private void rotateLL(Node unbal, Node p)
{
    boolean check = true; // 왼쪽 서브트리: true, 오른쪽 서브트리: false
    if(p != null) //unbal Node가 root가 아니면
    {check = p.left == unbal ? true : false;}

    Node sub = unbal.left;
    unbal.left = sub.right;
    sub.right = unbal;

    if(p == null) {root = sub;}
    else
    {
        if(check) {p.left = sub;}
        else {p.right = sub;}
    }
}

//Node unbal: 균형이 깨진 Node
//Node p: unbal Node의 부모 노드
private void rotateRR(Node unbal, Node p)
{
    boolean check = true; // 왼쪽 서브트리: true, 오른쪽 서브트리: false
    if(p != null) //unbal Node가 root가 아니면
    {check = p.left == unbal ? true : false;}

    Node sub = unbal.right;
    unbal.right = sub.left;
    sub.left = unbal;

    if(p == null) {root = sub;}
    else
    {
        if(check) {p.left = sub;}
        else {p.right = sub;}
    }
}

private void rotateLR(Node unbal, Node p)
{
    Node sub = unbal.left;
    Node q = unbal.left.right; // unbal Node가 root일때를 위한 temp Node

    rotateRR(sub, unbal);
    rotateLL(unbal, p);

    if(p == null)
    {root = q;}        
}

private void rotateRL(Node unbal, Node p)
{
    Node sub = unbal.right;
    Node q = unbal.right.left; // unbal Node가 root일때를 위한 temp Node

    rotateLL(sub, unbal);
    rotateRR(unbal, p);

    if(p == null)
    {root = q;}        
}

updateBF()

private void updateBF(int data)
{
    if(this.isEmpty()) {return;}

    Node p = root;
    Node q = null;

    // p가 leaf Node일때 까지 반복 \\
    while(!(p.left == null && p.right == null))
    {
        p.bf = calcBF(p); //p.setBF(calcBF(p));

        if(p.bf > 1 || p.bf < -1)
        {
            parents = q;
            unbalNode = p;
        }
        q = p;

        if(p.data > data) {p = p.left;}
        else {p = p.right;}

        if(p == null) {break;}
    }
}

전체 코드

코드가 너무 길어서 어떡할까 했는데, 일단 올리고 나중에 BST를 상속으로 다시 구현해야할 것 같다.(접은 글 참조)

300줄이나 되네....

package AVL;

public class AVL
{
	Node root;
	Node unbalNode; //균형이 깨진 Node를 참조하는 변수
	Node parents;  //균형이 깨진 Node의 부모 Node를 참조하는 변수
	
	public AVL()
	{
		root = null;
		unbalNode = null;
		parents = null;
	}
	
	public boolean isEmpty() {return root == null;}
	
	public void print() 
	{
		if(this.isEmpty()) {System.out.print("Tree is empty");}
		else {inorder(root);}
		
		System.out.println();
	}
	
	public void insert(int data)
	{
		unbalNode = null;
		parents = null;
		
		root = insertBST(root, data);
		updateBF(data); //updateBF 메소드를 수행하면서 unbalNode와 parents노드를 초기화 함
		
		if(unbalNode == null) {return;}
		
		if(unbalNode.bf > 1)
		{
			if(calcBF(unbalNode.left) >= 0)
			{
				rotateLL(unbalNode, parents);
				return;
			}
			else
			{
				rotateLR(unbalNode, parents);
				return;
			}
		}
		else if(unbalNode.bf < -1)
		{
			if(calcBF(unbalNode.right) <= 0)
			{
				rotateRR(unbalNode, parents);
				return;
			}
			else
			{
				rotateRL(unbalNode, parents);
				return;
			}
		}
		else {return;}
	}
	
	public void delete(int data)
	{
		unbalNode = null;
		parents = null;
		
		root = deleteBST(root, data);
		updateBF(data); //updateBF 메소드를 수행하면서 unbalNode와 parents노드를 초기화 함
		
		if(unbalNode == null) {return;}
		
		if(unbalNode.bf > 1)
		{
			if(calcBF(unbalNode.left) >= 0)
			{
				rotateLL(unbalNode, parents);
				return;
			}
			else
			{
				rotateLR(unbalNode, parents);
				return;
			}
		}
		else if(unbalNode.bf < -1)
		{
			if(calcBF(unbalNode.right) <= 0)
			{
				rotateRR(unbalNode, parents);
				return;
			}
			else
			{
				rotateRL(unbalNode, parents);
				return;
			}
		}
		else {return;}
	}
	
	private void rotateLL(Node unbal, Node p)
	{
		boolean check = true;;
		if(p != null)
		{check = p.left == unbal ? true : false;}
		
		Node sub = unbal.left;
		unbal.left = sub.right;
		sub.right = unbal;
		
		if(p == null) {root = sub;}
		else
		{
			if(check) {p.left = sub;}
			else {p.right = sub;}
		}
	}
	
	private void rotateRR(Node unbal, Node p)
	{
		boolean check = true;;
		if(p != null)
		{check = p.left == unbal ? true : false;}
		
		Node sub = unbal.right;
		unbal.right = sub.left;
		sub.left = unbal;
		
		if(p == null) {root = sub;}
		else
		{
			if(check) {p.left = sub;}
			else {p.right = sub;}
		}
	}
	
	private void rotateLR(Node unbal, Node p)
	{
		Node sub = unbal.left;
		Node q = unbal.left.right; // unbal Node가 root일때를 위한 temp Node
		
		rotateRR(sub, unbal);
		rotateLL(unbal, p);
		
		if(p == null)
		{root = q;}		
	}
	
	private void rotateRL(Node unbal, Node p)
	{
		Node sub = unbal.right;
		Node q = unbal.right.left; // unbal Node가 root일때를 위한 temp Node
		
		rotateLL(sub, unbal);
		rotateRR(unbal, p);
		
		if(p == null)
		{root = q;}		
	}
	
    private Node insertBST(Node temp, int data)
    {
        // 삽입할 노드를 탐색한다(재귀) \\
        if(temp == null) {temp = new Node(data);}
        else if(data < temp.data) {temp.left = insertBST(temp.left, data);}
        else if(data > temp.data) {temp.right = insertBST(temp.right, data);}

        return temp;
    }
	
	private Node deleteBST(Node temp, int data)
    {
        if(temp != null)
        {
            Node p;

            // 삭제할 노드까지 이동하는 과정(재귀) \\
            if(temp.data > data) {temp.left = deleteBST(temp.left, data);}
            else if(temp.data < data) {temp.right = deleteBST(temp.right, data);}

            // case 1: 삭제할 노드가 리프노드일 경우 \\
            else if(temp.left == null && temp.right == null)
                {temp = null;}

            // case 2-1: 삭제할 노드의 자식 노드가 1개(left)일 경우 \\
            else if(temp.right == null)
            {
                p = temp;
                temp = temp.left;
                p = null;
            }

            // case 2-2: 삭제할 노드의 자식 노드가 1개(right)일 경우 \\
            else if(temp.left == null)
            {
                p = temp;
                temp = temp.right;
                p = null;
            }
            // case 3: 삭제할 노드의 자식노드가 2개일 경우 \\
            else
            {
                //최소한의 균형을 위해 삭제하고자 하는 노드의 좌우 높이, 노드갯수를
                //비교해서 삭제를 유동적으로 실시함
                boolean flag; // left => true, right => false

                //case 3-1: 삭제할 노드의 왼쪽 subTree가 더 높을때\\
                if(getHeight(temp.left) > getHeight(temp.right))
                {
                    p = findMaxNode(temp.left);
                    flag = true;
                }

                //case 3-2: 삭제할 노드의 오른른쪽 subTree가 더 높을때\\
                else if(getHeight(temp.left) < getHeight(temp.right))
                {
                    p = findMinNode(temp.right);
                    flag = false;
                }

                //case 3-3: 양쪽의 subTree의 높이가 같을때\\
                else
                {
                    //case 3-3-1: 왼쪽 subTree의 node 개수가 더 많을때\\
                    if(getNumofNode(temp.left) >= getNumofNode(temp.right))
                    {
                        p = findMaxNode(temp.left);
                        flag = true;
                    }

                    //case 3-3-2: 오른쪽 subTree의 node 개수가 더 많을때\\
                    else
                    {
                        p = findMinNode(temp.right);
                        flag = false;
                    }
                }

                temp.data = p.data;

                if(flag) {temp.left = deleteBST(temp.left, p.data);}
                else {temp.right = deleteBST(temp.right, p.data);}
            }
        }
        return temp;
    }
	
	private void updateBF(int data)
	{
		if(this.isEmpty()) {return;}
		
		Node p = root;
		Node q = null;
		
		// p가 leaf Node일때 까지 반복 \\
		while(!(p.left == null && p.right == null))
		{
			p.bf = calcBF(p); //p.setBF(calcBF(p));
			
			if(p.bf > 1 || p.bf < -1)
			{
				parents = q;
				unbalNode = p;
			}
			q = p;
			
			if(p.data > data) {p = p.left;}
			else {p = p.right;}
			
			if(p == null) {break;}
		}
	}
	
	private int calcBF(Node temp)
	{
		if(temp == null) {return 0;}
		else
		{return getHeight(temp.left) - getHeight(temp.right);}
	}
	
    private int getHeight(Node temp)
    {
        if(temp == null) {return -1;}

        int leftSubTreeHeight = getHeight(temp.left) + 1;
        int rightSubTreeHegiht = getHeight(temp.right) + 1;

        return leftSubTreeHeight > rightSubTreeHegiht ? leftSubTreeHeight : rightSubTreeHegiht;
    }

    private int getNumofNode(Node temp)
    {
        if(temp == null) {return -1;}

        int leftSubTreeHeight = getHeight(temp.left) + 1;
        int rightSubTreeHegiht = getHeight(temp.right) + 1;

        return leftSubTreeHeight + rightSubTreeHegiht + 1;
    }

    private Node findMaxNode(Node temp)
    {
        if(temp.right == null) {return temp;}
        else {return findMaxNode(temp.right);}
    }

    private Node findMinNode(Node temp)
    {
        if(temp.left == null) {return temp;}
        else {return findMinNode(temp.left);}
    }
    
    private void inorder(Node temp)
    {
    	if (temp != null)
    	{
    		inorder(temp.left);
    		System.out.print(temp.data+" ");
    		inorder(temp.right);
    	}
    }
    
    public static void main(String[] args)
    {
    	int[] testcase = { 40, 11, 77, 33, 20, 90, 99, 70, 88, 80, 66, 10, 22, 30, 44, 55, 50, 60, 25, 49 };
    	
    	AVL avl = new AVL();
    	
    	//데이터 삽입\\
    	System.out.println("데이터 삽입");
    	for (int i = 0; i < 20; i++)
    	{ 
    		System.out.print(testcase[i]+"삽입: ");
    		avl.insert(testcase[i]); 
    		avl.print();
    	}
    	
    	//데이터 삭제\\
    	System.out.println("데이터 삭제");
    	for (int i = 0; i < 20; i++)
    	{ 
    		System.out.print(testcase[i]+"삭제: ");
    		avl.delete(testcase[i]); 
    		avl.print();
    	}
    }
}

아래는 github링크이다.

java:
https://github.com/JoSangYeon/Algorithm/blob/master/Tree/AVL/AVL.java

JoSangYeon/Algorithm

C++:
https://github.com/JoSangYeon/Algorithm/blob/master/Tree/AVL/20171706_AVLTree.cpp

JoSangYeon/Algorithm

결론

AVL확실히 BST보다 최대 높이에서 차이도 있고 그에 따라 탐색 시간이 빨라져서 효율이 좋다 할 수 있다.
전공 수업에서 이 AVL 트리의 구현이 과제로 나왔었는데, 정말 정신이 아득해 질 정도로 코딩했다... 처음에 C++로 구현하고 최근에 자바로 짰는데 C++로 작성했을땐 위 코드보다 훨씬 길었다... ㅍ_ㅍ;; 엄청 어렵기도 했고 근데, 그 과목을 수강하면서 교수님하고 조교님이 조언도 주시고 격려해 주셔서 나름 완성한것 같다.

 

다음은 다원트리의 기본인 B트리에 대해 포스팅하고자 한다.

 

틀린부분이나 궁금한 부분이 있으면 댓글에 남겨주세요!