Red Black Tree

Younji Kim / January 2023

한 노드의 값보다 작은 값은 왼쪽에, 큰 값은 오른 쪽에 두는 이진 탐색 트리(BST)의 한 종류인 레드 블랙 트리에 대해 정리한 포스트이다.

Table of contents

• Table of contents
• 기본 개념
• nil 노드
• red black 트리의 속성
• RB 트리는 어떻게 균형을 잡는가?
• RB 트리의 삽입
• RB 트리의 삭제

기본 개념

• 레드 블랙 트리는 스스로 균형을 잡는다는 특징이 있다.
• 이 말은, 이진 트리의 최악의 경우일 때 한 방향으로 노드가 치우쳐질 수 있는데 그런 최악의 수를 피할 수 있다는 뜻이다.
• 최악의 경우일 때 시간 복잡도를 보면, 기존 이진 트리는 O(N)이었다면, 레드 블랙 트리는 O(logN)에 그친다.
• 모든 노드는 red 혹은 black

nil 노드

• 존재하지 않음을 의미하는 노드
• 자녀가 없을 때 자녀를 nil 노드로 표기
• 레드 블랙 트리에서는 nil 노드는 값이 있는 노드와 동등하게 취급됨
• RB 트리에서 모든 leaf 노드(자녀가 없는 노드)는 nil 노드가 된다.

red black 트리의 속성

1. 모든 노드는 red 혹은 black
2. 루트 노드는 무조건 black이다.
3. 모든 nil(leaf) 노드는 black이다.
4. red의 자녀들은 반드시 black이어야 한다. = red가 연속 레벨로 존재할 수 없다. = black은 연속 레벨로 존재할 수 있다.
5. 임의의 노드에서 가장 끝 자손인 nil 노드까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
   • 노드 x의 black height : 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 노드의 수 (5번 속성을 만족해야 성립하는 개념)
   • 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

RB 트리는 어떻게 균형을 잡는가?

삽입/삭제 시 주로 4번, 5번 속성을 위반하게 된다. 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

RB 트리의 삽입

1. 삽입 전은 RB 트리 속성을 만족한 상태이다.
2. 삽입 방식은 일반적인 BST(이진탐색트리)와 동일하다.
3. 삽입 후에 RB 트리 속성을 위반한 게 있는지 확인한다.
4. RB 트리 속성을 위반했다면 재조정한다.
5. RB 트리 속성을 다시 만족시킨다.

• 삽입하는 노드는 항상 처음엔 red이다. e.g. 삽입 후에도 5번 속성(black height)을 만족하기 위해서이다.
• 새 (red)노드 삽입 후 2번 속성을 위반했을 떄 => 루트 노드를 black으로 바꿔준다.
• red 삽입 후 4번 속성을 위반했을 떄 =>

RB 트리의 삭제

1. 삭제 전 RB 트리의 속성을 만족한 상태이다.
2. 삭제 방식은 일반적인 BST와 동일하다.
3. 삭제 후 RB 트리 속성 위반 여부를 확인한다. (삭제되는 색에 따라 확인)
4. RB 트리 속성을 위반했다면 재조정한다.
5. RB 트리 속성을 다시 만족시킨다.

• 어떤 색이 삭제되는 지가 속성 위반 여부를 확인할 때 매우 중요하다. 여기서 삭제되는 색은 단순히 삭제되는 노드의 색을 뜻하는 게 아니다. 삭제하려는 노드의 (유효한 값을 가지는) 자녀가 없거나 하나라면 삭제되는 색은 삭제되는 노드의 색과 같고, 만약 삭제하려는 노드의 자녀가 둘이라면, 삭제되는 색은 삭제되는 노드의 successor(노드가 사라졌을 때 다음 축을 넘겨받을 바로 다음으로 큰 노드)의 색이다. 삭제되는 노드의 색을 successor가 물려받고, 대신 successor의 색이 사라지는 개념이다.
• 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.
• 삭제되는 색이 black이라면 2번, 4번, 5번 속성을 위반할 수 있다.
• 삭제되는 색이 black이고 2번 속성을 위반했을 때, 루트 노드를 black으로 바꾸면 된다.
• 삭제되는 색이 black이고 5번 속성을 위반했을 때, 케이스가 다음과 같이 나뉜다.
  • 삭제되는 색이 black일 때 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여한다.
  • 대체한 노드가 red-and-black이 됐다면 black으로 바꿔주면 된다.
  • 대체한 노드가 doubly black이 됐다면 다음과 같은 네 가지의 케이스 중 하나로 해결한다.