[자료구조] 트리

트리란?

트리는 계층적인 구조를 가지며, 여러 개의 노드(node)로 이루어진 비선형 자료 구조이다.

 

노드(Node)

• 트리의 기본 요소로서 데이터와 다른 노드와의 관계 정보를 가지고 있다.
• 각 노드는 하나의 데이터를 포함하고 있으며, 노드 간에는 부모(parent)와 자식(children) 관계가 있다.

 

루트(Root)

• 트리의 가장 상위에 위치한 노드로, 모든 다른 노드는 루트로부터의 경로를 통해 접근할 수 있다.

 

부모와 자식(Parent and Children)

• 트리에서 부모 노드는 자식 노드를 가리키는 관계를 가지고 있다.
• 부모 노드는 자식 노드보다 상위에 있으며, 자식 노드는 부모 노드에 의해 직접적으로 연결된다.

 

가지(Branch)

• 부모 노드와 자식 노드 사이의 연결을 나타내는 선이다.
• 각 노드는 하나의 부모를 가지지만, 여러 개의 자식을 가질 수 있다.

 

잎사귀(Leaf)

• 자식 노드를 가지지 않는 노드를 잎사귀 노드라고 한다.
• 트리의 가장 끝에 위치하며, 트리의 마지막 데이터를 나타낸다.

 

이진트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다. 이진 트리에서 각 노드는 최대 두 개의 자식을 가질 수 있으며, 왼쪽 자식과 오른쪽 자식으로 구분된다.

 

특징

• 각 노드는 최대 두 개의 자식 노드를 가질 수 있다. 왼쪽 자식과 오른쪽 자식 중 하나 또는 둘 다 없을 수도 있다.
• 각 노드는 하나의 부모 노드와 연결되어 있다. 부모 노드에서 해당 노드로 가는 경로를 "왼쪽 서브트리" 또는 "오른쪽 서브트리"라고 부른다.
• 이진 트리는 비선형 자료 구조이며, 계층적인 구조를 가지고 있다. 루트 노드에서 시작하여 리프 노드까지 경로를 따라가면서 데이터에 접근할 수 있다.
• 이진 트리는 재귀적인 성질을 가지고 있다. 각 노드의 서브트리는 다시 이진 트리다.

 

예 : 이진 탐색 트리(Binary Search Tree), 힙(Heap), 허프만 트리(Huffman Tree)

 

# 이진 검색 트리
from typing import Any
class Node:
    def __init__(self, key:Any,item:Any,left:Any=None,right:Any=None)->None:
        self.key = key
        self.item = item
        self.left = left
        self.right = right

class SearchBinaryTree:
    def __init__(self)->None:
        self.root = None

    def search(self,key:Any)->Any:
        start = self.root
        while True:
            if start == None :
                return None # 진행 할 수 없음
            if key == start.key: # 찾은 경우
                return start
            elif key < start.key: # 키보다 크면
                start = start.left
            else: # 키보다 작으면
                start = start.right
    
    def add(self,key:Any,item:Any)->Any:
        if self.root is None:
            self.root = Node(key, item)
        else:
            self.__addNode(self.root, key, item)
    
    def __addNode(self, currentNode: Node, key: Any, item: Any) -> None:
        if key < currentNode.key:
            if currentNode.left is None:
                currentNode.left = Node(key, item)
            else:
                self.__addNode(currentNode.left, key, item)
        elif key > currentNode.key:
            if currentNode.right is None:
                currentNode.right = Node(key, item)
            else:
                self.__addNode(currentNode.right, key, item)
        else:
            currentNode.item = item 
    
    def delete(self, key: Any) -> None:
        if self.root is None:
            return None
        
        self.root = self.__deleteNode(self.root, key)

    def __deleteNode(self, currentNode: Node, key: Any) -> Node:
        if currentNode is None:
            return currentNode

        if key < currentNode.key:
            currentNode.left = self.__deleteNode(currentNode.left, key)
        elif key > currentNode.key:
            currentNode.right = self.__deleteNode(currentNode.right, key)
        else:
            if currentNode.left is None:
                return currentNode.right
            elif currentNode.right is None:
                return currentNode.left

            # 삭제하려는 노드가 자식 노드를 양쪽 모두 가지고 있는 경우
            # 오른쪽 서브트리에서 가장 작은 값을 찾아와서 대체합니다.
            minNode = self.__findMinNode(currentNode.right)
            currentNode.key = minNode.key
            currentNode.item = minNode.item
            currentNode.right = self.__deleteNode(currentNode.right, minNode.key)

        return currentNode

    def __findMinNode(self, node: Node) -> Node:
        current = node
        while current.left is not None:
            current = current.left
        return current
    
    def dump(self, reverse=False) -> None:
        if reverse is False:
            self.__dumpInOrder(self.root)
        else:
            self.__dumpInOrderReverse(self.root)

    def __dumpInOrder(self, node: Node) -> None:
        if node is not None:
            self.__dumpInOrder(node.left)
            print(node.key, node.item)
            self.__dumpInOrder(node.right)

    def __dumpInOrderReverse(self, node: Node) -> None:
        if node is not None:
            self.__dumpInOrderReverse(node.right)
            print(node.key, node.item)
            self.__dumpInOrderReverse(node.left)

sbt = SearchBinaryTree()
sbt.add(1,"helo")
sbt.add(2,"heo")
sbt.add(3,"ho")
sbt.add(4,"elo")
sbt.add(5,"lo")
sbt.dump()
sbt.delete(3)
sbt.dump()