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

안녕하세요. 오늘 여러분들과 이야기해볼 주제는 바로 우선순위 큐와 트리맵(TreeMap)의 차이점에 대해서 이야기 해보려고 합니다. 이전 포스팅을 보신 분들이라면 아시겠지만 일단 우선순위 큐는 Heap 자료구조를 이용하고 트리맵은 Red-Black Tree를 이용합니다. 둘 다 트리 구조를 가지고 있기 때문에 어떤 상황에서 어떤 자료구조를 사용해야할지 한번 보도록 하겠습니다.

우선순위 큐

PriorityQueue는 Heap 자료구조를 기반으로 되어있습니다. 먼저 Heap 자료구조란 무엇인지를 확인해보겠습니다. Heap 자료구조는 최솟값, 최댓값을 빠르게 찾기위해 완전 이진 트리를 사용하는 자료구조입니다. 간단히 개념을 설명드리면 최소힙의 경우 root 노드가 값이 제일 작으며 트리는 부모 노드는 자식 노드보다 값이 작음을 항상 만족하는 트리입니다. 그리고 이렇게 Heap 자료구조를 맞추는 힙 생성 알고리즘을 Heapify 알고리즘이라고 합니다.

자세한 내용은 [자료구조] 코드로 알아보는 java의 PriorityQueue with Heap를 참고해주시기 바랍니다.

트리맵(TreeMap)

TreeMap는 내부에 레드-블랙 트리(Red-Black Tree)의 자료구조를 이용하고 있습니다. 레드-블랙 트리는 이진탐색트리의 문제점을 보완한 트리입니다. 이진 탐색 트리의 문제점은 한쪽으로 치우쳐 진다면 기존의 O(logN)의 탐색속도가 최악의 경우 O(N)으로까지 떨어질 수 있습니다. 이런 경우를 보완하기 위해 레드-블랙 트리가 등장했습니다.

레드-블랙 트리는 balanced binary search tree로 항상 넣을때와 뺄때, 그리고 순회에 대해서 모두 O(logN)을 만족합니다. 원리를 간단하게 말씀드리면 레드와 블랙으로 노드의 색깔을 칠하고 데이터를 넣을때(Insert)와 뺄때(Delete) Restructuring과 Recoloring라는 추가 프로세스로 진행하여 균형을 맞춥니다. "루트부터 리프노드까지의 블랙 노드의 개수는 같다."라는 것을 기조로 합니다. 레드-블랙 트리의 조건을 맞추면 루트로부터 리프까지의 최소길이와 최대길이의 차이가 2배 이하로 되게됩니다.

자세한 내용은 [자료구조] 코드로 알아보는 java의 TreeMap을 참고해주시기 바랍니다.

공통점

사실 우선순위 큐와 TreeMap은 공통점으로는 이진 트리(Binary Tree)구조를 이용한다는게 전부입니다. 트리를 사용하는 방법에는 둘다 너무나 큰 차이가 있습니다. 하지만 둘다 이진 트리 구조를 이용한다는 공통점 때문에 최고의 부모 노드, 즉 root 노드에는 최대 또는 최소값이 동일하게 들어가 있다라는 점입니다.

차이점

차이점을 한번 보도록 하겠습니다.

탐색 속도

• 우선순위 큐
  • 최댓값 또는 최솟값 데이터를 확인하는대는 O(1)의 시간이 걸립니다. 하지만 가져올때는 heapify가 필요하기 때문에 O(logN)이 걸립니다. 그리고 삽입 및 삭제에 대해서도 O(logN)의 시간이 소요됩니다. 특정 데이터를 탐색하는데는 전체적인 정렬이 아니기 때문에 O(N)의 시간이 걸립니다.
• 트리맵
  • 최댓값 또는 최솟값 데이터를 확인하는대는 O(1)의 시간이 걸립니다. 데이터를 가져오는데는 O(logN)이 소모됩니다. 그리고 삽입 및 삭제에 대해서도 O(logN)의 시간이 소요됩니다. 특정 데이터를 탐색하는데는 전체적인 정렬 상태이기 때문에 O(logN)의 시간이 걸립니다.

일반적으로 사용되는 곳

• 우선순위 큐
  • 우선순위 큐는 최대 또는 최솟값을 뽑아내는데 사용합니다. 뽑아내는데는 O(1)의 시간복잡도를 가지며 다시 Heapify하는데 O(logN)이 드므로 결과적으로 O(logN)의 시간복잡도로 이를 해결할 수 있습니다. 정렬된 순서의 탐색은 불가능합니다.
• 트리맵
  • 특정 key를 기준으로 사전순으로 정렬된 데이터를 가져올 때 사용합니다. key를 기준으로 특정 데이터를 가져오는데 사용됩니다. key를 기준으로 정렬된 순서로 탐색이 가능합니다.

데이터 저장 구조

• 우선순위 큐
  • 이진 트리 구조입니다. 최소 힙이라면 부모는 자식 노드보다 항상 작아야합니다. 만약 최대 힙이라면 부모는 항상 자식보다 커야합니다. 키의 중복이 존재할 수 있습니다. 형제 노드들간의 규칙은 없습니다.
• 트리맵
  • 이진 트리 구조입니다. 부모 노드는 항상 왼쪽 자식보다는 크며 오른쪽 자식보다는 작습니다. key의 중복은 허용되지 않습니다. 키가 중복되는 값이 들어오면 기존의 값과 교체됩니다.

구현 방법

• 우선순위 큐
  • 배열로 구현되어있습니다. root는 0번째 배열입니다. 그리고 왼쪽 자식은 부모노드 * 2, 오른쪽 자식은 (부모노드 * 2) + 1번째 노드를 유지합니다. 배열로 되어있기 때문에 node간의 이동에 오버헤드가 적습니다.
• 트리맵
  • 트리맵은 객체간의 참조로 구현되어있습니다. Node 객체 안에 또 다른 Node로 parent, left, right를 구현한 후 연결하는 형식입니다. 따라서 노드간의 이동에 우선순위 큐 보다는 오버헤드가 있습니다.

마무리

오늘은 이렇게 우선순위 큐와 트리맵에 대해서 알아보았습니다.

감사합니다.

참조

stackoverflow_what-are-the-differences-between-heap-and-red-black-tree