[자료구조] 트리 개념과 종류 (이진 탐색 트리, 트리 응용)

목차

• 트리란?
• 트리 종류
  • 편향 트리 (Skew Tree)
  • 이진 트리 (Binary Tree)
  • 완전 이진 트리 (Complete Binary Tree)
  • 포화 이진 트리 (Perfect Binary Tree)
  • 전 이진 트리 (Full Binary Tree)
• 이진 탐색 트리 (Binary Search Tree, BST)
• 트리 응용

 

---

1. 트리란?

트리는 데이터의 계층적 구조를 노드로 표현한 자료구조이다. 가장 상위 노드를 루트 노드라고 부르며, 하나의 루트 노드를 기준으로 가지처럼 뻗어져 나가는 형태를 지닌다.

 

(특징)

• 트리는 그래프의 한 종류이며, 최소 연결 트리라고도 부른다.
• 노드와 노드를 연결하는 간선으로 구성되며, 노드 N개인 트리는 항상 N-1개의 간선을 갖는다.
• 노드 사이의 경로에는 순환하는 사이클이 존재하지 않는다.
• 부모-자식 관계를 가지는 계층적 구조를 가지며, 자식은 하나의 부모 노드만 가질 수 있다.
• 트리는 단 하나의 루트 노드를 가진다.

 

---

2. 트리 종류

1) 편향 트리 (Skew Tree)

: 트리가 각 레벨에 대해 최소 개수의 노드를 가지면서, 하나의 자식 노드만을 가지는 트리

https://www.geeksforgeeks.org/types-of-binary-tree/

 

 

2) 이진 트리 (Binary Tree)

: 각 노드가 자식 노드를 최대 2개까지 가질 수 있는 트리

https://www.geeksforgeeks.org/types-of-binary-tree/

 

 

2-1) 완전 이진 트리 (Complete Binary Tree)

: 각 레벨의 왼쪽에서 오른쪽으로 빈 공간 없이 노드가 채워진 이진 트리

  (마지막 레벨을 제외하고 모든 레벨의 노드가 채워져 있다.)

https://www.geeksforgeeks.org/types-of-binary-tree/

 

 

2-2) 포화 이진 트리 (Perfect Binary Tree)

: 모든 레벨의 노드가 포화 상태로 차있는 이진 트리

https://www.geeksforgeeks.org/types-of-binary-tree/

 

 

2-3) 전 이진 트리 (Full Binary Tree)

: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리

https://www.geeksforgeeks.org/types-of-binary-tree/

 

---

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

: 효율적인 탐색을 위해 각 노드의 왼쪽 서브 트리에는 노드보다 작은 값만, 오른쪽 서브 트리에는 노드보다 큰 값만 포함되도록 구성하는 이진 트리이다.

 

(특징)

• 중복된 노드를 포함하지 않는다.
• 트리 순회 시 중위 순회 방식을 사용한다. (왼쪽 -> 노드 -> 오른쪽)
• 시간복잡도는 균형 상태일 때 O(logN), 불균형(편향) 상태일 때 O(N)이다.

 

---

4. 트리 응용

• 데이터베이스 인덱싱 : B-Tree, B+Tree
• 힙 자료구조 : PriorityQueue
• 검색 알고리즘 : Trie
• 파일 시스템 : B-Tree, B+Tree