Red-Black Tree

알고리즘 문제를 해결하다가, 이중 우선순위 큐 문제를 만났다. 문제 시간 제한이 6초라고 되어있길래, Binary Search Tree(BST)로 구현하려고, HashMap을 사용했다. 다만 만든 트리 구조가 최악의 경우 더하는 연산이 O(n)이기 때문에, 시간 초과가 났다. AVL이 생각이 났는데, 어떻게 구현하는지를 알지 못해 알아보던 도중 자바에 TreeMap 구조가 Red-Black Tree(RBT)라는 걸 알게되었다. TreeMap 이전에 RBT를 더 자세히 공부하고 싶어 위키트리 내용을 최대한 풀어서 정리했다.