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

이진 탐색트리의 삭제연산은 3가지 Case를 고려해야한다.

1. 단말 노드 삭제
2. 자식이 하나인 노드 삭제
3. 두개의 자식을 모두 갖는 노드의 삭제

각각의 Case를 개별 함수로 정의하고 하나의 delete 함수가 필요하다.

각 Case를 전부 고려한 delete 함수

def delete_bst(root,key):
    if root == None: return None
    
    parent = None
    node = root
    # 삭제할 노드를 탐색하는 과정
    while node != None and node.key != key: 
        parent = node
        if key < node.key: node = node.left
        else: node = node.right
    
	# 삭제할 노드가 없는 경우
    if node == None: return None
    
    # Case1 단말 노드 삭제
    if node.left == None and node.right == None:
        root = delete_bst_case1(parent, node, root)
        
    # Case2 자식이 하나인 노드 삭제
    elif node.left==None or node.right ==None:
        root = delete_bst_case2(parent, node, root)
        
    # Case3 두개의 자식을 모두 갖는 노드의 삭제
    else:
        root = delete_bst_case3(parent, node, root)
    return root 

Case1 단말노드 삭제

def delete_bst_case1(parent, node, root):
    if parent is None: # 삭제할 단말노드가 루트일 경우
        root = None # 공백트리
    else:
        if parent.left == node: # 삭제할 부모노드의 왼쪽이 삭제할 노드이면
            parent.left = None
        else:
            parent.right = None
    return root

• 삭제할 노드가 단말 노드인 경우이다. 삭제할 노드가 자기 부모의 왼쪽 노드인지 오른쪽 노드인지에 따라 삭제

Case2 자식이 하나인 노드 삭제

# case2. 자식이 하나인 노드의 삭제
def delete_bst_case2(parent, node, root):
    if node.left is not None: # 삭제할 노드가 왼쪽 자식을 가진다면
        child = node.left
    else:
        child = node.right # child는 삭제할 노드의 자식
        
    if node == root: # 없애려는 노드가 루트이면
        root = child # child가 새로운 루트가 됨
    else:
        if node is parent.left: #삭제할 노드가 부모의 왼쪽 자식이면
            parent.left = child # 부모의 왼쪽 자식이 child가 됨
        else:
            parent.right = child

• 삭제할 노드의 자식 노드를 child라는 변수에 할당해둔다. 그리고 삭제할 노드가 자기 부모의 왼쪽노드인지 오른쪽 노드인지에 따라 child값을 삽입

Case3 두개의 자식을 모두 갖는 노드의 삭제

def delete_bst_case3(parent, node, root):
    succp = node
    succ = node.right
    
    # 오른쪽 노드의 최솟값을 찾는 과정
    while(succ.left != None): # succ의 왼쪽노드가 공백이 아니면  한칸씩 내려감
        succp = succ
        succ = succ.left 
    
    # 다 내려왔을 때, 위로 올라갈 노드의 자식노드를 자신의 부모노드와 연결
    if(succp.left == succ): succp.left가 succ와 같다면 
        succp.left = succ.right
    else:
        succp.right = succ.right
       
    # 삭제할 노드에 succ 즉 후보 노드를 삽입
    node.key = succ.key
    node.value = succ.value
    node = succ
    
    return root

• 가장 복잡한 경우이다. 삭제할 경우가 왼쪽 오른쪽 자식을 모두 가지는 경우이다. 결국에 왼쪽 노드에선 가장 큰 값, 오른쪽 노드에선 가장 작은 값을 삭제 노드에 넣어주면 된다.