RBT(Red Black Tree) VS 힙

오늘은 RBT(Red Black Tree) vs 힙 에 대해서 알아 보겠습니다.

---

1. RBT은?

Red Black Tree라고 하며 이진 탐색 트리에 문재점을 고치기 위해 탄생한 기법입니다.

이진 탐색 트리가 한쪽에 치우쳐져있으면 시간 복잡도가 매우 증가하는 모습이있습니다 (기존의 시간 복잡도가 O(logN) 에서 O(N)으로 되는 현상).

이런 경우를 대비하기 위해 레드-블랙 트리가 탄생하였습니다.

 

레드-블랙 트리는 이진 탐색 트리에 항상 넣을때와 뺄때, 그리고 순회할때 모두 O(logN) 을 만족합니다.

원리를 간단하게 설명하면 Red 와 Black으로 노드의 색을 칠하고 데이터를 넣을때와 뺄때 Restructuring과 Recoloring라는 추가 프로세스로 진행하여 균형을 맞춥니다.

 

"루트 부터 리프 노드 까지 블랙 노드의 수는 같다." 라는 기초로 합니다.

 

Red-Black 트리의 조건을 맞추면 루트부터 리프까지의 최소길이와 최대길이의 차이가 2배가 됩니다.

 

출처 : https://sabarada.tistory.com/145

---

2. Heap은?

Heap은 최솟값과 최대값을 빠르게 찾기위해 고안된 자료구조입니다.

최소힙 : 루트를 다른 노드들중에 제일 작은 수를 넣는것입니다.

최대힙 : 루트를 다른 노드들 중에 제일 큰 수를 넣는 것 입니다.

 

 

---

3. 둘의 공통점 및 차이점

공통점 : 힙과, RBT는 둘다 이진트리를 사용한다는 점입니다. 하지만 트리를 사용하는 방식이 매우 다릅니다.

둘다 이진 트리를 사용한다는 점에서는 최고 노드 즉 root 노트가 최대값, 최소값이라는 것은 다름이없습니다.

 

차이점 : 차이점은 표를 통해서 보여 드리도록 하겠습니다.

 

RBT	힙
최대값 최소값을 확인하는데 O(1)의 시간이 걸립니다. 데이터를 가져오는데 O(logN)이 소모됩니다. 삽입 삭제에 대해서도 O(logN)의 시간이 소요됩니다. 특정 데이터를 탐색하기 위해 전체적인 정렬이 되있기 때문에 O(logN)의 시간이 걸립니다.	최대값 최소값을 확인하는데 O(1)의 시간이 걸립니다. 데이터를 가져오는데 O(logN)이 소모됩니다. 삽입 삭제에 대해서도 O(logN)의 시간이 소요됩니다. 하지만 특정 데이터를 탐색하는데는 전체적인 정렬을 안했기 때문에 O(N)의 시간이 걸립니다.
특정 Key를 기준으로 사전순으로 정렬된 데이터를 가져올 때 사용(set,map)	우선순위 큐에 사용이됨(Priority_queue) 정렬된 순서의 탐색은 불가
부모 노드는 항상 왼쪽 자식보다는 크며 오른쪽 자식보단 작습니다. Key의 중복은 허용되지 않고 키가 중복되는 값이 들어오면 기존의 값과 교체	최소 힙이면 부모는 자식노드보다 항상 작아야함, 최대 힙이면 부모는 항상 자식보다 커야함, 키의 중복이 존재할수 있음, 형제 노드들간의 규칙이 없습니다.

---

4. C++ 의 사용하는 자료구조

보통 RBT를 사용하는 자료구조는 정렬된 자료구조 즉 map 과 set 입니다.

map과 set은 키로 정렬하여 중복을 허용하지 않는 자료 구조입니다.

unordered_map 과 unordered_set은 해쉬 함수를 사용합니다.

https://chogyujin-study.tistory.com/65

해쉬 테이블(Hash Table)

힙은 보통 Priority_queue 우선순위 큐에 사용됩니다.

C++은 기본적으로 최대힙을 사용하고 있으며 최소 힙을 사용하고 싶으면 데이터 값을 -로 저장하는 방법이 있으며

priority_queue<int, vector<int>, greater<int>> pq; 이러한 방법으로 사용이 가능합니다.

 

---

5. Ref

https://sabarada.tistory.com/145

우선순위 큐(Heap)과 트리맵(Red black Tree)의 차이