완벽한 이진 트리 : DSW 및 RB 균형 트리

Question

DSW 알고리즘 또는 적색 검정 균형 트리를 사용하여 이진 검색 트리를 전처리하고 완벽한 이진 트리로 변환 할 수 있음을 알고 있습니다.

이 두 방법은 시간 복잡성과 어떻게 다른가요?

하나의 방법을 다른 방법으로 사용하는 이점을 보여주는 몇 가지 예제/응용 프로그램을 제공 할 수 있습니까?

Answer 1

DSW는 정적 알고리즘입니다. 한 번 사용하면 트리가 변경되지 않을 것으로 예상됩니다. 나무를 완벽하게 균형 잡히기 위해 O (N) 시간이 걸리므로 사용할 수는 있지만 수정하지 않을 것으로 예상됩니다. 당신은 여전히 ​​그것을 할 수 있지만 완벽하게 균형 잡힌 속성은 사라질 것입니다. 트리를 더 많이 수정할수록 트리가 더 잘 수행됩니다.

레드 - 블랙 트리는 동적 데이터 구조입니다. 그것은 O (log (N))에서 기본 연산을 수행하지만, 물론 완벽하게 균형 잡힌 나무만큼 좋은 성능을 발휘하지는 못합니다. 가장 중요한 것은 Red-Black 나무가 파리에서 수정 될 수 있으며 여전히 조작에 O (log (N))가 필요할 것입니다.

따라서 두 가지 접근 방식은 사용 사례가 다릅니다. 희망이 도움이됩니다.

Answer 2

DSW는 전체 BST (불균형)를 만든 다음 많은 수의 조회를 수행하려는 경우 유용합니다 (균형이 조정 된 BST에서). RB 트리는 발생하는 모든 것을 섞어서 추가/제거/조회 할 때 유용합니다.

RB 트리는 대부분 균형이지만 DSW는 완전한 이진 트리입니다 (어쩌면 마지막 레벨 제외).

두 가지 모두 O (log n)를 제공하지만 DSW는 수 한 번만 작업 할 수 있습니다.