Red-Black 트리 이진 트리에서 편향 이진 트리와 같은 최악의 시간복잡도를 같는 경우를 해결하기 위해 균형 트리인 AVL트리가 존재했었다. Red-Black 트리는 AVL과 동일하게 균형 트리이지만, AVL 트리보다는 덜 균형하다는 특징이 있다. 즉, 균형트리에서 삽입이나 삭제가 많은 경우 Red-Black 트리를 사용하는 것이 유리하며, 탐색이 많은 경우 AVL 트리가 유리하다. 평균과 최악의 상황에서 검색, 삽입, 삭제 등 모두 log(N)의 시간 복잡도를 갖는다. Red-Black 트리의 규칙 Red-Black 트리에는 5가지 규칙이 있다. 해당 규칙을 위배하는 순간 노드 재배치를 진행한다. 규칙은 다음과 같다. 모든 노드는 빨강 또는 검정이다. 루트 노드는 항상 검정이다. 모든 리프 노드는 ..