TreeMap (레드 - 블랙 트리)

• TreeMap

우리가 쓰던 HashMap에 이진트리의 기능을 더한 자료구조이다. HashMap처럼 key와 value를 갖는 요소들로 이루어져 있고 key값을 기준으로 이진 탐색 트리처럼 정렬이 이루어진다. 그래서 key값을 기준으로 최솟값과 최댓값을 탐색할 때 시간복잡도 O(logN)으로 탐색이 가능하다. 그러나 이진 탐색 트리에서는 루트값을 기준으로 나머지 요소들이 전부 크거나 전부 작으면 탐색의 시간이 O(N)까지 늘어난다.(트리의 높이만큼의 시간 복잡도가 걸린다) 그래서 TreeMap에서는 이진 탐색 트리의 단점을 보완한 레드-블랙 트리의 자료구조를 이용한다.

레드-블랙 트리

 레드-블랙 트리는 루트노드를 기준으로 균등하게 트리가 완성될 수 있게 규칙에 따라 트리가 만들어진다. (규칙은 https://zeddios.tistory.com/237에 잘 나와있다) 따라서 늘 높이가 logN이 되기 때문에 시간복잡도가 항상 O(logN)이 된다.

 노드를 추가할 때마다 자동으로 정렬이 이루어지고 put 명령어를 통해 노드 추가를, 그리고 remove명령어를 통해 노드 삭제를 할 수 있고 firstEntry, firstKey, lastEntry, lastKey를 통해 최소 Entry, Key값과 최대 Entry, Key값을 가져올 수 있다.

 

 

 

---

reference

 - https://coding-factory.tistory.com/557

 - https://zeddios.tistory.com/237