B- 트리와 바이너리 트리의 또 다른 차이점은 B- 트리가 같은 레벨에있는 모든 자식 노드를 가져야하며, 바이너리 트리에는 그러한 제약이 없다는 것입니다. 이진 트리는 최대 2 개의 하위 트리 또는 노드를 가질 수있는 반면 B- 트리에서는 M 개의 하위 트리 또는 노드가있을 수 있습니다. 여기서 M은 B- 트리의 순서입니다.
비교 차트
| 비교 근거 | B- 트리 | 이진 트리 |
|---|---|---|
| 필수 제약 | 노드는 최대 M 개의 자식 노드 (M은 트리의 순서 임)를 가질 수 있습니다. | 노드는 최대 2 개의 하위 트리를 가질 수 있습니다. |
| 익숙한 | 데이터가 디스크에 저장 될 때 사용됩니다. | 레코드와 데이터가 RAM에 저장 될 때 사용됩니다. |
| 나무의 높이 | log M N (m은 M 방향 트리의 순서 임) | 로그 2 N |
| 신청 | 많은 DBMS에서 코드 인덱싱 데이터 구조. | 코드 최적화, 허프만 코딩 등 |
B- 트리의 정의
B- 트리는 균형 잡힌 M- 방향 트리이며 균형 정렬 트리라고도합니다. 그것은 이진 검색 트리와 유사하며, 노드는 inorder traversal에 기반하여 구성됩니다. B- 트리의 공간 복잡도는 O (n)입니다. 삽입 및 삭제 시간 복잡도는 O (log n)입니다.
B- 트리에는 반드시 필요한 특정 조건이 있습니다.
- 나무의 높이는 가능한 한 최소가되어야합니다.
- 나무 잎 위에 빈 나무가 없어야합니다.
- 나무의 잎은 같은 레벨에 있어야합니다.
- 모든 노드는 이탈 노드를 제외하고 최소한의 자식을 가져야합니다.
M 차 B- 트리의 특성
- 각 노드는 최대 M 개의 자식 노드와 최소 M / 2 자식 노드 수 또는 2에서 최대 수를 가질 수 있습니다.
- 각 노드에는 최대 M-1 키가있는 하위 키보다 적은 키가 있습니다.
- 키 배열은 노드 내에서 특정 순서로 이루어집니다. 키의 왼쪽에있는 하위 트리의 모든 키는 키의 선행 키이고 키의 오른쪽에있는 키는 후속 키라고합니다.
- 전체 노드를 삽입 할 때 트리는 두 부분으로 나뉘며 중간 값을 갖는 키는 부모 노드에 삽입됩니다.
- 병합 작업은 노드가 삭제 될 때 수행됩니다.
이진 트리의 정의
이진 트리는 하위 노드에 대해 최대 두 개의 포인터를 가질 수있는 트리 구조입니다. 이것은 노드가 가질 수있는 가장 높은 등급이 2이고 0 또는 1도 노드가있을 수 있음을 의미합니다.
엄격하게 이진 트리, 완전한 이진 트리, 확장 이진 트리 등과 같은 이진 트리의 특정 변형이 있습니다.
- 엄격하게 이진 트리는 각 비단 말 노드가 하위 트리와 오른쪽 하위 트리를 남겨 두어야 만하는 트리입니다.
- 트리는 i가 레벨 인 각 레벨에서 2 개의 i 노드를 갖는 조건을 만족할 때 Complete Binary 트리라고 불립니다.
- 쓰레드 바이너리는 0 개의 노드 또는 2 개의 노드로 구성된 이진 트리입니다.
순회 기법
트리 순회는 각 노드가 체계적으로 한 번만 방문한 트리 데이터 구조에서 수행되는 가장 빈번한 작업 중 하나입니다.
- Inorder-이 트리 탐색에서 왼쪽 하위 트리를 재귀 적으로 방문한 다음 루트 노드를 방문하고 마지막으로 오른쪽 하위 트리를 방문합니다.
- Preorer-이 트리 탐색에서 루트 노드는 처음에는 왼쪽 하위 트리와 마지막으로 오른쪽 하위 트리를 방문합니다.
- 포스트 오더 (Postorder) -이 기술은 왼쪽 하위 트리를 방문한 다음 오른쪽 하위 트리를 방문하고 마지막 루트 노드를 방문합니다.
B- 트리와 Binary 트리의 주요 차이점
- B-tree에서 비 종단 노드가 가질 수있는 자식 노드의 최대 수는 M입니다. 여기서 M은 B- 트리의 순서입니다. 반면, 이진 트리는 최대 두 개의 하위 트리 또는 하위 노드를 가질 수 있습니다.
- B-tree는 데이터가 디스크에 저장 될 때 사용되는 반면, binary tree는 RAM과 같은 빠른 메모리에 데이터가 저장 될 때 사용됩니다.
- B- 트리의 또 다른 응용 분야는 DBMS의 코드 인덱싱 데이터 구조입니다. 반면 Binary 트리는 코드 최적화, 허프만 코딩 등에서 사용됩니다.
- B- 트리의 최대 높이는 logMN (M은 트리의 차수)입니다. 반대로, 이진 트리의 최대 높이는 log 2 N입니다 (N은 노드의 수이고, 기본은 2이므로 2입니다).
결론
B 트리는 바이너리 및 바이너리 검색 트리에 사용됩니다. 그 이유는 CPU가 저 대역폭 채널을 통해 디스크에 연결되어있는 동안 CPU가 고 대역폭 채널로 캐시에 연결되는 메모리 계층 구조 때문입니다. 이진 트리는 레코드가 RAM (작고 빠름)에 저장 될 때 사용되며 B 트리는 레코드가 디스크에 저장 될 때 (크고 느린 경우) 사용됩니다. 따라서 Binary 트리 대신 B-tree를 사용하면 높은 분기 계수와 트리의 높이가 줄어들어 액세스 시간이 크게 줄어 듭니다.
