정렬 된 배열 2-4 + 트리

Question

나는 다음과 같은 질문 도움이 필요 선형 시간에 배열로. 알고리즘은 시간 O (n)에 실행되어야합니다.

선형 시간으로 정렬 된 배열에서 빨간색 검정색 트리를 만드는 방법을 이미 알고 있습니다 (삽입 후 트리를 수정하는 함수의 상각 시간이 O (1)이기 때문에).

그러나이 트릭이 2-4 + 나무를 어떻게 돕는 지 알지 못합니다. 이 나무를 삽입 한 후 상각 된 고정 시간과 관련이 있습니까? (그리고 나는 그것이 무엇인지 모른다 ...)

나는 완전히 틀린가?

그런데 O (n)에서 빨간색 검은 색 나무로 2-4 나무를 만드는 것과 같은 방식으로 본 적이있는 트릭을 사용할 수 없습니다. 2-4까지는 직선적 인 배열이어야합니다. + 트리 알고리즘. 사전

Answer 1

레드/블랙 나무와 2-3-4 B-나무 사이에 밀접한 관계가 있습니다에서

감사합니다. 사실, 두 개는 서로의 등각 투영법입니다. 즉, 2-3-4 B- 트리가 적색 - 검정색 트리로 인코딩 될 수 있으며 그 반대도 마찬가지입니다. This older question에서 자세한 내용을 설명합니다.

이 연결을 사용하면 선형 시간에 리드 블랙 트리를 작성하는 알고리즘을 선형 ime에서 2-3-4 B- 트리를 대신 구성 할 수 있어야합니다. 레드 - 블랙 트리를 만든 다음 반복하여 B- 트리의 구조를 결정하거나 B- 트리를 직접 생성하는 알고리즘을 변경해보십시오.

희망이 도움이됩니다.