수는

Question

내가 책 모든 다양한에서 읽은 A B 트리의 정의는 절반 이상 전체로 루트 노드를 제외하고 다음

• 모든 노드를했다 포함
• 루트 노드가 인덱스 노드 인 경우 최소한 두 개의 자식이 있어야합니다.

두 번째 특수한 경우는 B 트리가 예를 들어 하나의 키만 가질 수 있고 여전히 유효하다고 가정합니다. 그러나 B 트리에 노드가 많은 경우 루트 노드가 두 개의 하위 트리 만 가질 수 있습니까? B 트리의 보장이 깨지지 않습니까?

Answer 1

그러나 B 트리에 노드가 많은 경우 루트 노드가 두 개의 하위 트리 만 가질 수 있습니까?

예, 다른 모든 내부 노드에는 병합 할 수있는 형제가 있으므로 루트는 특수한 경우입니다.

키를 삭제 한 결과 일부 내부 노드에 너무 적은 자식이 있다고 가정합니다. 일반적인 B-tree 알고리즘에는 두 가지 옵션이 있습니다.이 노드에 형제 중 일부 자식을 가져 오거나 형제를 완전히 병합 (가능하면 결함을 루트로 전파)합니다. 루트에 대한 옵션도 없으므로 최소 요구 사항에서 면제됩니다. 이것은 주어진 키의 최대 높이를 많아야 1만큼 증가 시켜서 점근 적으로 연산을 수행하는 시간에는 영향을 미치지 않습니다.