[HackerRank] Self Balancing Tree(Java, 로테이션, 이진트리)

www.hackerrank.com/challenges/self-balancing-tree/problem?isFullScreen=true

Self Balancing Tree | HackerRank

 

## 접근방법

---

이 문제는 기본적으로 AVL 트리에 대한 개념이 있어야 한다.

 

 

AVL 트리가 나오게 된 개념부터 생각해보자. 트리는 자료를 저장하기 위한 자료구조이다. 트리는 높이만큼의 탐색 시간을 가지므로, 일반적으로 log의 시간복잡도의 탐색을 할 수 있다.

 

 

하지만 치우져친 트리가 완성된다면, 트리의 장점을 이용할 수 없게 된다. 그래서, 나오게된 개념이 AVL 트리라는 것이다. 

 

 

AVL 트리를 만들기 위해서는 밸렁신이라는 개념이 필요하다. 밸런싱의 목적은 왼쪽 트리와 오른쪽 트리의 높이차를 줄이는 것이 목적이다.

 

 

AVL 트리는 밸런스 팩터라는 요소를 사용한다. 밸런스 팩터는 왼쪽 트리의 높이와 오른쪽 트리의 높이 차를 의미한다. 높이 차가 [-1, 1] 범위에 있지 않으면, 밸런싱이 필요함을 의미한다.

 

 

밸런싱의 목적은 높이 차가 [-1, 1] 범위에 있도록, 트리들을 이동시키는 것이다.

 

 

밸런싱을 하기 위해서는 로테이션이 필요하다. 로테이션은 왼쪽 로테이션과 오른쪽 로테이션이 존재한다. 

 

 

 

왼쪽 그림은 오른쪽 로테이션을 의미하고, 오른쪽 그림은 왼쪽 로테이션을 의미한다. 화살표의 방향으로 이해하면 된다. 

 

 

 

Left Right 케이스나 Right Left 케이스라면, 다른 작업들이 필요하다. LR 케이스의 경우, 왼쪽 노드를 먼저 오른쪽 로테이션을 해줘야 한다. RL 케이스의 경우는 오른쪽 노드를 먼저 왼쪽 로테이션을 해줘야 한다.

 

 

LR케이스와 RL 케이스에는 위와 같은 선행작업이 필요한 이유는, 위에서 바로 현재 노드를 로테이션 시키면 밸런스 팩터의 변화가 없다. LR 기준으로 가장 긴 트리가 왼쪽에 있어야, 왼쪽 트리의 높이를 줄일 수 있다. 

 

 

로테이션을 구현할 때, 항상 이진트리의 개념이 성립하도록 신경써서 코드를 구현하면 된다.

 

 

문제에서 요구한 것은, Insert 코드의 작성이다. Insert 함수를 정의를 잘해야 한다. Insert 함수는 삽입될 노드의 위치도 찾아야 하고, 삽입된 이후에 균형된 트리가 될 수 있도록 밸런싱(로테이션) 작업도 되어야 한다.

 

 

재귀 함수를 작성할 때는, 항상 함수와 다음 함수의 관계를 생각하면서 코드를 작성해야 한다. 전체를 이해하려고 하면, 더 어려울 것이다. 재귀 함수의 직관성을 이용해서 작성하자.

 

 

AVL의 개념적인 부분은 쉽지만, 코드를 작성하려면 더욱 쉽지 않다. 좋은 문제였다고 생각한다.

 

 

 

## 해설코드

---

    /* Class node is defined as :
    class Node 
        int val;    //Value
        int ht;        //Height
        Node left;    //Left child
        Node right;    //Right child
 
    */
 
    static Node insert(Node root,int val)
    {
        // Insert + Balancing
        if(root == null){
            root = new Node();
            root.val = val;
            root.ht = setHeight(root);
            return root;
        }
        
        if(root.val > val){
            root.left = insert(root.left, val);
        }
        
        if(root.val < val){
            root.right = insert(root.right, val);
        }
        
        int bf = height(root.left) - height(root.right);
        
        if(bf > 1){
            if(height(root.left.left) >= height(root.left.right)){
                // Left Left
                root = rightRot(root);
            }else{
                // Left Right
                root.left = leftRot(root.left);
                root = rightRot(root);
            }
        }else if(bf < -1){
            if(height(root.right.left) <= height(root.right.right)){
                // Right Right
                root = leftRot(root);
            }else{
                // Right Left
                root.right = rightRot(root.right);
                root = leftRot(root);
            }
        }else{
            root.ht = setHeight(root);
        }
        
        return root;
    }
 
    static Node rightRot(Node node){
        Node newNode = node.left;
        node.left = newNode.right;
        newNode.right = node;
        node.ht = setHeight(node);
        newNode.ht = setHeight(newNode);
        return newNode;
    }
 
    static Node leftRot(Node node){
        Node newNode = node.right;
        node.right = newNode.left;
        newNode.left = node;
        node.ht = setHeight(node);
        newNode.ht = setHeight(newNode);
        return newNode;
    }
 
    static int height(Node node){
        if(node == null)
            return -1;
        else
            return node.ht;
    }
 
    static int setHeight(Node node){
        if(node == null)
            return -1;
        else
            return 1 + Math.max(height(node.left), height(node.right));
    }