[Algorithm] Red Black Tree - 1

오늘 알아볼 것은 레드블랙트리의 간단한 개념이다.

 

레드블랙트리는 STL map 자료구조에 사용되는 자료구조이고, 자동으로 균형을 잡아주는 트리이다.

 

균형을 잡는 것이 왜 중요할까? 라는 질문에 대해 그림을 하나 그려보겠다.

불균형 이진트리

다음과 같은 이진트리가 있다고 가정해보자. 내가 찾고자 하는 값은 5이다. 위의 트리는 균형이 잡혀있지 않은 트리이기 때문에, 5까지 접근하기 위해서는 3번의 이동이 필요하다. 하지만, 균형잡힌 트리의 경우 어떻게 되는지 살펴보자.

 

균형잡힌 이진트리

다음과 같은 트리의 경우 어떤 경우에도 3번의 이동까지 하지 않고 모든 원소에 접근할 수 있다. 이처럼, 균형 잡힌 트리는 알고리즘의 성능에 큰 도움을 준다. 

위의 설명을 좀 더 깔끔하게 하자면, 이진탐색트리의 경우 저장 또는 탐색에 평균적으로 O(logN)의 시간이 소요되지만, 트리의 모양이 균형을 잘 이루지 못할 경우, O(N)의 시간이 소요될 수도 있다. -> 그냥 리스트를 불균형 이진 트리라고 할 수도 있다.

 

레드블랙트리에는 다음과 같은 규칙이 존재한다.

 

1. 노드는 빨간색 혹은 검정색 중의 하나이다.

2. 루트 노드는 검정색이다.

3. 모든 널 포인터는 검정색이다.

4. 빨간색 노드의 자식노드 양쪽은 모두 검정색이다. (즉 빨간색 노드는 연달아 나타날 수 없고, 검정색 노드만이 빨간색 노드의 부모 노드가 될 수 있다.

5. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

레드블랙트리 예

루트노드는 항상 검정색, 검정색의 자식노드는 빨간색, 빨간색 노드의 자식노드는 검정색, 널포인트는 모두 검정색, 위의 설명대로 대충 표현해보면 이런식으로 나타난다. 

 

여기까지 간단하게 설명하고 다음번에는 삽입, 삭제에 따라 균형을 잡는 회전 과정에 대해 알아보도록 하겠다.

 

그래서 대충 포스팅의 순서는 이러하다.

 

1. 간단한 개념 소개

2. 삽입, 삭제에 따른 회전 과정

3. 코드로 직접 구현

 

이건 내가 대학교 3학년 알고리즘 시간에 배웠던 내용이다. 다시 복습하는 차원에서 꼼꼼하게 봐야겠다.