1. 이진 탐색 트리(BST: Binary Search Tree)
1. 1 속성
1) 노드의 왼쪽 서브트리에는 그 노드보다 작은 값
2) 노드의 오른쪽 서브트리에는 그 노드보다 큰 값
3) 좌우 하위 트리는 각각이 다시 이진 탐색 트리
1. 2 단점
한쪽으로 쏠려있는 편향 이진트리에서는 O(N)의 시간복잡도를 가짐
1. 3 균형 검색 트리 등장 배경
편향 이진 트리의 경우 O(N)의 시간 복잡도를 가짐.
이를 해결하기 위해,
노드의 삽입과 삭제가 일어나는 경우, 자동으로 그 높이를 작게 유지하는 균형 검색 트리가 등장.
2. AVL 트리
(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)
자가 균형 이진 탐색 트리
스스로 균형 잡는 데이터 구조
2- 1 균형 유지 조건
- AVL 트리에서는 두 자식 서브트리의 높이는 항상 최대 1만큼 차이남.
- 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡음
균형인수(BF: Balance Factor)의 개념을 사용
만약 모든 노드에 대하여 균형인수가 -1, 0, 1 뿐이라면 그 트리는 AVL 트리 조건을 만족
노드 T의 균형인수 BF(T) = 왼쪽서브트리의 높이 - 오른쪽 서브트리의 높이
2 -2 균형 잡는 방법 : 회전
삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있음.
회전의 종류에는 총 4가지 존재: LL, RR, LR, RL
검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다.
| 평균 | 최악의 경우 | |
| 공간 | O(n) | O(n) |
| 검색 | O(log n) | O(log n) |
| 삽입 | O(log n) | O(log n) |
| 삭제 | O(log n) | O(log n) |
3. RB 트리
3 -1 속성
1번. 모든 노드는 레드이거나 블랙이다.
2번. 루트 노드는 블랙이다.
3번. 모든 외부 노드는 블랙이다.
4번. 레드 노드는 두 개가 연속해서 등장할 수 없다.
5번. 리프노드에서 루트노드까지 가는 경로에서 방문하는 블랙 노드의 수가 같다.
3 -2 장점
참조:
[자료구조] 균형 탐색 트리 (AVL트리, 레드-블랙 트리)
이전에 검색을 매우 빠르게 할 수 있는 이진 탐색 트리(BST)에 대해 알아보았는데 이진 탐색 트리도 한...
blog.naver.com
https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
레드-블랙 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년
ko.wikipedia.org
https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC
AVL 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로
ko.wikipedia.org
'크래프톤 정글 > TIL' 카테고리의 다른 글
| [5주차] exit(0)와 return의 차이 (0) | 2023.11.10 |
|---|---|
| [4주차] 소수판별 (에라토스테네스의 채) (0) | 2023.11.08 |
| [4주차] C 언어 포인터 주소값 출력 (0) | 2023.11.07 |
| [3주차] 시간복잡도, 공간복잡도 계산 (0) | 2023.10.27 |
| [2주차] 컴퓨터 시스템 1.5 - 1.8 (0) | 2023.10.26 |
