[자료구조] 트리

트리 (Tree)

1. 트리 구조

• 트리: Node, Branch로 이루어진 그래프로 사이클을 이루지 않도록 구성한 데이터 구조이다.
• 트리는 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
• 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

 

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

• 이진 트리: 노드의 최대 Branch가 2인 트리.
• 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리와 같이 최대 branch가 2개인 트리이면서, 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있는 경우.

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

 

이진 탐색 트리 예시 (Insert, Search)

# 노드 클래스를 만든다. 

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:                   # 새로 들어온 value < 현재 노드 이면, 현재 노드의 왼쪽 노드가 현재 노드 기준이 된다. 
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:                                             # 현재 노드 왼쪽에 아무 노드도 x -> 새로 들어온 value가 그 왼쪽에 들어 간다. 
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:               # 새로 들어온 value > 현재 노드 이면, 현재 노드의 오른쪽 노드가 현재 노드 기준이 된다. 
                    self.current_node = self.current_node.right
                else:                                             # 현재 노드 오른쪽에 아무 노드도 x -> 새로 들어온 value가 그 오른쪽에 들어 간다.
                    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        

head = Node(2)
BST = NodeMgmt(head)
BST.insert(4)
BST.insert(3)
BST.insert(1)
BST.insert(8)

BST.search(3)

True

삭제 기능 (Delete)

• 케이스에 따라 굉장히 다양하다.

1.  삭제할 노드가 있는지 확인 하는 절차

# 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:  # 찾는 노드가 head인 경우, True를 넣고 종료.
            searched = True
            break
        elif value < self.current_node.value: # 찾는 노드가 더 작으면, 왼쪽 노드를 확인해야 하므로 왼쪽 노드를 current(기준)로 넣는다. 이를 기준으로 다시 while문.
            self.parent = self.current_node
            self.current_node = self.current_node.left
        else:
            self.parent = self.current_node   # 찾는 노드가 더 크면, 오른쪽 노드를 확인해야 한다. 이 오른쪽 노드를 기준으로 다시 while문.
            self.current_node = self.current_node.right

    if searched == False: # 찾는 노드가 존재x -> False 리턴. 
        return False

 

2. 삭제할 노드가 Leaf Node인 경우

# self.current_node : 삭제하길 원하는 노드.
# self.parent.value : 삭제하길 원하는 노드의 parent
# value : 삭제하고자 하는 value
    if  self.current_node.left == None and self.current_node.right == None: # 자식 노드가 없으므로 leaf node이며 if 문이 실행된다.
        if value < self.parent.value: # 삭제할 노드의 parent노드가 삭제하고자 하는 value 보다 클 때, parent의 왼쪽 노드를 삭제. 
            self.parent.left = None
        else:
            self.parent.right = None
        del self.current_node

 

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