레드-블랙 트리

이진검색트리는 저장과 검색에 평균 Θ(

))시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다.

 

그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다.

자바의 TreeSet과 TreeMap은 레드-블랙 트리를 베이스로 한 구현을 사용한다.

 

 

레드-블랙 트리의 조건

1. 모든 트리의 노드에 검은색 혹은 빨간색을 색칠한다.
2. 루트 노드는 항상 검은색이다.
3. 모든 리프 노드 들은 검은색이다.
4. 빨간색 노드의 자식은 양쪽 다 항상 검은색이다.
   4.1. 즉, 빨간색 노드는 연달아 나타날 수 없다.
   4.2. 이 규칙을 지키면, 검은색 노드만이 빨간색 노드의 부모가 될 수 있다.
5. 루트 노드에서 어떠한 자식 노드를 타고 가던지 리프 노드에 도달했을 때 항상 같은 수의 검은색 노드를 만나게 된다.

 

 

레드-블랙 트리 삽입

• 레드 블랙 트리에서 모든 새로운 노드는 빨간색 색상을 가진채로 삽입되어야 한다.
  • 추후 레드-블랙 트리의 조건에 맞게 다시 변경한다.
    • 이 과정에서 재색칠, 회전 등이 일어난다.
• 삽입 연산에 드는 시간은 그냥 일반적인 이진 트리와 비슷하다.
• 삽입 연산 이후 레드-블랙 트리의 모든 조건을 체크해봐야 한다.
• 만일 모든 조건이 충족된다면, 다음 연산으로 넘어가고, 아니라면 아래와 같은 연산을 실행하여 레드-블랙 트리로 만들어주어야 한다.
  • 재색칠
  • 회전
  • 재색칠 이후 회전

 

 

레드-블랙 트리 삽입 절차

1. 트리가 비었는지 확인한다.
   1. 트리가 비었다면, 검은색 루트 노드를 삽입한다.
   2. 트리가 비어있지 않다면, 빨간색 리프 노드를 삽입한다.
      1. 새 노드의 부모가 검은색이라면, 연산을 마친다.
      2. 새 노드의 부모가 빨간색이면, 새 노드의 부모의 형제를 확인한다.
         1. 새 노드 부모의 형제가 검은색 혹은 NULL이면, 적절한 회전과 재색칠을 한다.
         2. 새 노드 부모의 형제가 빨간색이면, 재색칠을 한다.

 

 

간단한 의사코드 작성

if 트리가 비었는가?
  검은색 루트 노드 삽입 // 1.1
else
  새로운 빨간색 리프 노드 삽입 // 1.2
    if 새로운 빨간색 리프 노드의 부모가 검은색이 아닌가?
      if 새로운 빨간색 리프 노드의 부모 노드의 형제가 검은색인가?
        회전과 재색칠을 한다. // 1.2.2.1
      else
        while 레드-블랙 트리의 조건을 만족하지 않는가?
          내 부모와 부모의 형제를 검은색으로 칠한다.
          부모의 부모를 빨간색으로 칠한다. // 5. 조건을 맞추기 위함
          // 1.2.2.2

연산 종료 // 나머지 모두