[자료구조] #7_3 트리

** 트리 노드 삭제

• 3가지 경우의 수를 나눠서 생각

 

1) Leaf 노드 삭제 시

- 삭제할 노드의 Parent 노드가 삭제할 노드를 가리키지 않도록 한다

 

2) Child 노드가 1개인 노드 삭제 시

- 삭제할 노드의 Parent 노드가 삭제할 노드의 Child 노드를 가리키도록 한다

 

 

3) Child 노드가 2개인 노드 삭제 시

- 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 Parent 노드가 가리키도록 한다.

or

- 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 Parent 노드가 가리키도록 한다.

 

 

 

 

**파이썬 객체지향 프로그래밍으로 트리 구현

---> (삽입), (탐색), 삭제

---

class BinarySearchTree:
    def __init__(self, head):
        self.head = head
    
    # 삽입
    def insert(self, value):
       ...
                    
    # 탐색                
    def search(self, value):
        ...

    # 삭제
    def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        
        # 삭제할 노드 탐색
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif self.current_node.value > value:
                self.parent = self.current_node # 부모 노드도 함께 이동
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right
        
        # 삭제할 노드가 트리에 존재하지 않음
        if searched == False:
            return False
        
        # 이후부터 Case별로 코드 작성
        # self.current_node: 삭제 대상 노드
        # self.parent: 삭제 대상 노드의 부모 노드
        # 1
        if self.current_node.left == self.current_node.right == None:
            if self.parent.value > value:
                self.parent.left = None
            else:
                self.parent.right = None
            del self.current_node
            
        # 2-1) 삭제 대상 노드가 왼쪽 자식만 가지고 있을 때
        elif self.current_node.left != None and self.current_node.right == None:
            # 2-1-1)삭제 대상 노드가 부모 노드의 왼쪽 자식일 때
            if self.parent.value > value:
                self.parent.left = self.current_node.left
            # 2-1-2)삭제 대상 노드가 부모 노드의 오른쪽 자식일 때
            else:
                self.parent.right = self.current_node.left

        # 2-2) 삭제 대상 노드가 오른쪽 자식만 가지고 있을 때
        elif self.current_node.left == None and self.current_node.right != None:
            # 2-2-1) 삭제 대상 노드가 부모 노드의 왼쪽 자식일 때
            if self.parent.value > value:
                self.parent.left = self.current_node.right
            # 2-2-2) 삭제 대상 노드가 부모 노드의 오른쪽 자식일 때
            else:
                self.parent.right = self.current_node.right
        
        # 3) 삭제 대상 노드가 자식 노드를 2개 가지고 있고,
        elif self.current_node.left != None and self.current_node.right != None:
            # 3-1) 삭제 대상 노드가 부모 노드의 왼쪽 자식일 때
            if value < self.parent.value:
                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
                
                # 3-1-1) 삭제 대상 노드의 오른쪽 자식 중 가장 작은 값을 가지는 노드가 오른쪽 자식을 가질 때
                if self.change_node.right != None:
                    self.chage_node_parent.left = self.change_node.right
                # 3-1-2) 삭제 대상 노드의 오른쪽 자식 중 가장 작은 값을 가지는 노드가 자식을 가지지 않을 때
                else: 
                    self.change_node_parent.left = None
                
                # 삭제 대상 노드를 대체
                self.parent.left = self.change_node
                self.change_node.left = self.current_node.left
                self.chagne_node.right = self.current_node.right
            
            # 3-2) 삭제 대상 노드가 부모 노드의 오른쪽 자식일 때
            else:
                self.change_node = self.current_node.left
                self.change_node_parent = self.current_node.left
                
                # 삭제 대상 노드의 왼쪽 자식 중 가장 큰 값을 가지는 노드로 이동
                while self.change_node.right != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.right
                
                # 3-2-1) 삭제 대상 노드의 왼쪽 자식 중 가장 큰 값을 가지는 노드가 왼쪽 자식을 가질 때
                if self.change_node.left != None:
                    self.change_node_parent.right = self.change_node.left
                # 3-2-2) 삭제 대상 노드의 왼쪽 자식 중 가장 큰 값을 가지는 노드가 자식을 가지지 않을 때
                else:
                    self.change_node.parent.right = None

                # 삭제 대상 노드를 대체
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

 

        return True

 

---

 

# 테스트를 위한 코드
# 1-999 중 임의로 100개 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
# random 라이브러리 활용
import random

bst_nums = set() # 중복 불허
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))

# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트 노드의 값은 500으로 지정          
head = Node(500)
bst = BinarySearchTree(head)

for num in bst_nums:
    bst.insert(num)

# 입력한 100개의 숫자 검색
for num in bst_nums:
    if bst.search(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 bst.delete(del_num) == False:
        print('delete failed ', del_num) 

---

 

comment) Case 별로 적절한 그래프를 그려서 이해해보자