[data-structures] RB 트리, B- 트리 또는 AVL 트리를 언제 선택해야합니까?

B + 트리는 메인 메모리에서도 좋은 범용 순서 컨테이너 데이터 구조라고 생각합니다. 가상 메모리가 문제가되지 않는 경우에도 캐시 친 화성이 자주 발생하며 B + 트리는 특히 순차 액세스에 적합합니다. 연결 목록과 동일한 점근 적 성능이지만 단순한 어레이에 가까운 캐시 친 화성입니다. 이 모든 것 및 O (log n) 검색, 삽입 및 삭제.

그러나 B + 트리에는 삽입 / 삭제를 수행 할 때 노드 내에서 항목이 이동하여 해당 항목에 대한 포인터가 무효화되는 것과 같은 문제가 있습니다. “커서 유지 관리”를 수행하는 컨테이너 라이브러리가 있습니다. 커서는 현재 연결 목록에서 참조하는 리프 노드에 연결되므로 자동으로 수정되거나 무효화 될 수 있습니다. 커서가 하나 또는 두 개 이상인 경우는 거의 없기 때문에 잘 작동하지만 추가 작업은 모두 동일합니다.

또 다른 것은 B + 트리가 본질적으로 바로 그것이라는 것입니다. 필요한지 여부에 따라 리프가 아닌 노드를 제거하거나 다시 만들 수 있지만 이진 트리 노드를 사용하면 훨씬 더 많은 유연성을 얻을 수 있습니다. 이진 트리는 노드를 복사하지 않고 연결 목록으로 변환 할 수 있습니다. 포인터를 변경 한 다음 이제 다른 데이터 구조로 취급하고 있다는 것을 기억하십시오. 무엇보다도 이것은 트리의 O (n) 병합을 상당히 쉽게 할 수 있음을 의미합니다. 두 트리를 목록으로 변환하고 병합 한 다음 다시 트리로 변환합니다.

또 다른 것은 메모리 할당 및 해제입니다. 바이너리 트리에서 이것은 알고리즘과 분리 될 수 있습니다. 사용자는 노드를 생성 한 다음 삽입 알고리즘을 호출 할 수 있으며 삭제는 노드를 추출 할 수 있습니다 (트리에서 노드를 분리하지만 메모리를 해제하지는 않음). B- 트리 또는 B +-트리에서는 분명히 작동하지 않습니다. 데이터는 다중 항목 노드에 있습니다. 얼마나 많은 새 노드가 필요하고 할당 될 수 있는지 알 때까지 노드를 수정하지 않고 작업을 “계획”하는 삽입 메서드를 작성하는 것은 어려운 일입니다.

레드 블랙 vs. AVL? 큰 차이가 있는지 잘 모르겠습니다. 내 라이브러리에는 노드를 조작하기위한 정책 기반 “도구”클래스가 있으며, 이중 연결 목록, 단순 이진 트리, 스플레이 트리, 레드-블랙 트리 및 트레 프 (다양한 변환 포함)에 대한 메소드가 있습니다. 이러한 방법 중 일부는 내가 한 번에 지루했기 때문에 구현되었습니다. treap 방법을 테스트 했는지도 모르겠습니다. 내가 AVL이 아닌 빨강-검정 나무를 선택한 이유는 개인적으로 알고리즘을 더 잘 이해하기 때문입니다. 즉, 알고리즘이 더 간단하다는 의미는 아닙니다. 내가 더 익숙한 것은 역사의 우연 일뿐입니다.

마지막으로, 저는 원래 실험 목적으로 B + 트리 컨테이너 만 개발했습니다. 실제로 끝나지 않은 실험 중 하나이지만 다른 사람들이 반복하도록 권장하는 것은 아닙니다. 주문 된 컨테이너 만 있으면 가장 좋은 방법은 기존 라이브러리에서 제공하는 컨테이너를 사용하는 것입니다 (예 : C ++의 std :: map 등). 내 라이브러리는 수년에 걸쳐 진화했으며 안정적으로 만드는 데 꽤 오랜 시간이 걸렸으며 비교적 최근에 기술적으로 이식 할 수 없다는 사실을 발견했습니다 (WRT 오프셋의 정의되지 않은 동작에 따라 다름).