크래프톤 정글 6기 TIL - Day 20| RB Tree

RB트리 책을 볼때마다 너무 졸리다..으악

Red-Black Tree

- 이진 탐색 트리(BST)의 한 종류
- 스스로 균형(balancing) 잡는 트리
- BST의 Worst Case의 단점을 개선
- 모든 노드는 Red or Black

 

 

Red Black tree의 속성

1.  모든 노드는 red 또는 black이다.
2.  루트 노드는 black이다
3   모든 nil 노드는 black이다.
4.  노드가 red인 자녀들은 black이다.
5.  임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black의 수는 같다.( 자기 자신은 카운트에서 제외 )

💡nill 노드란?

 - 존재하지 않음을 의미하는 노드

 - 자녀가 없을 때 자녀를 nil 노드로 표기

 - 값이 있는 노드와 동등하게 취급

 - RB 트리에서 leaf 노드는 nil 노드

 

노드 X의 black height → bh(x)

- 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서 black의 수( 자기자신은 카운트에서 제외 )

- #5 속성을 만족해야 성립한다.

 

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

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

 

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

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

 

 

---

새로 삽입하는 노드가 red 인 이유?

---

RB-Tree 삽입

 

Insert(50)

Insert(20) → Insert(10)

 

Insert(40)

 

Insert(30)

 

삽입 Case 정리

CASE 1

CASE 2

CASE 3

 

---

RB-Tree 삭제

삭제되는 색을 통해 속성 위반 여부 확인 : RB 트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요하다!!!

succesor은 노드의 우측 서브트리에서 제일 작은 값을 가지는 노드를 의미한다.

 

✨ 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.
✨ 삭제되는 색이 black이라면 #2,#4,#5 속성을 위반할 수 있다.

 

 

삭제되는 색이 black일 때

#2 위반 해결하기

 

⚠️ 삭제되는 색이 black일 때 특수한 상황을 제외하면 #5 속성을 항상 위반하게 된다.

 

삭제되는 색이 black이고 #5 위반일 때

✨extra black의 역할
경로에서 black의 수를 count할 때 extra black은 하나의 black으로 카운팅된다.

✨어디에 extra black을 부여해야 하는가?
삭제된 색의 위치를 대체한 노드. 삭제된 색은 10의 black이므로, 10의 위치를 대체한 노드인 nil 노드에 extra black을 부여한다.

✨ 삭제되는 색이 black이고 #5 위반일 때, extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다.

 

delete(10)

 

delete(30)

30은 자녀가 하나라 삭제되는 색은 30의 black이다.

30이 삭제되면서 #5 속성위반을 했기 때문에 extra black을 부여한다.

 

 

delete(50)

50은 자녀가 둘이어서 삭제되는 색은 50의 successor인 80의 black

 

delete(30)

 

⚠️ extra black을 부여했더니 doubly black 노드가 생겼다면, extra black을 어떻게 없앨 것인가?

 

extra black 부여 후
doubly black 해결하기

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

CASE 1 : doubly black의 오른쪽 형제가 red 일때

B를 기준으로 왼쪽으로 회전하면 doubly black A의 형제는 C가 된다. 즉 black이 된다. 회전 후에도 #5 속성을 만족하려면 왼쪽으로 회전하기 전에 B와 D의 색을 바꿔준다!!

 

 

1. 부모와 형제의 색을 바꾼다.

2. 부모를 기준으로 왼쪽으로 회전

3. doubly black을 기준으로 Case 2,3,4 중 하나로 해결

(오른쪽 왼쪽 바꿔도 성립)

CASE 2 : doubly black의 형제가 black & 그 형제의 두 자녀 모두 black일 때

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

black을 전달받은 B는 red and black 또는 doubly black이 된다.

CASE 3: doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black 일 때

1. doubly black의 형제의 오른쪽 자녀가 red가 되기 만들어서 이후엔 CASE 4를 적용해서 해결한다.

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

CASE 4 : doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red 일 때

doubly black의  오른쪽 형제 가  black  &  그 형제의 오른쪽 자녀가  red  일 때

 

 

Red Black Tree 시간 복잡도

	avg	worst
insert	O(logN)	O(logN)
delete	O(logN)	O(logN)
search	O(logN)	O(logN)

 

Red-Black 트리와 AVL 트리의 성능 차이