힙과 레드 - 블랙 트리의 차이점은 무엇입니까?

Question

우리는 힙 모두 레드 - 블랙 트리가 이러한 속성이 있음을 알고 : 검색을위한

1. 최악의 경우 비용이 LGN입니다;
2. 최악의 삽입 비용은 lgN입니다.

빨강 - 검정 나무의 구현과 작동이 어렵 기 때문에 빨강 검정 나무 대신 힙을 사용하는 것이 어떻습니까? 나는 혼란 스럽다.

Answer 1

빨강 검정 나무 :
결정 성있는 균형 전략이있는 이진 검색 트리의 형식입니다. 이 밸런싱은 우수한 성능을 보장하며 항상 O (log n) 시간에서 검색 할 수 있습니다.

힙 :
요소가 내부에 있는지 확인하기 위해 힙의 모든 요소를 ​​검색해야합니다. 최적화를하더라도 검색이 여전히 O (N)라고 생각합니다. 반면에, 이것은 집합 O (1)에서 최소/최대를 찾는 것이 가장 좋습니다.

Answer 2

우선 위키피디아가이 문제를 해결하기에 충분하므로 우선 스택 오버 플로우 관련 질문이 아닙니다. (질문을하기 전에 FAQ를 읽어보십시오)

둘째, 힙의 O (log n)에서 검색 할 수있는 알고리즘이 없으므로 혼동이 더 깊습니다.

힙과 빨강 - 검정 나무는 완전히 다른 시나리오에서 사용됩니다.

RBT는 일반적으로 log n의 순서로 제한되는 다양한 작업을 유지하는 높이 균형 BST를 유지하는 데 사용됩니다. 힙은 우선 순위 큐 구현에 일반적으로 사용됩니다.

Answer 3

O(log n)의 힙에 임의의 요소를 찾을 수 없습니다. 이를 수행하려면 O(n)이 필요합니다. 힙에있는 첫 번째 요소 (가장 작은 것, 말)는 O(1)이고 은O(log n)에 있습니다. 빨강 - 검정 나무와 힙은 용도, 내부 순서 및 구현이 매우 다릅니다. 자세한 내용은 아래를 참조하십시오.

일반적인 사용

레드 - 블랙 트리 :뿐만 아니라 조회 당신이 키에 의해 정렬 된 요소를 원하는 위치를 예를 들어 순서대로 반복 할 수 있도록 사전을 저장. 삽입 및 조회는 O(log n)입니다.

힙 : 우선 순위 큐 (및 힙 정렬). 최소 및 삽입 추출은 O(log n)입니다. 구조에 의해

레드 - 블랙 트리를 부과

일관성 제약 : 전체 순서 : 왼쪽 아이 < 부모 < 바로 아이.

힙 : 지배 : 부모 < 아동 전용.

(당신이 <보다 더 일반적인 순서를 대체 할 수 있습니다 주)

구현/메모리 오버 헤드

레드 - 블랙 트리 : 요소마다 너무 오버 헤드, 트리의 구조를 나타내는 데 사용 포인터. 일반적으로 무료 저장소에 할당 된 여러 노드를 사용합니다 (예 : C++에서 new 사용). 노드는 다른 노드를 가리 킵니다. 로그 조회/삽입을 보장하기 위해 균형을 유지합니다.

힙 : 구조는 암시 적입니다. 루트는 0 위치에, 루트는 1 및 2 등으로 구성되므로 요소 당 오버 헤드가 없습니다. 일반적으로 단일 배열에 저장됩니다.