이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 사이트와, 다음 두 채널도 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 잔재미코딩 신규 강의 사이트

● 잔재미코딩 뉴스레터 오픈 [구독해보기]

● 잔재미코딩 유투브 오픈 [구독해보기]

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

참고: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html

합리적인 분들과 확연히 다른 좋은 IT 강의를 만들 수 있는 선순환 시스템을 지향합니다