그 외 트리들
트리들의 정의, 특징, 연산, 장단점
| 트리 종류 | 정의 | 특징 | 지원 연산 | 장점 | 단점 | |
|---|---|---|---|---|---|---|
| 이진탐색트리 (BST) Binary Search Tree |
- 노드의 왼쪽 자식은 부모보다 작고 - 노드의 오른쪽 자식은 부모보다 크도록 정렬된 트리 - 자식 간 순서 기반 |
- 균형을 유지하지 않음 - 탐색, 삽입, 삭제의 평균 시간복잡도가 O(log n) - 최악의 경우여도 O(n) |
- 탐색 : O(log n) - 삽입 : O(log n) - 삭제 : O(log n) |
- 구현이 간단하고 직관적 - 메모리 오버헤드가 적음 - 정렬된 데이터 표현이 간단 |
- 데이터가 정렬된 경우 최악의 경우 발생 - 고르게 분산된 데이터가 필요 |
|
| Splay Tree | - 최근 접근한 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리 - 비균형 허용 |
- 루트에 자주 사용된 데이터를 위치시켜 접근 효율성 향상 - 자주 사용된 데이터에 O(1)의 성능 제공 가능 |
- 탐색, 삽입, 삭제의 평균 시간복잡도가 O(log n) - 최악의 경우여도 O(n) |
- 탐색 : O(log n) - 삽입 : O(log n) - 삭제 : O(log n) - 평탄화 : O(n) |
- 자주 접근하는 데이터를 빠르게 처리 가능 - 균형 유지 비용이 없음. - AVL보다 구현이 간단 |
- 최악의 경우 성능이 O(n) - 균형 상태를 강제하지 않아 탐색에서 비효율 발생 가능 |
| AVL Tree | - 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지하는 이진 탐색 트리 | - 엄격한 균형 유지 - 탐색, 삽입, 삭제가 항상 O(log n) - 삽입/삭제 시 균형 회전 필요 |
- 탐색 : O(log n) - 삽입 : O(log n) - 삭제 : O(log n) 다른 트리는 평균 O(log n)이지만, 이건 O(log n) 보장 |
- 항상 균형 유자 - 탐색 시간이 O(log n)으로 일정 - 데이터 분포에 관계없이 안정적인 성능 |
- 삽입/삭제시 재균형 비용 발생 - 추가 메모리 사용(높이 정보) - 구현이 복잡 |
|
| BB Tree (Balanced Binary Tree) |
- 각 노드 양쪽 서브트리 무게가 균형을 유지하는 이진 탐색 트리를 포괄적으로 지칭 - 모든 하위 트리가 특정 균형 조건을 만족하도록 설계됨 |
- 모든 서브트리가 균형 조건을 만족 - 균형 유지 방법은 구현에 따라 다양 (AVL, Red-Black 포함 가능) - 삽입/삭제시 균형 유지 작업 필요 |
- 항상 균형 유지로 효율적인 탐색 성능 보장 - 다양한 균형 유지 기법을 선택적으로 사용 가능 - 안정적인 삽입, 삭제 성능 |
- 균형 유지 작업으로 인해 삽입/삭제 시 성능 오버헤드 발생 가능 - 구현 복잡성 증가 - 균형 유지방식에 따라 메모리 요구량 증가 가능 |
요약
(1) 이진 탐색 트리
- 단순하고 빠르게 구현 가능
- 데이터가 고르게 분산되지 않을 경우 성능이 저하됨
(2) Splay Tree
- 최근 접근 데이터 처리에 강점이 있음
- 균형 강제가 없어 특정한 경우 비효율적임
(3) AVL Tree
- 균형 유지로 탐색 성능이 안정적임
- 삽입/삭제 비용이 높음
- 구현이 복잡함
(4) BB Tree
- 노드 양쪽 서브트리 무게가 균형을 유지하도록 하는 이진 탐색 트리를 포괄적으로 지칭하는 것
- 균형을 맞추는 데 성능 오버헤드 발생 가능성
- 대신 항상 균형을 맞추기에 효율적인 탐색 가능