[자료구조] 트리(Tree)

트리(Tree) 구조

• Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 사용된다.

 

트리(Tree)와 관련된 용어

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0 로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타낸다.
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
• Sibling(Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

이진 트리와 이진 탐색 트리(Binary Search Tree)

• 이진트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리(Binary Search Tree): 이진 트리에 다음과 같은 추가 조건이 있는 트리
• 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

출처: https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

 

Node 클래스 구현

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

 

이진 탐색 트리 구현

class BST(self, value):
    def __init__(self, head):
        self.head = head

 

Insert 구현

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node:
                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

 

Search 구현

    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

 

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

 

Case1: Child Node가 없는 노드 삭제

        # self.current_node가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태 
        # Leaf Node삭제(Child 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
            del self.current_node

 

Case2: Child Node가 한개 있는 노드 삭제

        # 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
        # Child Node가 자신보다 작을 때
        if 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
                
        # Child Node가 자신보다 클 때
        if 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

 

Case3: Child Node가 두개 있는 노드 삭제

        # 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 삭제할 Node가 Parent Node보다 작을 경우
            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_parent = self.change_node
                    self.change_node = self.change_node.left
                    
                # 가장 작은 값을 가진 Node의 Child Node가 있을 때
                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.left = self.current_node.left
                self.change_node.right = self.current_node.right
            
            # 삭제할 Node가 Parent Node보다 클 경우
            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
                    
                # 가장 작은 값을 가진 Node의 Child Node가 있을 때
                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

 

전체 코드

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

class BST(self, value):
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node:
                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삭제(Child 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
            del self.current_node
            
        # 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
        # Child Node가 자신보다 작을 때
        if 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
                
        # Child Node가 자신보다 클 때
        if 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
                
        # 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 삭제할 Node가 Parent Node보다 작을 경우
            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_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.left = self.current_node.left
                self.change_node.right = self.current_node.right
            
            # 삭제할 Node가 Parent Node보다 클 경우
            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