[자료구조] 이진탐색트리 구현 - 삭제

이진탐색트리에서 삭제를 할 때에는 경우의 수를 3가지를 생각해야 한다.

 

경우 1) 리프노드(자식이 없는 노드)일 경우

         * 이 경우 단순히 해당 노드를 null로 처리하고 그 노드를 return하기만 하면 된다.

 

경우 2) 왼쪽/오른쪽 중에서 한쪽에만 자식이 있는 경우

         * 오른쪽에만 자식이 있다면, 왼쪽 자식을 해당 노드로 바꾸고 그 노드를 return한다

           (한마디로 할아버지가 손자 손을 잡도록 하는 격)

 

경우 3) 왼쪽/오른쪽 양쪽 모두 자식이 있는 경우

 

        * 삭제하려고 하는 노드를 [왼쪽 서브트리 중 가장 큰 노드]또는 [오른쪽 서브트리 중 가장 작은 노드]로 교체하고,            이 후 서브트리에서 그 노드는 삭제를 해준다.

        * 나는 [오른쪽 서브트리 중 가장 작은 노드]로 대체하는 방법을 선택하여 자바스크립트 코드로 구현했다.

 

remove(key){
        this.root = this.removeNode(this.root, key);
    }
    removeNode(node, key){
        if(node === null){
            return null;
        }else if(key < node.key){
            node.left = this.removeNode(node.left, key);
            return node;
        }else if(key > node.key){
            node.right = this.removeNode(node.right, key);
            return node;
        }else{ //key === node.key
            //경우1 - 리프노드
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }
            
            //경우2 - 자식이 하나뿐인 노드
            if(node.left === null){
                node = node.right;
                return node;
            }else if(node.right === null){
                node = node.left;
                return node;
            }
            //경우3 - 자식이 둘인 노드
            // 왼쪽에서 가장 큰 값과 바꾸던가 오른쪽에서 가장 작은 값과 바꾸면 되는데 여기서 오른쪽에서 가장 작은 값과 바꿀 것이다
            let aux = this.findMinNode(node.right);
            node.key = aux.key;
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    }