JEEGOO의 개발 노트

# 개념 이진 탐색 트리이며 자가 균형 이진 탐색 트리이다. 이진 탐색 트리는 값이 편향적으로 구성되는 경우가 있다. 예를 들어 7, 6, 5, 4, 3, 2, 1 순서로 값을 넣으면 한쪽으로 치우진 트리가 만들어진다. 즉, 이진 탐색 트리의 시간 복잡도는 최악의 경우(위 예시) O(트리의 높이=h)만큼의 시간 복잡도를 가진다. 레드-블랙 트리는 위 단점을 색상을 이용한 정렬로 해결하며 O(logN)의 시간 복잡도를 가진다. 또한 균형을 유지하기 위해서 다음의 조건을 만족해야 한다. 노드는 레드 혹은 블랙 중 하나이다. 루트 노드는 블랙이다. 모든 리프 노드(NIL)들은 블랙이다. 레드 노드의 자식 노드들은 항상 블랙이다. (즉, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있으며 레드 노드는 연속적으..