트리(Tree)는 자료 구조 중 하나로, 노드(Node)와 간선(Edge)으로 이루어진 그래프(Graph)의 일종이다. 트리는 계층 구조를 나타내며, 상위 노드인 부모 노드와 하위 노드인 자식 노드로 구성된다.

트리는 이진 트리(Binary Tree)와 같은 특수한 형태도 존재하며, 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다.

알고리즘에서는 트리를 활용하여 다양한 문제를 해결할 수 있다. 예를 들어, 이진 탐색 트리(Binary Search Tree)는 정렬된 데이터를 저장하고 탐색하는 데에 사용된다.

트리는 계층 구조를 나타내며, 이를 활용해 다양한 문제를 해결할 수 있는 강력한 자료 구조이다.

트리(Tree)의 특징

• 트리는 루트(Root) 노드에서 시작하여 자식 노드로 이어지는 간선(Edge)을 통해 계층 구조를 표현한다.
• 각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가질 수 있다.
• 트리는 사이클이 없는 연결 그래프이다.
• 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        new_node = Node(value)
        if not self.root:
            self.root = new_node
        else:
            current_node = self.root
            while True:
                if value < current_node.value:
                    if not current_node.left_child:
                        current_node.left_child = new_node
                        return
                    current_node = current_node.left_child
                else:
                    if not current_node.right_child:
                        current_node.right_child = new_node
                        return
                    current_node = current_node.right_child

위 코드는 이진 탐색 트리를 구현한 예시이다. 이진 탐색 트리는 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 큰 값을 가지도록 구성된다. 이를 통해 탐색 시간을 최적화할 수 있다.

이진 탐색 트리(Binary Search Tree) 삽입

이진 탐색 트리에 원소를 삽입하는 과정은 다음과 같다.

1. 삽입할 값을 루트 노드부터 시작해서, 왼쪽 서브트리에 삽입할지 오른쪽 서브트리에 삽입할지 결정한다.
2. 새로운 노드를 삽입할 위치가 결정되면, 해당 위치에 노드를 삽입한다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        new_node = Node(value)
        if not self.root:
            self.root = new_node
        else:
            current_node = self.root
            while True:
                if value < current_node.value:
                    if not current_node.left_child:
                        current_node.left_child = new_node
                        return
                    current_node = current_node.left_child
                else:
                    if not current_node.right_child:
                        current_node.right_child = new_node
                        return
                    current_node = current_node.right_child

이진 탐색 트리(Binary Search Tree) 삭제

이진 탐색 트리에서 노드를 삭제하는 과정은 상당히 복잡하다. 삭제할 노드의 자식 노드와 부모 노드를 적절하게 업데이트해야 하기 때문이다. 따라서 삭제 과정은 다음과 같은 세 가지 경우로 나뉜다.

1. 삭제할 노드가 단말 노드인 경우
   • 삭제할 노드의 부모 노드와의 연결을 끊는다.