[자료구조] AVL트리 [JAVA]

AVL 트리 개념

AVL트리는 이전 바이너리트리의 문제점인 밸런스가 맞지 않을 수 있다는점을 보완한 트리 구조이다.

BF(Balance Factor)라는 변수를 가지며 이 변수값을 이용하여 트리 Rotation하여 균형을 맞춘다.

 

• BF(Balance Factor) : 균형인수라고도 부르며, (왼쪽 서브트리의 높이) - (오른쪽 서브 트리 높이)값

Rotate 종류

LL Rotate

BF가 2일때, 왼쪽으로 치우친 경우에서 자식 노드가 왼쪽 -> 왼쪽순서로 있는 경우

BF가 비대칭인 서브트리를 오른쪽으로 한번 회전한다. 즉 서브트리 루트노드의 왼쪽 자식노드를 루트노드로 지정한다.

 

RR Rotate

BF가 -2일때, 오른쪽으로 치우친 경우에서 자식 노드가 오른쪽 -> 오른쪽순서로 있는 경우

BF가 비대칭인 서브트리를 왼쪽으로 한번 회전한다. 즉 서브트리 루트노드의 오른쪽 자식노드를 루트노드로 지정한다.

 

LR Rotate

BF가 2일때, 왼쪽으로 치우친 경우에서 자식노드가 왼쪽 -> 오른쪽 순서로 있는 경우

BF가 비대칭인 서브트리를 왼쪽으로 한번, 오른쪽으로 한번 회전한다.  즉 서브트리의 리프노드를 루트노드로 지정한다.

 

RL Rotate

BF가 -2일때, 오른쪽으로 치우친 경우에서 자식노드가 오른쪽 -> 왼쪽 순서로 있는 경우

BF가 비대칭인 서브트리를 오른쪽으로 한번, 왼쪽으로 한번 회전한다.  즉 서브트리의 리프노드를 루트노드로 지정한다.

 

AVL트리 구현

public class AVLTree {
    public class Node
    {
        Integer data;
        private Node left;
        private Node right;
        private int height;

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public void setHeight(int h)
        {
            height = h;
        }
        public int getHeight()
        {
            return height;
        }
    }

    public Node root;

    public Node Search(int val)
    {
        return Search(root,val);
    }

    private Node Search(Node root, int val)
    {
        if(root.data == null)
            return root;

        if(root.data == val)
            return root;

        if(val > root.data)
        {
            if(root.right == null)
                root.right = new Node();
            return Search(root.right, val);
        }

        if(root.left == null)
            root.left = new Node();
        return Search(root.left , val);
    }

    //root: now node, using for recursive function, val: value to be inserted
    public Node Insert(Node root, int val)
    {
        if(root == null) {
            root = new Node();
            root.data = new Integer(val);
        }
        else
        {
            if(val > root.data)
            {
                root.right = Insert(root.right,val);
                root = setBalance(root);
            }
            else
            {
                root.left = Insert(root.left,val);
                root = setBalance(root);
            }
        }

        return root;
    }

    //root: now node, using for recursive function, val: value to be deleted
    public Node Delete(Node root, int val)
    {
       if(root == null)
           return null;

       if(val > root.data)
       {
           root.right = Delete(root.right,val);
           root = setBalance(root);
       }
       else if(val < root.data)
       {
           root.left = Delete(root.left,val);
           root = setBalance(root);
       }
       else
       {
           if(root.left != null)
           {
               Node temp = root.left;

               while(temp.right != null)
                    temp = temp.right;

               root.data = temp.data;
               root.left = Delete(root.left,temp.data);

               root = setBalance(root);
           }
           else
               return root.right;
       }

       return root;
    }

    private Node setBalance(Node root)
    {
        int bf = getBf(root);
        if(bf >= 2)
        {
            if(getBf(root.left) >= 1)
                root = LL(root);
            else
                root = LR(root);
        }
        else if(bf <= -2)
        {
            if(getBf(root.right) <= -1)
                root = RR(root);
            else
                root = RL(root);
        }
        setHeight(root);
        return root;
    }

    private int setHeight(Node root)
    {
        int lh = 0,rh = 0;

        if(root.left != null)
            lh = root.left.height + 1;
        if(root.right != null)
            rh = root.right.height + 1;

        return lh > rh ? lh : rh;
    }

    private int getBf(Node root)
    {
        int lf = 0, rf = 0;
        if(root.left != null)
            lf = root.left.height;
        if(root.right != null)
            rf = root.right.height;
        return lf - rf;
    }


    private Node RotateRight(Node root)
    {
        int h = root.height;
        Node temp = root.left;
        root.left = temp.right;
        temp.right = root;

        temp.setHeight(h);

        return temp;
    }

    private Node RotateLeft(Node root)
    {
        int h = root.height;
        Node temp = root.right;
        root.right = temp.left;
        temp.left = root;

        temp.setHeight(h);

        return temp;
    }

    private Node RR(Node root)
    {
        root = RotateLeft(root);
        return root;
    }

    private Node LL(Node root)
    {
        root= RotateRight(root);
        return root;
    }

    private Node LR(Node root)
    {
        root.left = RotateLeft(root.left);
        root = RotateRight(root);
        return root;
    }

    private Node RL(Node root)
    {
        root.right = RotateRight(root.right);
        root = RotateLeft(root);
        return root;
    }

    public void printInorder(Node root)
    {
        if(root.left != null)
            printInorder(root.left);
        System.out.print(root.data + " ");
        if(root.right != null)
            printInorder(root.right);
    }
    public void printPreOrder(Node root)
    {
        System.out.print(root.data + " ");
        if(root.left != null)
            printPreOrder(root.left);
        if(root.right != null)
            printPreOrder(root.right);
    }
    public void printPostOrder(Node root)
    {
        if(root.left != null)
            printPostOrder(root.left);
        if(root.right != null)
            printPostOrder(root.right);
        System.out.print(root.data + " ");
    }
}

 

구현 방법

Insert

재귀함수를 사용하여 삽입될 값의 위치까지 이동 후 생성(leaf노드이기때문에 root == null이 될때까지)

함수가 종료되어 상위노드로 이동할때마다 노드의 BF를 비교하여 상황에 맞게 회전

 

Insert에서 올바른 위치까지 재귀적으로 탐색하는 코드(line:69)

if(val > root.data)
{
	root.right = Insert(root.right,val);
    root = setBalance(root);
}
else
{
	root.left = Insert(root.left,val);
    root = setBalance(root);
}

올바른 위치를 찾아 새로운 노드 생성(line:65)

        if(root == null) {
            root = new Node();
            root.data = new Integer(val);
        }

 

Delete

바이너리트리에서 삭제 방법으로는 현재 노드의 값을 왼쪽에서 가장 큰 값과 바꾸거나 오른쪽에서 가장 작은값과 바꾸면 된다. 이 코드에서는 왼쪽에서 가장 큰 노드와 바꿈

 

Insert와 유사하게 재귀적으로 탐색하며 삭제 완료시에는 함수가 종료되어 상위노드로 이동하면서 밸런스를 맞춤

Delete에서 삭제할 노드까지 재귀적으로 탐색하는 코드(line:92)

       if(val > root.data)
       {
           root.right = Delete(root.right,val);
           root = setBalance(root);
       }
       else if(val < root.data)
       {
           root.left = Delete(root.left,val);
           root = setBalance(root);
       }

삭제되어야할 노드를 찾은후의 코드(line:102)

       else
       {
           if(root.left != null)
           {
               Node temp = root.left;

               while(temp.right != null)
                    temp = temp.right;

               root.data = temp.data;
               root.left = Delete(root.left,temp.data);

               root = setBalance(root);
           }
           else
               return root.right;
       }

삭제되어야할 노드의 값을 왼쪽 가장 큰 노드의 값으로 변경 후, 왼쪽 가장 큰 노드를 삭제한다. 그 후 노드의 밸런스를 맞춰준다.