Tree Map (Red-Black Tree)

Tree Map은 앞서 포스팅한 Red-Black Tree의 구조로 이루어져 있다.

따라서 Key의 값을 기준으로 레드블랙 트리의 규칙에 따라 정렬이 이루어져 있다.

Tree Set도 Red-Black Tree의 구조로 이루어져있지만, Tree Set은 값만 저장되어 있다면, Tree Map은 Map의 구조가 더해져서 key-value의 쌍으로 값이 저장된다.

레드블랙 트리에 따라 부모노드보다 작은 것은 왼쪽 자식, 큰 것은 오른쪽 자식이 된다.

자동으로 정렬을 해주기 때문에 Map보다는 성능이 떨어지지만, 정렬이 필요한 경우에는 더 효율적으로 활용할 수 있다.

Priority Queue (Heap)

우선순위 큐는 Heap 기반으로 부모는 자식 노드보다 항상 작아야 한다.(최소 힙 기준)

이런 힙의 특성을 따라 데이터의 최소 또는 최대값을 항상 O(1)의 시간으로 찾을 수 있다.

저장하는 데이터에 따라 우선순위가 되는 기준을 정하여 관리할 수 있지만, 전체 데이터의 탐색은 불가능하다.

하지만 우선순위 큐는 형재 노드간의 규칙은 없기 때문에 최소힙이라면 최솟값, 최대힙이라면 최댓값은 O(1)이지만, 하나의 우선순위 큐로 최소와 최대를 한번에 O(1)로 구할 순 없다.
이렇게 하려면 하나의 데이터를 가지고 최소힙과 최대힙 2가지를 만들어서 사용해야 한다.
(<-> Tree Map은 최소와 최대를 한번에 둘 다 구할 수 있다.)