Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다. 트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다. 균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( \log_{2}{N} \)이기 때문에 빠르게 검색할 수 있다. 레드블랙트리는 아래의 규칙을 만족하도록 조정된다. 1. 노드는 레드 혹은 블랙 중의 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드는 블랙이다. 4. 레드 노드의 자식노드 양쪽은 언제나..