레드블랙 트리 기본 1) 개요 레드블랙 트리(이하 RB트리)는 AVL트리와 같은 '자가 균형 이진 탐색 트리'입니다. 삽입 및 삭제 시 스스로 균형을 유지하여 탐색에 있어 평균 O(log2 N) 만에 수행할 수 있도록 보장해 주죠. 멀쩡한 AVL 트리가 있는데 레드블랙 트리는 왜 등장했을까요? AVL 트리는 매우 엄격한 균형을 유지하는 트리이며, 오버헤드가 큽니다. 특히 높이를 계산하는 과정은 재귀를 통해 일어나기 때문에 자료가 많으면 많을수록 삽입/삭제 시 소모되는 계산 오버헤드는 커지게 되죠. (높이 계산을 매번 하지 않고 노드 자체에 저장하는 최적화 방법이 존재합니다.) 그러나 RB트리는 덜 엄격한 균형을 이룹니다. 심지어 balance factor를 균형의 규칙으로 사용하지도 않기에 시간적, 공간..
