B 트리: Difference between revisions
From IT Wiki
No edit summary |
No edit summary |
||
Line 21: | Line 21: | ||
* 삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요 | * 삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요 | ||
|} | |} | ||
== 같이 보기 == | |||
* [[B+ 트리]]: 순차검색 향상을 위해 Index Set과 Data Set을 구분 | |||
* [[B* 트리]]: 삽입 시 빈번한 노드 분할에 따른 연산 감소 |
Revision as of 00:17, 24 December 2019
- Balanced Tree, B-Tree, B Tree
조건
- 모든 노드는 최대 m개의 자식들을 가진다.
- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.
- 루트노드는 최소 2개 이상의 자식을 가진다.
- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.
- 모든 리프노드들은 같은 높이에 있어야 한다.
- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.
- 시간 복잡도 : O(logN)
비트리의 장단점
장점 | 단점 |
---|---|
|
|