트리 구조 (Tree)

👑 트리 구조 (Tree)

트리(Tree)란 그래프의 일종으로, 사이클을 가지지 않으며, 계층적 구조를 가지는

노드들의 집합이다. 각 노드들은 수많은 자식 노드를 가질 수 있지만, 루트 노드를 제외하면

부모 노드는 단 하나이다. 트리에서 두 노드 사이를 잇는 경로는 정확히 1개이며, 트리는 사이클이

없는 연결 그래프이기 때문에, n개의 노드가 있다면, n-1개의 간선이 필요하다.

💡 트리 기본 개념

• 루트 노드(Root Node) : 트리의 최상위 노드로, 유일하게 부모 노드가 없는 노드

• 부모 노드(Parent Node) : 자식 노드를 가진 노드

• 자식 노드(Child Node) : 부모 노드에 의해 연결된 하위 노드

• 형제 노드(Sibling Node) : 같은 부모 노드를 공유하는 노드들

• 리프 노드(Leaf Node) : 자식이 없는 노드로 트리의 말단을 이루는 노드

• 서브트리(Subtree) : 하나의 노드와 그 노드의 모든 자식 노드들로 이루어진 트리 구조

• 레벨(Level) : 루트 노드를 0레벨로 하고, 그 아래로 각 계층이 1씩 증가하는 구조
  (루트 노드의 레벨에 따라 달라질 수 O)

💡 트리의 종류

트리의 종류에는 이진 트리, 이진 탐색 트리, AVL 트리, 힙(Heap), 레드-블랙 트리 등

다양한 트리가 존재하며, 각자의 특징들을 가지고 있어, 다양한 자료구조와 알고리즘에서 사용된다.

🌳 이진 트리

각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리를 이진트리(Binary Tree)라 한다.

최대 2개의 자식 노드를 가지며, 자식이 없을 수도, 1개만 있을 수도 있다. 이진트리의 종류에는

정 이진 트리(Full Binary Tree), 포화 이진 트리(Perfect Binary Tree), 완전 이진 트리

(Complete Binary Tree) 등이 존재한다.

• 정 이진 트리(Full Binary Tree)

  • 트리의 모든 노드가 0 or 2개의 자식 노드를 가지는 트리이다.

  • 자식을 하나만 가지는 노드가 없어야 한다.

• 완전 이진 트리(Complete Binary Tree)

  • 트리에서 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드가
    왼쪽으로 몰려 있는 트리

  • 마지막 레벨 h에서 $ 1 ~ 2^h - 1 $ 개의 노드를 가질 수 있다.

• 포화 이진 트리(Perfect Binary Tree)

  • 모든 노드가 2개의 자식 노드를 가지며, 모든 리프 노드가 동일한 레벨을 가지는 트리이다.

  • 정 이진 트리이면서 완전 이진 트리인 이진트리이다.

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

이진 탐색 트리 (BST)란 이진 트리의 일종으로, 각 노드의 왼쪽 자식 노드는 해당 노드보다 작은

값을, 오른쪽 자식 노드는 큰 값을 가지는 특징을 가진다. 즉, 어떠한 노드의 왼쪽 서브트리의 값들은

모두 해당 노드보다 작으며, 오른쪽 서브트리의 값들은 모두 큰 값들을 가진다.

💡 트리의 순회 (Traversal)

트리의 순회란 트리 구조를 따라 모든 노드를 방문하는 과정을 의미한다. 트리의 순회 방법에는 다양한

방법들이 존재하며, 레벨 순회, 전위 순회, 중위 순회, 후위 순회 등이 대표적이다.

트리를 코드로 구현하는 방법에도 다양한 방법들이 존재한다. 클래스나 구조체를 이용하여 구현할 수도

있지만 간단하게 배열을 통해서도 구현이 가능하다.

// class를 사용한 구현
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
      data = val;
      left = nullptr;
      right = nullptr;
    }
};

// 배열을 사용한 구현
// 왼쪽 자식, 오른쪽 자식, 부모를 저장할 배열을 만들어 구현
// 각 인덱스가 노드이며, 인덱스의 자식, 부모를 저장
int left_child[9] = {0, 2, 4, 0, 0, 7, 0, 0, 0};
int right_child[9] = {0, 3, 5, 6, 0, 8, 0, 0, 0};
int parent[9] = {0, 0, 1, 1, 2, 2, 3, 5, 5};

✔ 레벨 순회(Level-order Traversal)

레벨 순회는 말 그대로 트리의 레벨 순으로 방문하는 순회이다. 간단하게 루트 노드에서 BFS를 돌리면

그것이 바로 레벨 순회이다.

✔ 전위 순회(Preorder Traversal)

전위 순회는 재귀적으로 다음과 같이 정의할 수 있다.

1. 현재 정점을 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

void preorder(Node* node) const {
    if (node == nullptr) return;

    cout << node->data << " ";
    preorder(node->left);  // 왼쪽 서브트리 전위 순회
    preorder(node->right); // 오른쪽 서브트리 전위 순회
}

✔ 중위 순회(Inorder Traversal)

중위 순회도 재귀적으로 다음과 같이 정의가 가능하다.

만약 트리가 이진 탐색 트리라면 크기 순으로 방문하게 된다.

1. 왼쪽 서브트리를 중위 순회한다.
2. 현재 정점을 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

void inorder(Node* node) const {
    if (node == nullptr) return;

    inorder(node->left);  // 왼쪽 서브트리 중위 순회
    cout << node->data << " ";
    inorder(node->right); // 오른쪽 서브트리 중위 순회
}

✔ 후위 순회(Postorder Traversal)

후위 순위 역시 재귀적으로 정의한다.

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 현재 정점을 방문한다.

void postorder(Node* node) const {
    if (node == nullptr) return;

    postorder(node->left);  // 왼쪽 서브트리 후위 순회
    postorder(node->right); // 오른쪽 서브트리 후위 순회
    cout << node->data << " ";
}