Red-Black Tree

본 프로젝트의 개요와 프로젝트를 진행하기 위한 개념 확립

1. 특징

• 이진 탐색 트리(BST)의 한 종류
• 스스로 균형(balancing) 잡는 트리 ( worst case : 𝑂(log𝑛) )
• BST의 worst case( 𝑂(n) )의 단점을 개선
• 모든 노드는 red 혹은 black

 

2. 속성

1. 모든 노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil(leaf) 노드는 black
4. red의 자녀들은 black (= red가 연속적으로 존재할 수 없음)
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 노드 수는 같음 (자기 자신 제외)
   • RB 트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족

nil 노드란?

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

노드 x의 black height

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

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

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

 

3. 삽입

3-1. 삽입 과정

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

삽입하는 노드는 항상 red 이다. (삽입 후에도 #5 속성을 만족하기 위함)

3-2. 삽입 후 #2 속성 위반

새로운 노드를 삽입할 때 노드는 항상 red여야하기 때문에 최초 노드를 삽입한 경우 #2 속성을 위반하게 된다면 루트 노드를 black으로 바꿔서 해결하면 된다.

3-3. 삽입 후 #4 속성 위반

#4 속성 위반을 해결하기 위해 red 하나를 넘겨야 하는데 BST 특징 또한 유지하면서 넘기려면 회전을 사용해야 한다.

case 3 :

삽입된 red 노드가 부모의 왼쪽 자녀이고, 부모도 red이면서 할아버지의 왼쪽 자녀이고, 삼촌(할아버지의 오른쪽 자녀)은 black이라면, 부모와 할아버지 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전한다.

왼쪽을 오른쪽, 오른쪽을 왼쪽으로 바꿔도 성립

case 2 :

case 3와 살짝 다른 점은 삽입된 노드를 기준으로 할아버지까지의 경로가 꺾였다는 점이다. 따라서 꺾인 부분을 펴줘서 case 3와 같은 형태로 만들고 case 3를 적용시키면 된다.

삽입된 red 노드가 부모의 오른쪽 자녀이고, 부모도 red이면서 할아버지의 왼쪽 자녀이고, 삼촌(할아버지의 오른쪽 자녀)은 black이라면, 부모를 기준으로 왼쪽으로 회전한 뒤 case 3를 적용시킨다.

왼쪽을 오른쪽, 오른쪽을 왼쪽으로 바꿔도 성립

case 1 :

삽입된 red 노드의 부모도 red이면서, 삼촌도 red라면, 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서 다시 속성을 위반하는지 않았는지 확인을 한다.

 

4. 삭제

4-1. 삭제 과정

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

4-2. 속성 위반 여부 확인

삭제 시 RB 트리의 속성 위반 여부는 삭제되는 색을 통해 확인할 수 있다.

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

• 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색은 삭제되는 노드의 successor의 색이다. (여기서 자녀는 유효한 값을 가지는 자녀를 의미)

  • successor란 노드의 오른쪽 서브트리에서 가장 작은 값의 노드를 의미

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

• 삭제되는 색이 black이라면 #2, #4, #5 속성을 위반할 수 있다.

4-3. 삭제 후 #2 속성 위반

루트 노드를 삭제할 경우, 해당 노드의 자녀가 루트 노드가 되면서 #2 속성을 위반하게 된다면 루트 노드를 black으로 바꿔서 해결하면 된다.

4-4. 삭제 후 #5 속성 위반

삭제되는 색이 black일 때 특수한 상황을 제외하면 주로 #5 속성을 위반하게 된다. #5 속성을 다시 만족시키기 위해서는 삭제된 색의 위치를 대체한 노드에 extra black을 부여해야 한다. 경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다. 만약 nil 노드에 extra black이 부여된 노드는 doubly black이라고 부르고 red에 extra black이 부여된 노드는 red-and-black이라고 부른다.

정리하자면 삭제되는 색이 black이고 #5 속성을 위반할 때 삭제된 색의 위치를 대체한 노드에 extra black을 부여하게 되고 extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다.

red-and-black 해결하기

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

doubly black 해결하기

doubly black을 해결하는 방법은 doubly black의 형제의 색과 그 형제의 자녀들의 색에 따라 다음의 4가지 case로 분류할 수 있다.

case 4:

doubly black의 오른쪽 형제가 black이고, 그 형제의 오른쪽 자녀가 red일 때, 그 red를 doubly black 위로 옮기고, 옮긴 red로 extra black을 전달해서 red-and-black으로 만든다. red-and-black은 black으로 바꿔주면 해결된다.

다시 말하자면, doubly black의 오른쪽 형제가 black이고, 그 형제의 오른쪽 자녀가 red일 때, 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀와 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 되는 것이다.

왼쪽을 오른쪽, 오른쪽을 왼쪽으로 바꿔도 성립

case 3:

doubly black의 오른쪽 형제가 black이고, 그 형제의 왼쪽 자녀가 red, 오른쪽 자녀가 black일 때, doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 case 4의 형태를 만들어준다. 이후엔 case 4를 적용하여 해결하면 된다.

다시 말하자면, doubly black의 오른쪽 형제가 black이고, 그 형제의 왼쪽 자녀가 red, 오른쪽 자녀가 black일 때, doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 case 4를 적용한다.

왼쪽을 오른쪽, 오른쪽을 왼쪽으로 바꿔도 성립

case 2:

doubly black의 형제가 black이고, 그 형제의 두 자녀 모두 black일 때, doubly black과 그 형제의 black을 모아서 부모에게 전달해 부모가 extra black을 해결하도록 위임한다. 부모가 red-and-black이 됐다면 black으로 바꿔주면 바로 해결이 될 것이고, 부모가 doubly black이 됐다면 부모가 루트 노드라면 black으로 바꿔서 해결, 아니라면 case 1, 2, 3, 4 중에 하나로 해결한다.

case 1:

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

다시 말하자면 doubly black의 오른쪽 형제가 red일 때, 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 case 2, 3, 4 중 맞는 case를 적용한다.

왼쪽을 오른쪽, 오른쪽을 왼쪽으로 바꿔도 성립

 

5. 시간 복잡도

BST	best	avg	worst
insert	𝑂(1)	𝑂(log𝑛)	𝑂(n)
delete	𝑂(1)	𝑂(log𝑛)	𝑂(n)
search	𝑂(1)	𝑂(log𝑛)	𝑂(n)

 

AVL Tree	best	avg	worst
insert	𝑂(1)	𝑂(log𝑛)	𝑂(log𝑛)
delete	𝑂(1)	𝑂(log𝑛)	𝑂(log𝑛)
search	𝑂(1)	𝑂(log𝑛)	𝑂(log𝑛)

 

RB Tree	avg	worst
insert	𝑂(log𝑛)	𝑂(log𝑛)
delete	𝑂(log𝑛)	𝑂(log𝑛)
search	𝑂(log𝑛)	𝑂(log𝑛)

 

6. RB Tree vs AVL Tree

	RB Tree	AVL Tree
BST	Yes	Yes
삽입/삭제/검색 시간복잡도	worst에서도 𝑂(log𝑛)	worst에서도 𝑂(log𝑛)
삽입/삭제 성능	AVL에 비해 빠름	RB에 비해 느림
검색 성능	AVL에 비해 느림	RB에 비해 빠름
균형 잡는 방식	RB 트리 속성을 만족시킴	balance factor ∈ {-1, 0, 1}
응용 사례	linux kernel 내부, Java TreeMap, c++ std::map	dictionary, 삽입/삭제 거의 없고 검색이 대부분인 경우

 

References
https://www.youtube.com/watch?v=2MdsebfJOyM&t=16s
https://www.youtube.com/watch?v=6drLl777k-E