경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
편집을 취소할 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 |
당신의 편집 |
1번째 줄: |
1번째 줄: |
| [[분류:자료 구조]][[분류:데이터베이스]] | | [[분류:자료 구조]][[분류:데이터베이스]] |
| ;Balanced Tree, B-Tree, B Tree | | ;Balanced Tree, B-Tree, B Tree |
|
| |
| == 개요 ==
| |
| * 자가 균형 트리(Self Balancing Tree)<ref>모든 리프노드의 높이를 항상 같게 유지하는 트리</ref>의 일종.
| |
|
| |
|
| == 조건 == | | == 조건 == |
| * 차수가 m인 B 트리는 아래의 조건을 만족해야 한다.
| | * 모든 노드는 최대 m개의 자식들을 가진다. |
| ** 모든 노드는 최대 m개의 자식들을 가진다.
| | * 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다. |
| ** 루트노드와 리프노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다.
| | * 루트노드는 최소 2개 이상의 자식을 가진다. |
| ** 루트노드는 2개 이상의 자식을 가진다.
| | * k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다. |
| ** k개의 자식을 가진 노드는 k-1개의 키를 가진다.
| | * 모든 리프노드들은 같은 높이에 있어야 한다. |
| ** 즉, 자식을 가진 노드는 최소 m/2-1개에서 최대 m-1개의 키를 가진다.
| | * 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다. |
| ** 모든 리프노드들은 같은 높이에 있어야 한다.
| | * 시간 복잡도 : O(logN) |
| ** 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.
| |
| | |
| ==특징==
| |
| * 탐색 시간 복잡도 : O(logN) | |
| * 노드의 삽입 또는 삭제 연산 후에도 정렬된 자료구조를 보장한다.
| |
|
| |
|
| == 비트리의 장단점 == | | == 비트리의 장단점 == |