주니어 백엔드 개발자 인터뷰

# 레드-블랙 트리(Red-Blck Tree)

# 레드-블랙 트리란?

레드 블랙 트리

  • 레드 블랙트리는 자가 균형 이진 탐색 트리(balanced binary search tree)입니다.
  • 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용됩니다.
  • 특정 조건을 만족시켜야합니다.

# 레드-블랙 트리의 조건

  1. 모든 노드는 빨간색 혹은 검은색이다.
  2. 루트 노드는 검은색이다
  3. 모든 리프 노드(NIL)들은 검은색이다.
  4. 빨간색 노드의 자식은 검은색이다. (== 빨간색 노드가 연속으로 나올 수 는 없다)
  5. 모든 리프 노드에서 Black Depth는 같다. (== 리프노드에서 루트노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다)

NIL란?

NIL : null leaf로 자료를 갖지 않고 트리의 끝을 나타내는 노드를 말합니다.

# 레드-블랙 트리의 삽입

레드 블랙트리에 새로운 노드를 삽입할 때, 새로운 노드는 항상 빨간색으로 삽입해야합니다.
그러면 4번 조건이 위배되는 상황이 발생하는데 이때 Restructuring이나 Recoloring을 통해 이를 해결해야 합니다.

DoubleRed발생 해결방법
이때, 앞으로 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드(부모의 형제 노드)를 U(Uncle)라고 칭하겠습니다.

  • Restructuring

    • Restructuring은 삼촌의 노드가 검은색일때 수행하면 됩니다.

    • Restructuring 과정

      1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
      2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
      3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

    • 예시
      Restructuring
      그림과 같이 부모노드가 레드이고 삼촌노드가 블랙일 때, N,P,G를 오름차순으로 정렬합니다.
      3이 중간값이되었으니, 3을 부모노드로 바꾸고 2와 5를 자식 노드로 바꿉니다. 이때, 원래 5의 자식이였던 7은 그대로 5를 따라갑니다.
      마지막으로 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식인 2와 5의 색을 빨간색으로 바꿔주면 Double Red문제가 해결됩니다.

  • Recoloring

    • Recoloring은 삼촌의 노드가 빨간색일때 수행하면 됩니다.
    • Recoloring 과정
      1. 새로운 노드(N)의 부모 노드(P)와 삼촌노드(U)를 검은색으로 바꾸고 조상노드(G)를 빨간색으로 바꾼다.
        1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
        2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.
    • 예시
      Recoloring
      그림과 같이 부모노드와 삼촌노드가 다 레드일 때, 부모노드와 삼촌노드를 블랙으로 조상노드를 빨간색으로 변경합니다.
      변경 뒤에 조상노드가 root노드인데 빨간색이 되었으니 조상노드를 다시 검은색으로 변경해줍니다.
    • 예시2
      Recoloring2
      앞선 예제의 조상노드가 root노드가 아닐 경우에는, 조상노드에서 Double Red문제가 발생하게 됩니다.
      이 경우에는 다시 Restructuring와 Recoloring 중 어느 것으로 해결할 지 선택하고 그 방법에 따라 문제를 해결해주면 됩니다.
      이 예제의 경우에는 부모노드와 삼촌 노드가 레드여서 다시 Recoloring을 진행했습니다.

레드-블랙트리 시뮬레이터 페이지

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
-> 레드 블랙 트리에 원소를 삽입하는 과정을 확인할 수 있는 사이트입니다.

# 레드-블랙 트리의 시간복잡도

균형잡힌 트리이기 때문에 탐색, 삽입, 삭제가 모두 O(log n)입니다.

# 레드-블랙 트리를 활용한 사례

  • Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있습니다.
  • 자바의 TreeSet과 TreeMap은 레드-블랙 트리를 베이스로 구현했습니다.
  • Map에서 HashMap의 Separate Chaining(충돌 처리 기법 중 하나, LinkedList로 Hash 충돌을 해결하는 방법)에서 사용됩니다.

# 참고자료

출처: https://code-lab1.tistory.com/62 [코드 연구소:티스토리]
출처: https://junboom.tistory.com/18

← B 트리 & B+ 트리 (B-Tree & B+Tree) →