이진 탐색 트리 삭제

---

Leaf Node 삭제

• Leaf Node(=Terminal Node) : 자식 노드가 없는 노드
• 삭제할 노드의 부모 노드가 삭제할 노드를 가리키지 않도록 한다.
  

자식 노드가 하나인 노드 삭제

• 삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키도록 한다.
  

자식 노드가 두 개인 노드 삭제

• 2가지 방법으로 삭제할 수 있다.
  • 삭제할 노드의 오른쪽 자식의 왼쪽 자식들 중에서 가장 값이 작은, 즉 가장 왼쪽에 있는 노드를 삭제할 노드의 부모 노드가 가리키게 한다.(이 방법으로 구현한다.)
  • 삭제할 노드의 왼쪽 자식의 오른쪽 자식들 중에서 가장 값이 큰, 즉 가장 오른쪽에 있는 노드를 삭제할 노드의 부모 노드가 가리키게 한다.
    

첫 번째 방법의 순서

1. 삭제할 노드의 오른쪽 자식을 선택한다.
2. 오른쪽 자식의 가장 왼쪽에 있는 노드를 선택한다.
3. 해당 노드를 삭제할 노드의 부모 노드의 왼쪽 branch가 가리키게 한다.
4. 해당 노드의 왼쪽 branch가 삭제할 노드의 왼쪽 자식 노드를 가리키게 한다.
5. 해당 노드의 오른쪽 branch가 삭제할 노드의 오른쪽 자식 노드를 가리키게 한다.
6. 만약 해당 노드가 오른쪽 자식노드를 가지고 있다면, 해당 노드의 원래 부모 노드의 왼쪽 branch가 해당 노드의 오른쪽 자식 노드를 가리키게 한다.

이진 탐색 트리 삭제 구현

---

삭제할 노드 탐색

• 삭제할 노드가 없는 경우 False를 리턴하고, 함수를 종료 시킨다.

def deleteNodeSearch(self, value):
        searched = False
        self.current_node = self.head
        self.parent_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif self.current_node.value > value:
                self.parent_node = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent_node = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False
        else:
            return self.current_node, self.parent_node

삭제할 노드가 Leaf Node인 경우

• current_node : 삭제할 노드
• parent_node : 삭제할 노드의 부모 노드

def deleteNode(self, value):
        self.current_node, self.parent_node = self.deleteNodeSearch(value)
        
        # 삭제할 노드가 Leaf Node인 경우
        if self.current_node.left == None and self.current_node.right == None: 
            # 삭제할 노드가 부모 노드의 왼쪽에 있는 경우, 오른쪽에 있는 경우
            if self.parent_node.value > value: 
                self.parent_node.left = None
            else:
                self.parent_node.right = None

삭제할 노드가 자식 노드를 한 개 가지고 있을 경우

        # 삭제할 노드의 자식 노드가 1개인 경우
        if self.current_node.left != None and self.current_node.right == None: 
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.left
            else:
                self.parent_node.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.right
            else:
                self.parent_node.right = self.current_node.right

삭제할 노드가 자식 노드를 두 개 가지고 있을 경우

• 사용 가능한 전략
  • 삭제할 노드의 오른쪽 자식의 왼쪽 자식들 중에서 가장 값이 작은, 즉 가장 왼쪽에 있는 노드를 삭제할 노드의 부모 노드가 가리키게 한다.(이 방법으로 구현한다.)
  • 삭제할 노드의 왼쪽 자식의 오른쪽 자식들 중에서 가장 값이 큰, 즉 가장 오른쪽에 있는 노드를 삭제할 노드의 부모 노드가 가리키게 한다.

삭제할 노드가 부모 노드의 왼쪽에 있을 경우

• 경우의 수가 또 나뉜다.
  • 가장 작은 값을 가진 노드의 자식 노드가 없을 경우
  • 가장 작은 값을 가진 노드의 자식 노드가 있을 경우
    

        # 삭제할 노드의 자식 노드가 2개인 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 가장 작은 값을 가진 노드와 그 노드의 부모 노드
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            # 삭제할 노드가 왼쪽에 있는 경우
            if self.parent_node.value > value:
                # 가장 작은 값을 가진 노드가 오른쪽 자식 노드를 가진 경우
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

삭제할 노드가 부모 노드의 오른쪽에 있을 경우

• 경우의 수가 또 나뉜다.
  • 가장 작은 값을 가진 노드의 자식 노드가 없을 경우
  • 가장 작은 값을 가진 노드의 자식 노드가 있을 경우
    

            # 삭제할 노드가 오른쪽에 있는 경우
            else:
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

전체 코드 구현

---

class Node:
    def __init__(self, value): 
        # head, left, right는 노드의 주소를 가리키는 변수이다.
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self, head):
        # head는 루트노드의 주소를 가진다.
        self.head = head 
    
    def insertNode(self, value):
        # 트리를 순회하며 값을 삽입해야하기 때문에 임의 변수를 선언한다.
        self.current_node = self.head 
        
        while True:
            if self.current_node.value > value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def searchNode(self, value):
        self.current_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif self.current_node.value > value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False
    
    def deleteNodeSearch(self, value):
        searched = False
        self.current_node = self.head
        self.parent_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif self.current_node.value > value:
                self.parent_node = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent_node = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False
        else:
            return self.current_node, self.parent_node
                
    def deleteNode(self, value):
        self.current_node, self.parent_node = self.deleteNodeSearch(value)
        
        # 삭제할 노드가 Leaf Node인 경우
        if self.current_node.left == None and self.current_node.right == None: 
            # 삭제할 노드가 부모 노드의 왼쪽에 있는 경우, 오른쪽에 있는 경우
            if self.parent_node.value > value: 
                self.parent_node.left = None
            else:
                self.parent_node.right = None
        
        # 삭제할 노드의 자식 노드가 1개인 경우
        if self.current_node.left != None and self.current_node.right == None: 
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.left
            else:
                self.parent_node.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.right
            else:
                self.parent_node.right = self.current_node.right
                
        # 삭제할 노드의 자식 노드가 2개인 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 가장 작은 값을 가진 노드와 그 노드의 부모 노드
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            # 삭제할 노드가 왼쪽에 있는 경우
            if self.parent_node.value > value:
                # 가장 작은 값을 가진 노드가 오른쪽 자식 노드를 가진 경우
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
            # 삭제할 노드가 오른쪽에 있는 경우
            else:
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
                
        del self.current_node
        return True

전체 코드 테스트

import random

# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))
# print (bst_nums)

# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = BinarySearchTree(head)
for num in bst_nums:
    binary_tree.insertNode(num)
    
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
    if binary_tree.searchNode(num) == False:
        print ('search failed', num)

# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
    if binary_tree.deleteNode(del_num) == False:
        print('delete failed', del_num)

# 출력 없음