파이썬과 컴퓨터 사이언스(알고리즘) - . 이진 트리 탐색 (Binary Tree Search)

12. 이진 트리 탐색 (Binary Tree Search)

이진 트리(Binary Tree)

  • 모든 노드가 최대 두 개의 자식 노드를 가지고 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!

이진 트리 특징을 생각하면, 탐색 속도를 높일 수 있음

이진트리와 정렬된 배열간의 탐색 비교

어떻게 구현할까? -- 부득이 객체가 가장 구현하기 쉬움

노드 클래스 만들기

In [ ]:
class Node:
    def __init__(self, value):
        self.value = value
        self.left, self.right = None, None    # 이렇게도 한번에 여러 변수를 초기화할 수 있음


이진 트리에 데이터를 넣는다면? 이진 트리의 특징에 맞게 넣어줘야 함

  • 링크드 리스트와 유사함 (복잡)
In [ ]:
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(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.right = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.left = Node(value)
                    break
In [ ]:
head = Node(1)
binary_tree = NodeMgmt(head)
In [ ]:
binary_tree.insert(2)

이진 트리 탐색

In [ ]:
class NodeMgmt:
    def __init__(self, node):
        self.head = node
    
    def insert(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 search(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    
In [ ]:
head = Node(1)
binary_tree = NodeMgmt(head)
binary_tree.insert(2)


In [ ]:
binary_tree.search(2)

이진 트리에 있는 데이터를 삭제한다면? (초심화)

  • 경우의 수가 많아서 매우 복잡함
In [ ]:
class NodeMgmt:
    def __init__(self, node):
        self.head = node
    
    def insert(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 search(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 delete(self, value):
        self.current_node, self.parent = self.head, self.parent
        while self.current_node:
            if self.current_node.value == value:
                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

        # case1 
        if self.current_node.left == None and self.current_node.right == None:
            if self.parent.value > value:
                self.parent.left = None
            else:
                self.parent.right = None
        
        # case2
        if self.current_node.left != None and self.current_node.right == None:
            if self.parent.value > 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 self.parent.value > value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        # case3
        if self.current_node.left != None and self.current_node.right != None:
            if self.parent.value > value:
                self.parent.left = self.current_node.right
                self.added_node = self.current_node.right
                self.added_node_parent = self.current_node.right                
                while self.added_node.left != None:
                    self.added_node_parent = self.added_node
                    self.added_node = self.added_node.left
                self.added_node_parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.right
                self.added_node = self.current_node.right
                self.added_node_parent = self.current_node.right                
                while self.added_node.left != None:
                    self.added_node_parent = self.added_node
                    self.added_node = self.added_node.left
                self.added_node_parent.left = self.current_node.left
In [ ]: