파이썬 자료구조 (6) 트리

1. 트리

• Node와 Branch를 이용해 사이클을 이루지 않도록 데이터를 나뭇가지처럼 연결하는 구성의 구조
• 트리 중 이진 트리(binary tree)형태의 구조로 탐색(검색) 알고리즘 구현을 위해 주로 사용

 

2. 알아둘 용어

• Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 레벨0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node: Child Node가 없는 노드
• Sibling Node: Parent Node가 동일한 노드

 

3. 이진 트리와 이진 탐색 트리

• 이진 트리: 노드의 최대 Branch가 2개인 트리
• 이진 탐색 트리: 왼쪽 노드는 부모 노드보다 작은 값, 오른쪽 노드는 부모 노드보다 큰 값을 가지는 이진 트리

 

4. 자료구조 이진 탐색 트리의 장점과 주요 용도

• 장점: 탐색 속도를 개선할 수 있음
• 주요 용도: 데이터 검색(탐색)

 

 

5. 파이썬 객체지향 프로그래밍으로 이진 탐색 트리 구현

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함 -> head를 기준으로 head 값보다 작으면 왼쪽, 크면 오른쪽으로 저장
# 중복 데이터를 넣지 않음
class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < 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:                                               # value > 상위 노드
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

 

# insert 테스트
head = Node(10)
BST = NodeMgmt(head)

BST.insert(4)
BST.insert(9)
BST.insert(13)
BST.insert(11)

 

 

문제1

이진 탐색 트리의 탐색(Search) 메서드 만들기

단, 결과는 bool 타입으로 반환

    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True

            elif value < self.current_node.value:
                self.current_node = self.current_node.left

            else:
                self.current_node = self.current_node.right
        return False

# search 테스트
print(BST.search(4))
print(BST.search(9))
print(BST.search(13))
print(BST.search(11))		# True
print(BST.search(2))		# False

 

 

문제2

이진 탐색 트리 삭제(Delete) 메서드 만들기

    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 value < self.current_node.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

 

 

2-1. leaf node 삭제

삭제할 node의 parent node가 leaf node를 가리키지 않도록 함

        # Leaf node의 경우
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None

        return True

 

 

2-2. child node가 하나인 node 삭제

삭제할 node의 parent node가 삭제할 node의 child node를 가리키게 함

        # child node가 하나인 경우
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.right
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        return True

 

 

2-3. child node가 두 개인 node 삭제

삭제할 node의 오른쪽 자식 중 가장 작은 값을 삭제할 node의 parent node가 가리키도록 함

삭제할 node의 왼쪽 자식 중 가장 큰 값을 삭제할 node의 parent node가 가리키도록 함

 

        # child node가 두 개인 경우
        elif self.current_node.left != None and self.current_node.right != None:
            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
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            else:
                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.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
        return True

 

 

전체 완성 코드

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.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 search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False
    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 value < self.current_node.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
        # Leaf node의 경우
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        # child node가 하나인 경우
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right
        # child node가 두 개인 경우
        elif self.current_node.left != None and self.current_node.right != None:
            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
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            else:
                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.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
        return True

 

 

전체 코드 테스트

import random

bst_nums = set()
while len(bst_nums) != 100:
    value = random.randint(0, 999)
    if value != 500:
        bst_nums.add(value)
print(bst_nums)

head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
    binary_tree.insert(num)
    
for num in bst_nums:
    if binary_tree.search(num) == False:
        print('검색 실패!', num)

delete_nums = set()
bst_nums = list(bst_nums)

while len(delete_nums) != 10:
      delete_nums.add(bst_nums[random.randint(0, 99)])
print(delete_nums)

for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('삭제 실패!', del_num)
    else:
        print('삭제 성공', del_num)
        
binary_tree.search(8)
binary_tree.delete(8)