트리란?
[자료구조] 1. 트리(Tree) - 이진 트리(Binary Tree), 트리 순회(Tree Traverse)
선형 리스트란? [자료구조] 선형 리스트 (Linear List) ● 선형 리스트 (Linear List) - 데이터를 논리적인 순서대로 메모리에 연속하여 저장하는 구현하는 방식 - 데이터의 논리적인 순서와 기억 장소에
toward-the-future.tistory.com
● 이진 탐색 트리 (Binary Search Tree)
- 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것이다.
- 중위 순회를 통해 원소의 키 값을 오름차순으로 얻을 수 있다.
○ 조건
- 모든 원소는 서로 다른 유일한 키를 갖는다.
- 모든 왼쪽 자식들은 부모보다 키 값이 작아야한다.
- 모든 오른쪽 자식들은 부모도 키 값이 커야한다.
○ 탐색 연산
- 탐색할 키 값이 현재 탐색하는 노드의 키 값보다 크면 오른쪽 서브트리로 이동
- 탐색할 키 값이 현재 탐색하는 노드의 키 값보다 작으면 왼쪽 서브트리로 이동
- 탐색할 키 값이 현재 탐색하는 노드의 키 값과 같으면 탐색 성공
○ 삽입 연산
① 삽입할 원소의 키 값이 트리 안에 같은 키 값이 있는지 탐색하여 확인한다.
② 탐색에서 실패하면 그 탐색을 실패한 위치에 원소를 삽입한다.
○ 삭제 연산_삭제할 노드가 단말 노드인 경우
① 삭제할 노드를 탐색한다.
② 노드를 삭제한다.
○ 삭제 연산_삭제할 노드가 자식 노드를 한 개 가진 경우
① 삭제할 노드를 탐색한다.
② 노드를 삭제한다.
③ 노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다.
④ 삭제한 부모 노드의 자리를 자식 노드에게 물려준다.
○ 삭제 연산_삭제할 노드가 자식 노드 두 개 가진 경우
① 삭제할 노드를 탐색한다.
② 노드를 삭제한다.
③ 노드를 삭제하면, 자식 노드들은 트리에서 연결이 끊어져서 고아가 된다.
④ 삭제한 노드의 자리를 자손 노드들 중에서 선택한 후계자에게 물려준다.
# 후계자를 선택하는 방법은 삭제한 노드의 왼쪽 서브트리에서 키 값이 가장 큰 자손 노드를 선택하는 방법과 오른쪽 서브 트리에서 키 값이 가장 작은 자손 노드를 선택하는 방법이 있다.
○ 이진 탐색 트리의 문제점
- 부모의 노드보다 오름차순 혹은 내림차순으로 데이터가 삽입될 경우 트리의 높이가 커진다.
● 균형 이진 탐색 트리 (Balanced Binary Search Tree)
- 이진 탐색 트리의 문제점을 보완하고자 나온 것이 균형 이진 탐색 트리이다.
- 높이를 \(O(log(n))\)으로 제한하여 고안된 것이다.
○ 종류
| 이진의 균형 검색 트리 | AVL 트리 Red-Black 트리 |
| 이진이 아닌 균형 검색 트리 | 2-3 트리 2-3-4 트리 B 트리 |
● AVL 트리
- 노드가 삽입&삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 유지하는 트리이다.
- 각 노드의 BF는 {-1, 0, 1} 값만 가지게 함으로써 왼쪽 서브 트리와 오른쪽 서브 트리의 균형을 항상 유지한다.
○ BF(Balace Factor, 균형 인수)
- 균형의 정도를 표현하기 위해서 사용한다.
- BF = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리 높이
- 즉, 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이
- 단말 노드는 서브 트리가 없으므로 BF는 0이다.
○ 균형을 맞춰주는 재구성 작업(Rebalancing, 리밸런싱)
- 균형이 깨진 노드의 BF가 ' + ' 이면 왼쪽 서브 트리에 문제가 있는 것이다.
- 균형이 깨진 노드의 BF가 ' - ' 이면 오른쪽 서브 트리에 문제가 있는 것이다.
- AVL트리는 삽입&삭제 후에 BF를 확인하여 '회전 연산'을 한다.
| 회전 | 유형 | 원인 | 해결 방법 |
| 단순 회전 (한 번 회전) |
LL 유형 | 불균형 발생 노드의 왼쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 왼쪽으로 쏠려있다. | LL 회전 |
| RR 유형 | 불균형 발생 노드의 오른쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 오른쪽으로 쏠려있다. | RR 회전 | |
| 이중 회전 (두 번 회전) |
LR 유형 | 불균형 발생 노드의 왼쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 왼쪽 서브 트리가 쏠려있다. | LR 회전 |
| RL 유형 | 불균형 발생 노드의 오른쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 오른쪽 서브 트리가 쏠려있다. | RL 회전 |
○ LL 회전
- 문제 구간 중 상위 구간을 오른쪽(시계 방향)으로 회전 시킨다.
○ RR 회전
- 문제 구간 중 상위 구간을 왼쪽(반시계 방향)으로 회전 시킨다.
○ LR 회전
- 문제 구간 중 하위 구간을 1차로 RR 회전을 시켜서 LL유형으로 변환한 다음 LL회전을 적용한다.
○ RL 회전
- 문제 구간 중 하위 구간을 1차로 LL 회전을 시켜서 RR유형으로 변환한 다음 RR회전을 적용한다.
댓글