B 트리: Difference between revisions
From IT Wiki
No edit summary |
(→조건) |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
[[분류: | [[분류:자료 구조]][[분류:데이터베이스]] | ||
;Balanced Tree, B-Tree, B Tree | ;Balanced Tree, B-Tree, B Tree | ||
== 개요 == | |||
* 자가 균형 트리(Self Balancing Tree)<ref>모든 리프노드의 높이를 항상 같게 유지하는 트리</ref>의 일종. | |||
== 조건 == | == 조건 == | ||
* 모든 노드는 최대 m개의 자식들을 가진다. | * 차수가 m인 B 트리는 아래의 조건을 만족해야 한다. | ||
* 루트노드와 리프노드가 아닌 | ** 모든 노드는 최대 m개의 자식들을 가진다. | ||
* 루트노드는 | ** 루트노드와 리프노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다. | ||
* k개의 자식을 가진 | ** 루트노드는 2개 이상의 자식을 가진다. | ||
* 모든 리프노드들은 같은 높이에 있어야 한다. | ** k개의 자식을 가진 노드는 k-1개의 키를 가진다. | ||
* 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다. | ** 즉, 자식을 가진 노드는 최소 m/2-1개에서 최대 m-1개의 키를 가진다. | ||
* 시간 복잡도 : O(logN) | ** 모든 리프노드들은 같은 높이에 있어야 한다. | ||
** 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다. | |||
==특징== | |||
* 탐색 시간 복잡도 : O(logN) | |||
* 노드의 삽입 또는 삭제 연산 후에도 정렬된 자료구조를 보장한다. | |||
== 비트리의 장단점 == | == 비트리의 장단점 == | ||
| Line 21: | Line 29: | ||
* 삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요 | * 삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요 | ||
|} | |} | ||
== 같이 보기 == | |||
* [[B+ 트리]]: 순차검색 향상을 위해 Index Set과 Data Set을 구분 | |||
* [[B* 트리]]: 삽입 시 빈번한 노드 분할에 따른 연산 감소 | |||
Latest revision as of 22:33, 16 September 2021
- Balanced Tree, B-Tree, B Tree
개요[edit | edit source]
- 자가 균형 트리(Self Balancing Tree)[1]의 일종.
조건[edit | edit source]
- 차수가 m인 B 트리는 아래의 조건을 만족해야 한다.
- 모든 노드는 최대 m개의 자식들을 가진다.
- 루트노드와 리프노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다.
- 루트노드는 2개 이상의 자식을 가진다.
- k개의 자식을 가진 노드는 k-1개의 키를 가진다.
- 즉, 자식을 가진 노드는 최소 m/2-1개에서 최대 m-1개의 키를 가진다.
- 모든 리프노드들은 같은 높이에 있어야 한다.
- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.
특징[edit | edit source]
- 탐색 시간 복잡도 : O(logN)
- 노드의 삽입 또는 삭제 연산 후에도 정렬된 자료구조를 보장한다.
비트리의 장단점[edit | edit source]
| 장점 | 단점 |
|---|---|
|
|
같이 보기[edit | edit source]
- ↑ 모든 리프노드의 높이를 항상 같게 유지하는 트리
