[자료구조]트리(Tree)

트리(Tree)

계층적인 데이터를 표현하는 비선형 자료구조로 ‘루트’에서 시작하여 여러 자식 노드(child Node)로 분기하며 데이터를 관리한다.

트리는 그래프의 한 종류이지만, ‘사이클이 없는 방향성 그래프’로 특정 노드에서 출발해 다른 노드를 방문할 때 루프가 형성되지 않는다.

cf) 루프가 형성되지 않는다 : 어떤 노드에서 출발해서 다시 그 노드로 돌아오는 경로가 없다.
트리는 항상 단방향으로만 연결되며 부모 노드에서 자식 노드로 이어지는 방향이 고정되어 있기 때문에 순환이 일어나지 않는다.

트리 구조는 파일 시스템, 데이터베이스, 네트워크 경로 탐색 등 다양한 분야에서 사용되며 특히 이진 트리 (Binary Tree), 이진 탐색 (Binary Search), 힙(Heap), 트라이(Trie)등 여러 형태로 확장되어 활용된다.

트리의 장점

1. 경로가 유일함
   경로의 탐색이 단순해지므로 최단 경로 계산 등이 필요하지 않게 된다.
2. 탐색 알고리즘의 효율성
   루프가 있는 경우 잘못 된 경로를 반복해서 탐색하는 문제가 일어날 수 있지만
   트리구조는 이로부터 안전하다.
3. 데이터의 계층적 구조 표현

트리의 구성요소

• 노드 : 트리의 각 요소, 데이터를 포함하며 자식 노드오 ㅏ연결된다.
• 루트 노드 : 트리의 최상위 노드. 단 하나만 존재한다.
• 레벨 : 루트 노드에서부터 특정 노드까지의 경로 길이(깊이)를 나타낸다. (루트 노드의 레벨은 0)
• 깊이 : 트리의 루트 노드부터 해당 노드까지의 경로의 길이를 의미한다. 루트에서 리프까지 가장 긴 경로가 트리의 깊이가 된다.
• 차수 : 한 노드가 가지는 자식 노드의 개수, 트리 전체에서 가장 높은 차수를 트리의 차수라고 부른다.

트리의 순회 방식

         A
        / \
       B   C
      / \   \
     D   E   F

1. 전위 순회 (Preorder Traversal)
   • 루트 → 왼쪽 자식 → 오른쪽 자식
   • A → B → D → E → C _> F
2. 중위 순회 (Inorder Traversal)
   • 왼쪽 자식 → 루트 → 오른쪽 자식
   • D → B → E → A → C → F
3. 후위 순회 (Postorder Traversal)
   • 왼쪽 자식 → 오른쪽 자식 → 루트
   • D → E → B → F → C → A
4. 레벨 순서 순회 (Level Order Traversal)
   • 각 레벨의 노드를 왼쪽에서 오른쪽으로 순차적으로 방문
   • A → B → C → D → E → F

트리 구조의 장점

• 계층적 데이터 표현
• 효율적 검색

트리 구조의 단점

• 균형 유지의 필요성
  이진 탐색 트리와 같은 경우 삽입 순서에 따라 트리가 한쪽으로 치우쳐 균형이 깨지면 최악의 경우 O(N)의 시간 복잡도가 발생할 수 있다. (전체순회) 따라서 AVL 트리나 레드-블랙 트리와 같은 균형 트리를 사용해야한다.

• 트리의 재구성
  트리 구조는 삽입, 삭제 시 노드를 재구성해야 하는 경우가 있다.

---

이진 탐색 트리

• 특징
  1. 각 노드는 자식 노드를 최대 2개까지 가질 수 있다.
  2. 각 노드의 값은 왼쪽 가지에 있는 노드의 값보다 크다.
     → 이진 탐색 트리의 최솟값은 가장 위에 있는 노드에서 왼쪽 트리만 탐색하면 찾을 수 있다.
  3. 각 노드의 값은 오른쪽 가지에 있는 노드들의 값보다 작다.
     → 이진 탐색 트리의 최대값은 가장 위에 있는 노드에서 오른쪽 트리만 탐색하면 찾을 수 있다.
  4. 이진 탐색 트리는 데이터를 찾거나 추가할 때, 현재 위치의 데이터와 크기를 비교하여 왼쪽 혹은 오른쪽으로 진행하면서 노드의 위치를 찾는다. 비교 연산은 트리의 높이만큼 수행하게 되므로 따라서 노드 n개가 균형있게 배치되어 있다면 최대 log2n번 비교하기 대문에 계산 시간은 O(log n)이 된다. 다만 트리가 한쪽으로 치우친 구조라면 높이가 높아지므로 O(n)에 가까워지게 된다.