[HackerRank] Self Balancing Tree

AVL트리는 self balancing binary search tree이다. 자식 subtree의 높이가 최대 1개까지 차이가 나는데 둘 이상 차이가 나면 이를 복원하기 위해서 균형을 맞춘다. -> balanceFactor = height(left subtree) - height(right subtree)

 

Q. 트리에 새로운 값을 삽입하기 위한 insert 함수를 완성해야 한다.

	/* 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)
    {
        
        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)){
                root = rightRot(root);
            }else{
                root.left = leftRot(root.left);
                root = rightRot(root);
            }
        }else if(bf < -1){
            if(height(root.right.left) <= height(root.right.right)){
                root = leftRot(root);
            }else{
                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));
    }

- insert 함수 

첫 if문에서 root == null이면 노드가 하나도 없다는 것이므로 root 노드를 생성해서 값을 넣어준다. 그리고 높이도 지정해준다. 두 번째랑 세 번째 if문에서는 기존 root 노드의 값과 새로운 값을 비교해서 새 값이 더 작으면 root 노드의 왼쪽에 삽입하고, 크면 root 노드의 오른쪽에 삽입한다. 이렇게 기본적으로 트리를 생성한다.

그런데 balanceFactor를 고려해야 하므로, 정수형 변수 bf에 왼쪽 노드의 높이에서 오른쪽 노드의 높이를 뺀 값을 구한다. 만약 bf가 1보다 크면 오른쪽으로 회전하여 균형을 맞춰줘야 한다. 그런데 왼쪽에 있는 서브트리들의 배치를 한 번 더 고려해야 한다. Left Left의 경우에는 그냥 1번의 오른쪽 회전으로 균형을 이룰 수 있는데 Left Right의 경우에는 왼쪽 회전을 1회 한 후에 오른쪽 회전을 해야 한다. root.left.left의 높이가 root.left.right의 높이보다 크면 Left Left의 경우이므로 rightRot을 해주고, root.left.left의 높이가 root.left.right의 높이보다 크지 않다면 Right Left의 경우이므로 root.left를 leftRot한 후에 root로 rightRot한다. bf가 -1보다 작은 경우는 이와 딱 반대로 생각하면 된다. 그리고 else 문에는 -1과 1 사이의 값일 때가 될텐데 이는 회전을 할 필요가 없다.