#4 트리와 이진 탐색 트리

1.  트리(Tree)

 

트리는 계층적인 구조를 표현하는 비선형 자료구조입니다.

하나의 루트 노드에서 여러 자식 노드로 뻗어나가는 구조이며, 순환이 없는 특징이 있습니다.

파일 시스템, 조직도, HTML DOM 등 다양한 분야에서 계층 구조를 표현할 때 사용됩니다.

 

---

트리의 기본 용어

• 루트(Root): 트리의 시작점이 되는 노드
• 노드(Node): 데이터를 담고 있는 단위
• 간선(Edge): 노드와 노드를 연결하는 선
• 리프(Leaf): 자식 노드가 없는 노드
• 부모/자식(Parent/Child): 계층 관계를 나타내는 관계
• 서브트리(Subtree): 하나의 노드와 그 하위 노드들로 구성된 트리
• 높이(Height): 루트에서 가장 먼 리프까지의 거리
• 레벨(Level): 루트로부터의 깊이

 

---

트리의 특징

 

하나의 루트 노드를 기준으로 계층적인 구조를 가짐

• 노드 간의 관계는 일반적으로 일대다(Many)
• 사이클(순환)이 없음
• 부모가 하나이고, 0개 이상의 자식 노드를 가짐

 

---

 

2. 이진 트리(Binary Tree)

 

이진 트리는 각 노드가 최대 2개의 자식 노드를 가지는 트리입니다.

왼쪽 자식(left)과 오른쪽 자식(right)으로 나뉘며, 다양한 탐색 및 트리 기반 알고리즘의 기본 구조가 됩니다.

 

---

이진 트리의 종류

• 포화 이진 트리: 모든 레벨이 완전히 채워져 있고, 모든 노드가 자식 2개를 가짐
• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽부터 순서대로 채워짐
• 편향 이진 트리: 한쪽 방향(왼쪽 혹은 오른쪽)으로만 자식 노드가 연결되어 있는 구조 (ex. 선형)

 

---

 

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

 

이진 탐색 트리는 정렬된 구조를 가지는 이진 트리입니다.

노드의 값이 왼쪽 자식보다 크고, 오른쪽 자식보다 작은 규칙을 따릅니다.

 

---

BST의 조건

 

• 왼쪽 서브트리의 모든 노드는 루트보다 작고
• 오른쪽 서브트리의 모든 노드는 루트보다 큽니다

 

---

BST의 특징

 

• 중복 데이터를 일반적으로 허용하지 않음
• 평균적으로 검색, 삽입, 삭제 모두 O(log n)의 성능
• 단, 트리 구조가 편향되면 O(n)까지 느려질 수 있음 → 이를 방지하기 위한 균형 트리 사용(AVL, Red-Black 등)

 

---

이진 탐색 트리의 시간 복잡도

연산평균최악 (편향 트리)

검색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

 

---

 

4.  트리/이진 탐색 트리의 활용 예시

 

트리 구조는 다음과 같은 분야에서 자주 사용됩니다.

 

• 파일 시스템 구조, 조직도, HTML DOM
• 이진 탐색(Binary Search)
• DFS, BFS 알고리즘 구현
• 힙, 우선순위 큐의 기반 구조
• 데이터베이스 인덱싱 (B-Tree, B+Tree 등)

 

---

 

5.  트리 vs 이진 탐색 트리(BST)

구분트리(Tree)이진 탐색 트리(BST)

구조	자식 노드 개수 제한 없음	노드당 자식 최대 2개
정렬 여부	없음	왼쪽 < 루트 < 오른쪽
검색 속도	느림	평균적으로 빠름 (O(log n))
사용 예시	계층 구조 표현	정렬된 데이터 탐색/삽입/삭제

 

---

 

정리 및 복습 )

• 트리는 순환이 없는 계층 구조를 표현하는 자료구조입니다.
• 이진 트리는 자식 노드를 최대 2개까지 가지는 구조입니다.
• 이진 탐색 트리는 정렬 규칙을 따르기 때문에 탐색, 삽입, 삭제가 평균 O(log n)으로 빠릅니다.
• 하지만 균형이 깨지면 선형 구조가 되어 O(n)까지 느려지기 때문에, 균형 유지가 중요합니다.
• 이를 보완하기 위해 AVL 트리, Red-Black 트리 같은 균형 이진 탐색 트리를 사용하기도 합니다.

 

정렬된 데이터를 빠르게 찾고 싶을 때 → 이진 탐색 트리(BST)

빠른 삽입/삭제와 정렬된 구조 유지가 필요할 때 → 균형 트리(AVL 등)