비선형 자료구조 - 트리

트리

- 순환 X, 무방향, 계층적인 구조를 갖는 그래프

- 그래프의 표현(인접 리스트/행렬)과 탐색(DFS/BFS) 알고리즘을 그대로 사용 가능

 

등장 배경

- 정보를 계층적이고 체계적으로 관리하고 싶음

- 분기를 나눠 탐색 속도를

줄일 수 있음 -> 분기로 통해 탐색 방향이 걸러지면 걸러진 분기는 탐색 X

 

트리의 종류

 

1. 이진 트리

- 모든 노드가 최대 2개의 자식을 가짐

ex. 이진 검색 트리, heap, 완전 이진 트리

 

2. N진 트리

- 한 노드가 여러 자식을 가질 수 있음

ex. 파일 시스템 디렉토리 구조

 

3. 균형 트리

- 모든 리프 노드가 비슷한 깊이를 갖도록 설계

ex. AVL 트리, Red-Black 트리

---

이진 트리

각 노드가 최대 2개의 자식을 갖는 트리

 

1. 정 이진트리

- 모든 노드가 0 or 2개인 자식 노드를 가지는 트리

 

2. 완전 이진 트리

- 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리

- 왼쪽에서 오른쪽 순서로 채워져야 하는 규칙 존재

 

 

3. 이진 트리 순회

- 그래프 ⊃ 트리 ⊃ 이진 트리 이기 때문에 BFS/DFS 적용 가능

 

- 아래의 순회 순서 기준은 부모 노드의 방문 순서 

 

3-1. 전위 순회

- 부모 ▷ 왼쪽 ▷ 오른쪽

- 방문 순서를 고려했을 때, DFS와 동일

 

3-2. 중위 순회

- 왼쪽 ▷ 부모 ▷ 오른쪽

 

3-3. 후위 순회

- 왼쪽 ▷ 오른쪽 ▷ 부모

---

탐색

 

1. 순차 탐색

- 처음부터 끝가지 순차적으로 순회하면서 찾고자 하는 데이터 탐색

- 정렬이 되어있지 않아도 적용 가능

- 시간 복잡도: O(N)

 

2. 이진 탐색

- 정렬되어 있는 경우에만 가능

- 검색 범위를 반씩 줄여가며 탐색 ▷ O(logN)

- 단, 많은 삽입/삭제가 발생하는 배열을 정렬 상태로 유지하기 어려움 

▷▷▷▷▷ 이를 보완하기 위해 탄생한 자료구조가 이진 검색 트리

---

이진 검색  트리

왼쪽 < 부모, 오른쪽 > 부모에 맞춰 값을 갖도록 설계된 이진 트리

 

1. 탐색

- 시간 복잡도는 높이에 비례

 

2. 삽입

- 이진 검색 트리에 맞춰 삽입 위치 결정

 

3. 삭제

 

3-1. 자식 노드 X

- 그냥 삭제

 

3-2. 자식 노드 1개

- 자식 노드가 부모 노드 자리로 이동

 

3-3. 자식 노드 2개

- 삭제 시,

- 좌측 트리 중 가장 큰 값 (삭제된 노드보다 작은 값들 중 가장 큰 값) or

- 우측 트리 중 가장 작은 값(삭제된 노드보다 큰 값들 중 가장 작은 값)

- 을 기존 노드 자리로 이동

 

4. 단점

- 데이터 편향 문제

- 데이터가 편향되었을 때, 시간복잡도가 O(N)이 되는 문제 ▷ 이진 트리의 장저밍 퇴색

- 이 문제를 해결하기 위해 AVL 트리, Red-Black 트리 사용

---

균형 트리

이진 검색 트리의 단점을 보완해, 트리 높이가 항상 O(logN)이 되도록 균형을 유지하도록 하는 트리

 

1. AVL 트리

- 노드마다 왼쪽, 오른쪽 서브트리 높이 차이가 최대 1

- 삽입, 삭제마다 불균형을 감지하고, 회전(LL, RR, LR, RL 회전)을 통해 균형 복원

- 탐색, 삽입, 삭제 모두 O(logN) 보장

- 엄격하게 균형을 맞추기에 탐색 성능이 좋지만, 삽입/삭제 시 회전이 자주 발생

 

1-1. LL 회전

1-2. RR 회전

1-3. LR 회전

1-4. RL 회전

 

 

2. Red-Black 트리

 

관리 규칙

- 모든 노드는 Red or Black

- 루트 노드 + 모든 리프노드 >> 검은색

- 빨간색 노드의 자식은 무조건 검은색 > 연속될 수 없음

- 임의의 노드 ~ 리프 노드까지의 검은색 노드 수는 같음 ==>> black height or black depth

 

삽입

- 새 노드는 기본적으로 빨간색으로 삽입 후, 근처 노드의 색을 확인 하여 규칙 위반 시, 색 변경, 회전 등 수행

 

삭제

- 노드를 지우는 과정에서 검은색 노드가 사라지면 black height가 깨지므로 근처 노드의 색 조정 및 회전을 통해 균형 유지

 

특징

- 노드 색을 Red, Black으로 칠해, 루프에서 리프까지 가는 경로상의 검은 노드수를 동일하게 유지

- 삽입, 삭제 시 색상 변경, 회전 등을 통해 균형 유지

- 탐색, 삽입, 삭제 모두 평균 O(logN) 보장

- AVL 보다 회전이 적어 실제 구현에서 많이 사용됨

---

Heap 

- 완전 이진 트리 형태로 구성된 자료구조

- 삽입 시, 높이가 낮은 곳 -> 높은곳, 왼쪽 -> 오른쪽의 규칙성대로 삽입 진행

- 삭제 시, 루트노드의 값을 삭제하는 과정(heap을 사용하는 이유)

- 부모 노드와 자식 노드 간의 대소 관계를 만족

- 최소힙 : 부모 < 자식

- 최대힙 : 자식 < 부모

- 최대/최소 값을 빠르게(O(1)) 얻을 수 있고, 삽입/삭제 시, O(logN)

 

 

Heap VS 이진 검색 트리

 

- 두 자료구조 모두 이진트리 기반

- 힙은 완전 이진 트리 => 최댓값, 최솟값에 대한 접근

- 이진 검색 트리는 완전 이진 트리가 아님 => 빠른 탐색, 삽입, 삭제에 활용