2022.05.01 TIL

Red-Black tree

• 이진 탐색 트리(BST)의 한 종류
• 스스로 균형(Balancing) 잡는 트리
• BST의 worst case의 단점을 개선
  : 일반 BST에서 최악의 경우(노드가 한쪽으로 편향되어 있는 경우) 삽입, 삭제, 검색의 시간 복잡도는 O(N)임. 모든 노드를 다 확인해야함. 레드블랙 트리는 스스로 균형을 맞춰줘서 트리가 편향되지 않도록 해줘서 O(logN)이 될 수 있도록 해줌.
• 모든 노드는 red 혹은 black

nil 노드란? (보라색 표시)

• 존재하지 않음을 의미하는 노드
• 자녀가 없을 때 자녀를 nil 노드로 표기
• 값이 있는 노드와 동등하게 취급
• RB 트리에서 leaf 노드는 nil 노드

1. 모든 노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil(leaf) 노드는 black
   4. red의 자녀들은 black or red가 연속적으로 존재할 수 없음
   5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외)

노드 x의 black height

• 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트에서 제외)
• #5 속성을 만족해야 성립하는 개념

5번 속성을 이용하여 임의의 노드에서 nil 노드까지의 경로 하나만 골라서 black height를 계산하면 됨.

색을 바꾸면서도 #5 속성을 유지하기

• RB 트리가 #5 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.

RB 트리는 어떻게 균형을 잡는가?
삽입/삭제 시 주로 #4, #5를 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

삽입

overview
0. 삽입 전 RB 트리 속성 만족한 상태
1. 삽입 방식은 일반적인 BST와 동일
2. 삽입 후 RB 트리 위반 여부 확인
3. RB 트리 속성을 위반했다면 재조정
4. RB 트리 속성을 다시 만족

삽입하는 노드는 항상red

삽입 절차 예시

insert(50)

• 노드를 삽입할 때 두 nil 노드의 색은 black으로 고정한다(#3. 모든 nil 노드는 black 조건 만족)
• 현재 루트노드가 red이므로 (#2 루트 노드는 black) 조건 위반. 따라서, 루트 노드를 black으로 바꾸면 해결됨.

insert(20)

• 50보다 작고, 50의 왼쪽 서브트리에 nil 노드이므로 삽입.
• Red-Black 트리의 모든 속성 만족

왜 새로 삽입하는 노드는 red인가?
삽입 후에도 #5 속성을 만족하기 위해, 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외)

insert(10)

• 새로 삽입되는 10은 50(black) 및 20(red)보다 작기 때문에 20의 왼쪽 서브트리에 위치하게 되고, 삽입되는 노드는 red 이므로 #4. 노드가 red라면 자녀들은 black을 위반하게 됨.
• red가 한 쪽으로 몰려 있으니 red 하나를 반대편으로 옮겨줄 수 있다면 해결할 수 있음. 하지만 이러한 구조를 바꿔주는 과정에서 BST의 특징 또한 유지되어야 함(루트노드:20(black), 왼쪽자식:10(red), 오른쪽자식:50(red))
• 구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다.

1. 20과 50의 색을 바꿔준다.
2. 50을 기준으로 오른쪽으로 회전한다.

red 삽입 후 #4 속성을 위반했을 때(case3)

• 삽입된 red 노드가 부모의 왼쪽* 자녀 & 부모도 red고 할아버지의 왼쪽* 자녀 & 삼촌(=부모의 형제)은 black이라면 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽\* 으로 회전한다.
• 오른쪽 왼쪽을 바꿔도 성립함.

insert(40) - #4 속성 위반

• case.3와 다른 부분은 삽입된 노드를 기준으로 할아버지까지의 경로가 꺾였다는 점
• 20을 기준으로 왼쪽으로 회전해서, case3와 동일한 모양으로 바꿔줌.
• 40과 50의 색을 바꾼다.
• 50을 기준으로 회전한다.

red 삽입 후 #4 속성을 위반했을 때(case2)

• 삽입된 red 노드가 부모의 오른쪽* 자녀 & 부모도 red고 할아버지의 왼쪽* 자녀 & 삼촌(=부모의 형제)은 black이라면 부모를 기준으로 왼쪽\*으로 회전한 뒤 case.3의 방식으로 해결함.
• 오른쪽, 왼쪽을 바꿔도 성립

insert(30)

• Red-Black 트리 #4 속성 위반이지만 red가 한쪽으로 몰려 있지 않아서 옮길 수가 없음

• #4를 만족시키면서 #5를 유지하려면 10과 50을 black으로 바꾸고 20을 red로 바꿈.
  RB 트리가 #5 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.
• 20이 루트노드이므로 #2 조건을 위반함. 따라서, 20을 black으로 바꿔줌.

red 삽입 후 #4 속성을 위반했을 때(case1)

• 삽입된 red 노드의 부모도 red & 삼촌(=부모의 형제)도 red라면 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서 다시 확인을 시작함.
• 할아버지의 색이 red로 변경됐는데 만약 루트노드라면 black으로 바꿔줘야 하고, 할아버지의 색이 red로 변경됐는데 할아버지의 부모 노드가 있고, 부모 또한 red라면 #4 조건을 위반하므로 다시 확인을 해야함.

insert(80)
insert(40)

• #4 속성을 위반한 case.1 상태이므로 부모와 삼촌을 black으로, 할아버지는 red로 변경함.
• 이후에 할아버지 노드를 확인해야 하는데 모든 red-black tree의 조건을 만족하므로 상황 종료.

insert(35)

• #4 속성을 위반한 case.2 상태이므로 40을 기준으로 오른쪽으로 회전해서 case.3의 형태로 만들어야 함.
• 이후 30과 35의 색을 바꾸고 30을 기준으로 왼쪽으로 회전함.

insert(25)

• #4 속성을 위반한 case.1 상태이므로 부모와 삼촌을 black으로, 할아버지는 red로 변경함.
• 근데 할아버지 노드인 35에서 확인을 했더니 부모노드가 자신과 동일한 red이므로 #4 속성을 위반한 case.2 상태이므로 50을 기준으로 오른쪽으로 회전해서 case.3의 형태로 만듦.

• #4 속성을 위반한 case.3 상태이므로 20과 35의 색을 바꾸고 20을 기준으로 왼쪽으로 회전함.

회전을 하면서 위치가 없어진 노드들은 자식이 없어진 노드의 자식 노드로 보통 들어가게 되는듯

삭제

1. 삭제 전 RB 트리 속성 만족한 상태
2. 삭제 방식은 일반적인 BST와 동일
3. 삭제 후 RB 트리 속성 위반 여부 확인
4. RB 트리 속성을 위반했다면 재조정
5. RB 트리 속성을 다시 만족

RB 트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요함.
-> 삭제하려는 노드의 자녀(유효한 값을 가지는 자녀)가 없거나 하나라면
삭제되는 색 = 삭제되는 노드의 색
ex) 25 삭제: red 삭제, 80 삭제: black 삭제, 40 삭제: black 삭제

삭제하려는 노드의 자녀가 둘이라면
삭제되는 색 = 삭제되는 노드의 successor의 색
ex) 20 삭제: successor 25 -> red 삭제
: 20의 오른쪽 서브트리 중 가장 작은 값인 25가 자리를 대신하게 됨. 이때 삭제되는 색은 20의 red가 아니라 25가 20의 자리를 대체하면서 20의 색을 물려받게 되기 때문
35 삭제: successor 37 -> red 삭제
: 오른쪽 서브트리에서 가장 작은 값인 37이 35 자리를 대체하게 되고, 35의 색은 유지하고 37 위치에서의 빨간색이 삭제됨.
50 삭제: successor 80 -> black 삭제

속성 위반 여부 확인은 삭제되는 색을 통해

• 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색은 삭제되는 노드의 색
• 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색은 삭제되는 노드의 successor의 색

Red가 삭제될 때

삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

Black이 삭제될 때

#2, #4, #5 속성을 위반할 수 있음.

#2 위반 해결하기

• 루트 노드를 black으로 바꿔줌. 하지만 대부분의 상황에서 #5 속성을 항상 위반하게 됨.

#5 위반 해결하기

• 삭제되는 색이 black이고 #5 위반일 때 extra black 부여
• #5 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여함.
• doubly black: extra black이 부여된 black 노드
• red and black: extra black이 부여된 red 노드
• extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다.

#5. red-and-black 해결하기

• red-and-black을 black으로 바꾸면 해결

• 30은 자녀가 하나라서 삭제되는 색은 30의 black -> #5 위반

• 20과 25가 바로 연결되면서 -> #4 위반

• 삭제된 색은 30의 black이었고, 30을 대체하는 25의 reddp extra black 부여

• 25가 red-and-black이 됐으니 25를 black으로 바꿔주면 종료

#5. doubly black 해결하기

• 결국 extra black을 어떻게 없앨것인지가 관건

• 네 가지 case로 분류할 때의 기준은 doubly black의 형제의 색과 그 형제의 자녀들의 색

Case. 4

• doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때 그 red를 doubly black 위로 옮기고 옮긴 red로 extra black을 전달해서 red-and-black으로 만들면 red-and-black을 black으로 바꿔서 해결

• red를 왼쪽으로 보내기 위해서는 D의 위치가 red가 돼야 하고, 이를 위해 D의 black을 C와 E로 보내고 D를 red로 바꾼다(#5의 규칙을 만족하기 위해).

• c가 red인지 black인지 알 수 없기 때문에 extra black과 같이 표기 해주면 red-and-black 혹은 doubly black으로 생각할 수 있음.

• red가 왼쪽으로 넘어갈 수 있도록 왼쪽으로 회전 전에 B와 D의 색을 바꿔준다.

• B를 기준으로 왼쪽으로 회전한다.
  

<증명>

• A와 C의 extra black을 B로 올려도 #5는 만족함.

• B는 red-and-black이 됐기 때문에 B의 색을 Black으로 바꿔서 extra black을 제거하면 문제 해결
  

doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때, 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결~!

오른쪽* 형제는 부모의 색으로, 오른쪽* 형제의 오른쪽* 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽*으로 회전하면 해결
* 오른쪽 왼쪽을 바꿔도 성립

Case. 3

• doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black일 때 doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 이후엔 case. 4를 적용하여 해결

• E 위치에 red가 오도록 만들기 위해 C와 D의 색을 바꾼 후에 D를 기준으로 오른쪽으로 회전하면 됨.

• C는 B의 색으로 B와 D는 black으로 바꾼 후 B를 기준으로 왼쪽으로 회전하면 해결

doubly black의 형제의 오른쪽* 자녀를 red가 되게 만들어서 이후엔 case. 4를 적용하여 해결

Case. 4

• doubly black의 형제가 black & 그 형제의 두 자녀 모두 black일 떄, doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.

• A와 A의 형제인 D인 black을 모아서 부모에게 전달하게 되면 A와 D에서 black을 모았기 떄문에 A는 여전히 black이고 D는 red가 된다.

• black을 전달받은 B는 red-and-black 혹은 doubly black이 되고, #5 속성은 여전히 만족되고 있음.

• B가 red-and-black이 됐다면 black으로 바꿔주면 상황은 종료되지만 B가 doubly black이 됐다면 B가 루트 노드라면 black으로 바꿔서 해결, 아니라면 case 1, 2, 3, 4 중에 하나로 해결함.

doubly black과 그 형제의 black을 모아서 부모에게 전달하여 부모가 extra black을 해결하도록 위임한다.

Case 1.

• doubly black의 형제가 red일 때, doubly black의 형제를 black으로 만든 후 case 2, 3, 4 중에 하나로 해결

• B를 기준으로 왼쪽으로 회전하면 doubly black A의 형제는 C가 되며 즉, black이 된다.

• 회전 후에도 #5 속성을 만족하려면 왼쪽으로 회전하기 전에 B와 D의 색을 바꿔줌.

• doubly black의 형제는 black이 됐으므로 case 2, 3, 4 중에 해결책을 찾으면 된다.

부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 case 2, 3, 4 중에 하나로 해결.

정리

삭제되는 색이 black 일 때, #5 위반 해결하기

• 삭제되는 색이 black일 때 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여한다.

• 대체한 노드가 red-and-black이 됐다면 black으로 바꿔주면 끝

• 대체한 노드가 doubly black이 됐다면 case 1, 2, 3, 4 중에 하나로 해결함.

삭제 예제

delete(15)

• 삭제되는 노드는 15, 삭제되는 색은 15의 black(15의 자녀가 없기 때문에), 15의 위치를 대체할 nil node에 extra black을 부여함.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 함. doubly black의 왼쪽 형제도 black이고 그 형제의 왼쪽 자녀가 red여서 case. 4에 해당한다.

• 5를 부모 노드의 색인 red로 바꾸고 5의 부모인 10과 5의 왼쪽 자녀인 2는 black으로 바꾼 뒤 10을 기준으로 오른쪽으로 회전함.

• RBtree의 모든 조건 만족함.

delete(33)

• 삭제되는 노드는 33, 삭제되는 색은 33의 black, 33의 위치를 대체할 nil node에 extra black을 부여함.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 한다. doubly black의 왼쪽 형제가 black이고 그 형제의 왼쪽 자녀는 black이고 오른쪽 자녀가 red여서 case. 3에 해당함.

• case. 4의 방식으로 해결할 수 있게 case. 4의 형태로 먼저 만들려면 25와 27의 색을 바꾸고 25를 기준으로 왼쪽으로 회전함.

• Case. 4의 형태가 됐으므로 27의 색을 부모인 30의 색으로 바꾸고 27의 부모와 왼쪽 자녀는 black으로 바꾼 뒤 30을 기준으로 오른쪽으로 회전함.

• RBtree의 모든 조건 만족함.

delete(37)

• 삭제되는 노드는 37, 삭제되는 색은 37의 red, red가 삭제되므로 37 삭제 후 상황 종료.

delete(35)

• 삭제되는 노드는 35, 삭제되는 색은 40의 black, 40의 위치를 대체할 45에 extra black을 부여함. (이때, successor는 오른쪽 서브트리에서 가장 작은 값)

• 45는 red-and-black이 됐기 때문에 45를 black으로 바꾸면 red-black 트리의 모든 속성을 만족하며 상황 종료

delete(40)

• 삭제되는 노드는 40, 삭제되는 색은 45의 black, 45의 위치를 대체할 nil node에 extra black을 부여함.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 한다. doubly black의 형제도 black이고 그 형제의 두 자녀도 black이기 때문에 case. 2에 해당함.

• nil 노드의 extra black과 80의 black을 모아서 50으로 올리고 80은 red로 바꿔준다. 50은 extra black을 가진다.

• 이제 50이 doubly black이 됐기 때문에 이번엔 어떤 case인지 분류해야 한다. doubly black의 왼쪽 형제가 black이고 그 형제의 왼쪽 자녀가 red이기 때문에 case. 4에 해당함.

• 20을 부모 노드의 색인 black으로 바꾸고 20의 부모인 45와 20의 왼쪽 자녀인 5는 black으로 바꾼 뒤 45를 기준으로 오른쪽으로 회전함.

delete(50)

• 삭제되는 노드는 50, 삭제되는 색은 50, 삭제되는 색은 50의 black, 50의 위치를 대체할 80에 extra black을 부여함.

• 80은 red-and-black이 됐기 때문에 80을 black으로 바꾸면 red-black 트리의 모든 속성을 만족하며 상황 종료

delete(80)

• 삭제되는 노드는 80, 삭제되는 색은 80의 black, 80의 위치를 대체할 nil 노드에 extra black을 부여함.

• nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 한다. doubly black의 형제가 red이기 때문에 case. 1에 해당함.

• case. 1의 형태를 바꿔서 case. 2, 3, 4 중에 하나의 형태로 만든다.

• 형제와 부모의 색을 바꾼 뒤 45를 기준으로 오른쪽으로 회전함.

• doubly black의 형제가 black이고 형제의 두 자녀가 모두 black이기 때문에 case. 2의 방식으로 해결함(doubly black의 black과 형제 노드의 black을 부모노드에게 줌).

• 45가 red-and-black이 됐기 때문에 검은색으로 바꿔주면 해결됨.

delete(27)

• 삭제되는 노드는 27, 삭제되는 색은 30의 red, red가 삭제되므로 27 삭제 후 상황 종료

트리의 시간 복잡도