Today I Learned

오늘 할일
1. LeetCode
2. 현장실습 지원
3. 모바일 프로그래밍 과제
4. 알고리즘 과제

오늘 한일
1. LeetCode

• 450. Delete Node in a BST를 해결하기 위해 Heap노드 삭제를 검색해보았다. 루트 노드를 삭제해야하는경우, 끝단의 노드를 가져온 뒤 swap을 진행한다는 아이디어는 쓸만한 듯 하다. 이제 루트 외 노드의 삭제를 생각하면 되는데..

이진탐색트리에서 노드의 삭제를 참고하여 삭제 노드 기준으로 자식이 없다면 부모과 disconnect, 자식이 둘이면 right에서 최자측 노드와 swap후 disconnect, 자식이 하나면 방향에 따라 최좌측, 최우측 노드와 swap후 disconnect하게 코드를 작성하였다.

class Solution {
    private TreeNode root;
    private TreeNode left_most(TreeNode node){
        TreeNode cur=node;
        while(cur.left!=null){
            cur=cur.left;
        }
        return cur;
    }
    private TreeNode right_most(TreeNode node){
        TreeNode cur=node;
        while(cur.right!=null){
            cur=cur.right;
        }
        return cur;
    }
    private void disconnect(TreeNode node, TreeNode target, TreeNode prev){
        if(node.val<target.val){
            disconnect(node.right, target, node);
        } else if(node.val>target.val){
            disconnect(node.left, target, node);
        } else{
            if(prev.left.val==target.val)
                prev.left=null;
            else if(prev.right.val==target.val)
                prev.right=null;
        }
    }

    private void remove(TreeNode node, int key, TreeNode prev){
        if(node==null)
            return;
        
        if(node.val<key){
            remove(node.right, key, node);
        } else if(node.val>key){
            remove(node.left, key, node);
        } else {
            if(node.left==null && node.right==null){
                if(prev.right==node)
                    prev.right=null;
                else
                    prev.left=null;
            } else if(node.left!=null && node.right!=null){
                TreeNode tmp=left_most(node.right);
                node.val=tmp.val;
                tmp.val=0;
                disconnect(root, tmp, root);
            } else if(node.left==null && node.right!=null){
                TreeNode tmp=left_most(node.right);
                node.val=tmp.val;
                tmp.val=0;
                disconnect(root, tmp, root);
            } else if(node.left!=null && node.right==null){
                TreeNode tmp=right_most(node.left);
                node.val=tmp.val;
                tmp.val=0;
                disconnect(root, tmp, root);
            }
        }
    }
    public TreeNode deleteNode(TreeNode root, int key){
        this.root=root;
        if(root==null || (root.val==key && root.left==null && root.right==null))
            return null;

        remove(root, key, root);
        return root;
    }
}

하지만 parameter전달부에 null값이 전달되는 오류가 발생하였고, 값을 출력시켜보았지만 값은 잘 출력된다..

인텔리제이로 옮겨 직접 디버깅 한 결과

tmp값이 제대로 탐색되지 않았다.

private void disconnect(TreeNode node, TreeNode target, TreeNode prev){
		//if(node==null) return;
        if(node.val<target.val){
            disconnect(node.right, target, node);
        } else if(node.val>target.val){
            disconnect(node.left, target, node);
        } else{
            if(prev.left.val==target.val)
                prev.left=null;
            else if(prev.right.val==target.val)
                prev.right=null;
        }
    }

문제는 부모노드를 찾아 자신과의 연결을 끊는 disconnect함수에서 node가 null일 경우의 escape처리를 하지 않았기 때문이다..가 아니지. 애초에 disconnect가 호출되기 전에 left_most에서는 잘 들어오네..!

현재까지의 모든 코드를 주석달고 정리하며 논리오류를 발견했다. 삭제할 target노드를 remove함수에서 찾고, disconnect함수로 target과 그 부모노드간의 연결을 끊기 전에 값을 swap해버렸기 때문이다. disconnect함수에서는 노드가 정렬상태임을 가정하고 BFS나 DFS가 아닌 이진탐색을 수행하는데, 함수 호출 이전에 값이 swap되며 정렬상태가 깨져, disconnect해야하는 노드를 찾기 못하는 것이다. 값의 swap을 disconnect함수 호출 이후로 미루자.

이를 보완하여 코드를 작성하였다.

class Solution {
    private TreeNode root;
    private TreeNode left_most(TreeNode node){
        TreeNode cur=node;
        while(cur.left!=null){
            cur=cur.left;
        }
        return cur;
    }
    private TreeNode right_most(TreeNode node){
        TreeNode cur=node;
        while(cur.right!=null){
            cur=cur.right;
        }
        return cur;
    }
    private void disconnect(TreeNode node, TreeNode target, TreeNode prev){//루트, 타겟, 이전 노드를 기준으로 타겟의 연결을 끊는다.
        if(node.val<target.val){
            disconnect(node.right, target, node);
        } else if(node.val>target.val){
            disconnect(node.left, target, node);
        } else{
            if(prev.left.val==target.val)
                prev.left=null;
            else if(prev.right.val==target.val)
                prev.right=null;
        }
    }

    private void remove(TreeNode node, int key, TreeNode prev){
        if(node==null)
            return;
        
        if(node.val<key){
            remove(node.right, key, node);
        } else if(node.val>key){
            remove(node.left, key, node);
        } else {//삭제 대상을 찾았다.
            if(node.left==null && node.right==null){//1. 삭제 대상의 자식 노드가 없는 경우, 이전 노드와의 연결을 끊는다.
                if(prev.right==node)
                    prev.right=null;
                else
                    prev.left=null;
            } else if(node.left!=null && node.right!=null){//2. 삭제 대상의 자식 노드가 두개인 경우, 우측 자식 의 최소값을 가져와 swap한다
                TreeNode tmp=left_most(node.right);//우측 노드의 최소노드를 가져온다
                disconnect(root, tmp, root);//우측 최소노드를 부모 노드의 링크로부터 제거한다.
                int node_tmp=node.val;//기존 노드값 복사
                node.val=tmp.val;//기존 노드값을 우측 최소노드 값으로
                tmp.val=node_tmp;//우측 최소노드 값을 기존 노드값으로
            } else if(node.left==null && node.right!=null){//3. 삭제 대상의 자식 노드가 오른쪽 1개인 경우, 우측 자식의 최소값을 가져와 swap한다
                TreeNode tmp=left_most(node.right);
                disconnect(root, tmp, root);
                int node_tmp=node.val;
                node.val=tmp.val;
                tmp.val=node_tmp;
            } else if(node.left!=null && node.right==null){//4. 삭제 대상의 자식 노드가 좌측 1개인 경우, 좌측 자식의 최댓값을 가져와 swap한다
                TreeNode tmp=right_most(node.left);
                disconnect(root, tmp, root);
                int node_tmp=node.val;
                node.val=tmp.val;
                tmp.val=node_tmp;
            }
        }
    }
    public TreeNode deleteNode(TreeNode root, int key){
        this.root=root;
        if(root==null || (root.val==key && root.left==null && root.right==null))
            return null;

        remove(root, key, root);
        return root;
    }
}

테스트케이스를 돌려보던 중, disconnect시에 target의 자식 노드를 연결하지 않았다는 점을 발견할 수 있었다.

해당 부분을 수정해보았지만, 코드가 너무 복잡하다. 전반적으로 최적화 진행해보기로 결정했다.

class Solution {
    private TreeNode root;
    private TreeNode left_most(TreeNode node){
        TreeNode cur=node;
        while(cur.left!=null){
            cur=cur.left;
        }
        return cur;
    }
    private TreeNode right_most(TreeNode node){
        TreeNode cur=node;
        while(cur.right!=null){
            cur=cur.right;
        }
        return cur;
    }
    private void disconnect(TreeNode node, TreeNode target, TreeNode prev){//루트, 타겟, 이전 노드를 기준으로 타겟의 연결을 끊는다.
        if(node.val<target.val){
            disconnect(node.right, target, node);
        } else if(node.val>target.val){
            disconnect(node.left, target, node);
        } else{
            if(target.left==null && target.right==null){
                if(prev.left.val==target.val){
                    prev.left=null;
                } else if(prev.right.val==target.val){
                    prev.right=null;
                }
            } else if(target.left==null && target.right!=null){
                if(prev.left.val==target.val){
                    prev.left=target.right;
                } else if(prev.right.val==target.val){
                    prev.right=target.right;
                }
            } else if(target.left!=null && target.right==null){
                if(prev.left.val==target.val){
                    prev.left=target.left;
                } else if(prev.right.val==target.val){
                    prev.right=target.left;
                }
            } else if(target.left!=null && target.right!=null){
                if(prev.left.val==target.val){
                    prev.left=target.right;
                } else if(prev.right.val==target.val){
                    prev.right=target.left;
                }
            }
        }
    }

    private void remove(TreeNode node, int key, TreeNode prev){
        if(node==null)
            return;
        
        if(node.val<key){
            remove(node.right, key, node);
        } else if(node.val>key){
            remove(node.left, key, node);
        } else {//삭제 대상을 찾았다.
            if(node.left==null && node.right==null){//1. 삭제 대상의 자식 노드가 없는 경우, 이전 노드와의 연결을 끊는다.
                if(prev.right==node)
                    prev.right=null;
                else
                    prev.left=null;
            } else if(node.left!=null && node.right!=null){//2. 삭제 대상의 자식 노드가 두개인 경우, 우측 자식 의 최소값을 가져와 swap한다
                TreeNode tmp=left_most(node.right);//우측 노드의 최소노드를 가져온다
                disconnect(root, tmp, root);//우측 최소노드를 부모 노드의 링크로부터 제거한다.
                int node_tmp=node.val;//기존 노드값 복사
                node.val=tmp.val;//기존 노드값을 우측 최소노드 값으로
                tmp.val=node_tmp;//우측 최소노드 값을 기존 노드값으로
            } else if(node.left==null && node.right!=null){//3. 삭제 대상의 자식 노드가 오른쪽 1개인 경우, 우측 자식의 최소값을 가져와 swap한다
                TreeNode tmp=left_most(node.right);
                disconnect(root, tmp, root);
                int node_tmp=node.val;
                node.val=tmp.val;
                tmp.val=node_tmp;
            } else if(node.left!=null && node.right==null){//4. 삭제 대상의 자식 노드가 좌측 1개인 경우, 좌측 자식의 최댓값을 가져와 swap한다
                TreeNode tmp=right_most(node.left);
                disconnect(root, tmp, root);
                int node_tmp=node.val;
                node.val=tmp.val;
                tmp.val=node_tmp;
            }
        }
    }
    public TreeNode deleteNode(TreeNode root, int key){
        this.root=root;
        if(root==null || (root.val==key && root.left==null && root.right==null))
            return null;

        remove(this.root, key, root);
        return this.root;
    }
}