B 트리에 등호가있는 노드 삽입

Question

빈 B 트리에 3을 삽입하려고합니다. t = 3. 일부 애플릿을 온라인으로 시도했지만 모두 4 번 삽입 한 다음 4 번만 삭제합니다. 의사 코드를 완전히 이해하지 못했기 때문에 CLRS에서 구현 된 방식입니까?

Answer 1

N이 3이되고 네 번째 삽입을 수행하면 루트 노드가 분할되어 최소한 N/2 노드가 나머지 각 새 노드에 있어야합니다. 따라서 결과는 루트에 1 개의 키가있는 트리 여야하고, 중복 키가 기존 복제본의 앞뒤에 위치하는 것으로 간주하는지에 따라 각각 1과 2 개의 키가있는 두 개의 잎이 있어야합니다. 일반적으로 그것은 이후 것입니다 ...