오늘 알아볼 것은 레드블랙트리의 간단한 개념이다. 레드블랙트리는 STL map 자료구조에 사용되는 자료구조이고, 자동으로 균형을 잡아주는 트리이다. 균형을 잡는 것이 왜 중요할까? 라는 질문에 대해 그림을 하나 그려보겠다. 다음과 같은 이진트리가 있다고 가정해보자. 내가 찾고자 하는 값은 5이다. 위의 트리는 균형이 잡혀있지 않은 트리이기 때문에, 5까지 접근하기 위해서는 3번의 이동이 필요하다. 하지만, 균형잡힌 트리의 경우 어떻게 되는지 살펴보자. 다음과 같은 트리의 경우 어떤 경우에도 3번의 이동까지 하지 않고 모든 원소에 접근할 수 있다. 이처럼, 균형 잡힌 트리는 알고리즘의 성능에 큰 도움을 준다. 위의 설명을 좀 더 깔끔하게 하자면, 이진탐색트리의 경우 저장 또는 탐색에 평균적으로 O(logN..
