[자료구조] 트리 (Tree)

트리 구조

• 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실제로 어디에 많이 사용? 이진트리(Binary Tree)형태의 구조에서 탐색 알고리즘 구현을 위해 사용

용어

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

이진 트리 & 이진 탐색 트리

• 이진 트리 : 노드의 최대 branch가 2인 트리
• 이진 탐색 트리(Binary Search Tree, BST) : 이진 트리에 추가적인 조건이 있는 트리
  • 왼쪽 노드는 현노드보다 작은 값, 오른쪽 노드는 현노드보다 큰 값을 가지고 있음
  • 주요 용도 : 데이터 검색(탐색)
  • 장점 : 탐색 속도를 개선할 수 있음

 

이진 탐색 트리 구현

노드 클래스

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  

 

이진 탐색 트리 삭제

세가지 case로 나누어서 생각

case1 삭제할 노드가 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
        del self.current_node

 

case2 삭제할 노드가 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
    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

 

case 3-1 삭제할 노드가 parent의 왼쪽, child node를 두개 가지고 있는 경우

• case 3-1-1 삭제할 노드가 parent의 왼쪽, 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 child node가 없을 때
• case 3-1-2 삭제할 노드가 parent의 왼쪽, 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽 child node가 있을 때

    if self.current_node.left != None and self.current_node.right != None: # case3
        if value < self.parent.value: # case3-1
            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.change_node.left

 

case 3-2 삭제할 노드가 parent의 오른쪽, child node를 두개 가지고 있는 경우

• case 3-1-1 삭제할 노드가 parent의 오른쪽, 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 child node가 없을 때
• case 3-1-2 삭제할 노드가 parent의 오른쪽, 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽에 child 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.left = self.current_node.left
            self.change_node.right = self.current_node.right