Today I Learned

오늘 할일
1. 창엔 업무_11차 초대 및 이전회차 검토
2. LeetCode
3. 인턴 or 현장실습 지원하기
4. 인공지능 개론 Car_evaluation 과제

오늘 한일
1. LeetCode
기존에 실패했던 문제를 다시 읽어보자

• 450. DeleteNode in a BST는 이진정렬트리에서 노드를 삭제하는 문제이다. 간단하지만 이진 "정렬" 트리라는 것을 제대로 읽지 않아 난항을 겪었다. 처음부터 코드를 작성해 볼 것인데, 루트 노드의 삭제를 주의하여 코드를 설계해보자. 간단하게 알고리즘을 구상해보면, 삭제하고자하는 노드를 기준으로 자식과 삭제하고자하는 부모의 연결만 고려하면 될 듯 하다. LL회전과 RR회전이 문득 생각났다. 어떻게 해결해야할지 한 눈에 알고리즘이 떠오르진 않는다.

순차적으로 생각해보자. 노드를 삭제할 경우 자식 노드 중 하나를 올리게 된다. 그러면 직선상태의 그래프가 되고, 추가적인 정렬이 필요하다면 LL회전 RR회전으로 균형을 맞춘다. 만약 삭제하고자하는 노드가 루트노드라면? 자식 노드를 올리는 게 아니라 특정 말단 노드를 올릴 수도 있다. 즉, 자식 노드를 올린다는 것은 틀렸다.

가설1) 노드를 삭제할 경우 노드에서 가장 크기가 가까운 노드를 올린다. 이 경우 좌우측 자식노드에서 가장 가까운 정도가 동일한 두개의 노드가 존재할 수 있다.
가설2) 자신이 부모노드로부터 왼쪽에 있다면 우측 자식노드를, 오른쪽에 있다면 좌측 자식노드를 올린다.
이 경우 삭제하고자 하는 노드가 루트면 부모노드를 정할 수 없다.
가설3) 노드를 삭제할 경우 자신과 가장 가까운 값을 가진 하위 노드와 바꾼다. 이 과정에서 직선에 가까운 트리가 발생하면 LL회전, RR회전으로 균형을 맞춘다.
인터넷) 우측 노드에서 가장 좌측값 노드로 끼워넣는다.

class Solution {
    private TreeNode left_most(TreeNode node){
        TreeNode cur=node;
        while(cur.left!=null){
            cur=cur.left;
        }
        return cur;
    }
    private void remove(TreeNode node, int key){
        if(node==null)
            return;
        if(node.val<key){
            remove(node.right, key);
        } else if(node.val>key){
            remove(node.left, key);
        } else{
            TreeNode swap_node=left_most(node.right);
            node.val=swap_node.val;
        }
    }
    public TreeNode deleteNode(TreeNode root, int key){
        if(root==null || (root.val==key && root.left==null && root.right==null))
            return null;

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

굉장히 어렵다... 오늘 이 문제를 꼭 정복해보자..