BST: 450. Delete Node in a BST ★

450. Delete Node in a BST

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root

        if root.val < key: # key 가 더 크면, 오른쪽으로 내려가서 삭제
            root.right = self.deleteNode(root.right, key)

        elif root.val > key: # key 가 더 작으면, 왼쪽으로 내려가서 삭제
            root.left = self.deleteNode(root.left, key)
        else: # root.val == key: # 아니면, root 삭제
            if not root.left: # root 의 왼쪽 노드가 없으면,
                return root.right # 오른쪽 반환
            elif not root.right: # root 의 오른쪽 노드가 없으면,
                return root.left
            else: # 둘다 있으면 
                # root 삭제 전에, 오른쪽 노드의 가장 작은 값을 root 에 적용하고, 
                # 오른쪽 노드의 가장 작은 노드(왼쪽으로 내려가야함)를 삭제해야 하므로
                cur = root.right
                while cur.left:
                    cur = cur.left

            root.val = cur.val
            root.right = self.deleteNode(root.right, cur.val)
        
        return root # 현재 노드

 

https://youtu.be/LFzAoJJt92M?si=_LrfMfVYxmtP2HPL

 

 

def delete(node, val):

    if not node:

        return None # 빼먹으면 안됨

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        
        def minValue(node):
            # 현재 노드 트리에서 최소값을 가진 노드 리턴.
            # 그래서, 왼쪽으로만 내려가면되고, 왼쪽 끝 리프노드를 리턴

            cur = node

            while cur.left:
                cur = cur.left # 이게 내려가는 건데.

            # 원래 while cur: 이렇게 하면,
            # while 문 끝나면, cur 이 null 이 되므로
            # while cur.left 하면
            # cur.left 가 null 이 되었을때 while 문이 나오므로.
            # cur 는 왼쪽 끝 leaf 노드가 됨
            return cur

        def delete(node, val):
            if not node: 
                return None # 빼먹으면 안됨

            if val < node.val: # 삭제 할 값이, 현재 노드 값보다 작으면, 왼쪽으로 내려가서 삭제
                node.left = delete(node.left, val)
            elif val > node.val: # 삭제 할 값이, 현재 노드 값보다 크면, 오른쪽으로 내려가서 삭제
                node.right = delete(node.right, val)
            else: # 삭제할 값이 현재 값이면
                if not node.left: # 왼쪽 자식이 없으면
                    return node.right # 오른쪽 자식 리턴
                elif not node.right: # 오른쪽 자식이 없으면
                    return node.left
                elif node.left and node.right: # 둘다 있으면
                    # 현재꺼 삭제하면
                    # 오른쪽에서 가장 작은 노드가 현재 노드로 올라와야 하니
                    # 오른쪽에서 가장 작은 노드를 우선 찾음
                    rightMin = minValue(node.right)
                    
                    # 현재 노드값을 rightMin 값으로 바꾸고
                    node.val = rightMin.val
                    #현재 노드의 오른쪽에서 이 rightMin 값을 삭제
                    node.right = delete(node.right, rightMin.val)
            return node

        return delete(root, key)

 

최종 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # 현재 노드 삭제시, 오른쪽 자식의 가장 최소값이 현재노드쪽으로 올라와야 함
        def minNode(node):
            """
            왼쪽이 작은값
            node.left 있을때까지 내려가서
            마지막에 node = node.left 하면, 가장 최소값이 됨 
            """
            while node.left:
                node = node.left
            return node

        
        def delete(node, val):
            """
            node 없을때, None 리턴 빼먹지 말기!!
            """
            if not node:
                return None

            if val < node.val: 
                """
                삭제할 값이 왼쪽에 있으면, 왼쪽으로 내려가
                """
                node.left = delete(node.left, val)
            elif val > node.val:
                """
                삭제할 값이 오른쪽에 있으면, 오른쪽으로 내려가
                """
                node.right = delete(node.right, val)
            else:                
                """
                삭제할 값이 현재 노드이면

                * 자식 노드가 하나만 있거나 없는 경우 *

                왼쪽 자식이 없으면, 오른쪽 으로 내려가, 오른쪽 자식 리턴
                오른쪽 자식이 없으면, 왼쪽 으로 내려가, 왼쪽 자식 리턴
                """
                if not node.left:
                    return node.right
                elif not node.right:
                    return node.left
                elif node.left and node.right:
                    """
                    * 자식 노드가 둘 다 있는 경우 *

                    삭제할 값이 지금 노드면, 
                    현재노드 삭제하고, 오른쪽 자식 중 가장 최소값은 현재노드로
                    즉, 
                    1) 오른쪽 자식 중 가장 최소 노드 찾기
                    2) 현재 노드 값 <= 오른쪽 최소값
                    3) 오른쪽 최소값 노드 삭제 
                    """
                    rightMin = minNode(node.right)
                    node.val = rightMin.val
                    node.right = delete(node.right, rightMin.val)
            return node

        """
        return 빼먹으면 안됨!!
        """
        return delete(root, key)

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        def findMin(node):
            while node.left: # 이렇게 해야. 마지막 왼쪽 노드 있을때.. 까지 돌고. 
                node = node.left # 한번더 왼쪽으로 가면
            return node # 가장 마지막 왼쪽 노드임

        def delete(node, key):
            if not node: # 빈 노드이면 
                return node # 어차피 이것도 None 임  <-- 중요!!
            
            if node.val < key: # 삭제하려는 값이, 현재 값보다 크면, 오른쪽으로 내려가야 함
                node.right = delete(node.right, key)
            elif node.val > key: # 삭제하려는 값이, 현재 값보다 작으면, 왼쪽으로 내려가야 함
                node.left = delete(node.left, key)
            else: # node.val == key 이면, 현재 노드 삭제
                # 현재 노드 삭제하면
                # 왼쪽 노드가 없으면, 오른쪽 노드를 연결하면 되고
                if not node.left:
                    node = node.right
                # 오른쪽 노드 가 없으면, 왼쪽 노드를 연결하면 되고
                elif not node.right:
                    node = node.left
                elif node.left and node.right: # 왼쪽,오른쪽 둘다 있으면, 오른쪽 노드의 가장 왼쪽이 내자리로.
                    minNode = findMin(node.right)
                    node.val = minNode.val
                    # delete(minNode, minNode.val) <-- 이렇게 하면 안됨!!
                    node.right = delete(node.right, minNode.val) # 원래 노드에서 삭제해서, 갱신해줘야 함!!
            return node
            
        return delete(root, key)