📘트리(Tree)란?

트리(Tree) 자료구조는 계층적인 정보를 모델링하는 데 매우 적합한 비선형 자료구조이다. 각각의 요소를 노드(Node)라고 하며, 노드들은 부모-자식 관계로 연결된다. 이러한 연결 방식은 트리가 하나의 루트 노드(Root Node)에서 시작하여, 더 작은 서브트리(Subtrees)로 분화되면서 확장되는 구조를 가지게 한다. 이러한 구조는 자연스럽게 계층적 데이터를 표현하는데 적합하며, 디렉토리 구조와 조직도 등 다양한 분야에서 활용된다.

💡트리(Tree) 관련 용어

노드(Node)

• 트리를 구성하는 기본 요소로, 데이터와 하나 이상의 자식 노드를 가리키는 참조로 구성된다.
• A, B, C, D, E, F, G, H, I, J

간선(Edge)

• 노드와 노드 간의 연결선을 말한다.

루트 노드(Root Node)

• 트리의 최상위에 위치하는 노드로, 부모가 없는 유일한 노드이다.
• A

리프 노드(Leaf Node)

• 자식이 없는 노드로, 트리의 가장 바깥쪽에 위치한다.
• H, I, J

내부 노드(Internal Node)

• 적어도 하나의 자식 노드를 가지는 노드로, 리프 노드를 제외한 모든 노드이다.
• A,B,C,D,E

부모 노드(Parent Node)

• 특정 노드의 직접적인 상위 노드이다.
• 자식 노드를 가진 노드이다.
• H, I의 부모 노드는 D

자식 노드(Child Node)

• 특정 노드의 직접적인 하위 노드이다.
• 부모 노드의 하위 노드이다.
• 노드 D의 자식 노드는 H, I

형제 노드(Sibling Node)

• 같은 부모를 가지는 노드이다.
• H, I는 같은 부모를 가진 형제 노드

서브트리(Subtree)

• 노드와 그 자손들로 구성된 트리이다.
• 트리 안에서 특정 범위를 묶어 하나의 작은 트리를 구성할 수 있다.

깊이(Depth)

• 루트 노드에서 특정 노드까지의 경로 길이이다.
• A의 깊이는 0, B의 깊이는 1, H의 깊이는 3

높이(Height)

• 특정 노드에서 가장 깊은 리프 노드까지의 경로 길이이다.
• 트리의 높이는 루트 노드의 높이로 정의된다.
• 리프 노드의 높이는 0, 루트 노드의 높이는 3

차수(Degree)

• 노드가 가지는 자식 노드의 수이다.
• 트리의 차수는 트리 내 모든 노드의 차수 중 최댓값이다.

💡트리(Tree)의 특징

• 계층적 구조: 트리는 계층적 관계를 나타내는 자료구조로, 각 요소가 하나 이상의 요소와 관계를 가진다.
• 비선형 구조: 트리는 선형 구조가 아니며, 노드 간 다양한 경로가 존재할 수 있따.
• 사이클이 없음: 트리 구조에서는 어떤 노드로부터 시작해 같은 노드로 돌아오는 경로인 사이클이 존재하지 않는다.
• 루트 노드에서부터 데이터에 접근: 모든 노드는 직접적이거나 간접적으로 루트 노드와 연결되어 있으며, 루트 노드를 통해 트리의 모든 데이터에 접근할 수 있다.

📚트리(Tree)의 종류

트리의 종류에는 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree, BST)가 있다. 두 종류는 트리 구조의 특수한 형태로, 데이터의 효율적인 저장과 검색에 널리 사용된다. 이 두 구조는 유사해 보일 수 있지만, 각각의 정의와 용도에 있어서 중요한 차이점을 가지고 있다.

💡이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽 자식과 오른쪽 자식)를 가질 수 있는 트리 구조이다. 이진 트리는 다음과 같이 분류될 수 있다.

완전 이진 트리(Complete Binary Tree)

• 모든 레벨이 노드로 꽉 차있다.
• 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있어야 한다.
• 마지막 레벨의 노드는 왼쪽부터 차례대로 채워져야 하며, 오른쪽에는 빈 공간이 있을 수 있다.
• 배열을 사용하여 효율적으로 표현할 수 있다.
• 완전 이진 트리는 힙(Heap)과 같은 자료구조의 구현에 이용된다.

포화 이진 트리(Full Binary Tree)

• 모든 내부 노드가 두 개의 자식 노드를 가진다.
• 모든 리프 노드가 동일한 깊이 또는 레벨을 가지는 특정을 가졌다.
• 완전히 균형 잡힌 형태로, 모든 레벨이 완전히 채워져 있다.
• 노드의 개수와 트리의 높이 사이에 고정된 관계가 있다.
• 포화 이진 트리는 이론적인 모델링과 알고리즘 설계에 자주 사용된다.

균형 이진 트리(Balanced Binary Tree)

• 어떤 노드의 두 서브트리의 사이의 높이 차이가 최대 1만큼만 나는 트리를 의미한다.
• 트리의 깊이를 최소화하여 탐색, 삽입, 삭제와 같은 동작들이 가능한 한 효율적으로 이루어질 수 있도록 하는 것이다.
• AVL 트리와 레드-블랙 트리는 균형 이진 트리의 대표적인 예이다.
• 자동으로 균형을 유지하는 알고리즘을 구현하여 데이터베이스와 같은 시스템에서 효율적인 탐색과 수정 작업을 가능하게 한다.

💡이진 트리 순회

전위 순회(preorder)

• 현재 노드 -> 왼쪽 자식 -> 오른쪽 자식

def preorder(now):
    if now > len(arr)-1:
        return
    print(arr[now],end=' ') # 전위순회 출력 위치
    preorder(now*2) # 왼쪽 자식
    preorder(now*2+1) # 오른쪽 자식

preorder(1) # 루트 노드 1번 인덱스

후위 순회(postorder)

• 왼쪽 자식 -> 오른 자식 -> 현재 노드

def postorder(now):
    if now > len(arr)-1:
        return
    postorder(now*2)
    postorder(now*2+1)
    print(arr[now],end=' ') # 후위순회 출력위치 (왼쪽 자식 오른쪽 자식 모두 탐색 후 출력)
    
postorder(1)

중위 순회(inorder)

• 왼쪽 자식 -> 현재 노드 -> 오른쪽 자식

def inorder(now):
    if now > len(arr)-1:
        return
    inorder(now*2)
    print(arr[now],end=' ') # 중위순회 출력위치 (왼쪽 자식 탐색 후 출력)
    inorder(now*2+1)
    
inorder(1)

💡이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리는 이진 트리의 한 종류로, 중복되지 않는 특정 순서를 가진 데이터의 효율적인 검색과 정렬을 위해 사용된다.

이진 탐색 트리 특징

• 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들로 이루어진 노드들만 포함된다.
• 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값들로 이루어진 노드들만 포함된다.
• 즉, 노드의 왼쪽 자식은 부모 노드보다 작은 값을 가지고 노드의 오른쪽 자식은 부모 노드보다 큰 값을 가진다.
• 왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리이다.

이진 탐색 트리는 데이터를 정렬된 방식으로 저장하므로 탐색, 삽입, 삭제와 같은 기본적인 동작들을 효율적으로 수행할 수 있다. 평균적인 경우, 이러한 동작들의 시간 복잡도는 O(logn)이다. 여기서 n은 트리에 있는 노드의 수이다. 하지만 최악의 경우 예를 들어, 트리가 한 쪽으로 치우친 경우에는 이러한 동작들의 시간 복잡도는 O(n)이 될 수 있다.

이진 탐색 트리의 동작

• 탐색(Search): 주어진 값을 가진 노드를 찾는다. 탐색을 시작하는 루트 노드부터 탐색하려는 값과 현재 노드의 값을 비교하며, 값에 따라 왼쪽 또는 오른쪽 서브트리로 이동한다.
• 삽입(Insertion): 새로운 값을 가진 노드를 적절한 위치에 추가한다. 트리를 탐색하며 삽입하려는 값이 들어갈 위치를 찾고, 새로운 노드를 그 위치에 연결한다.
• 삭제(Deletion): 주어진 값을 가진 노드를 트리에서 제거한다. 노드를 삭제할 때는 해당 노드가 리프 노드인지, 하나의 자식만 가지고 있는지, 또는 두 개의 자식을 모두 가지고 있는지에 따라 처리 방법이 달라진다.

참고
https://yoongrammer.tistory.com/68
https://mommoo.tistory.com/95