Red-Black 트리

• 이진 탐색 트리(BST)의 한 종류
• 스스로 균형을 잡는 트리(→Balancing)
• BST의 worst case의 단점을 개선

Red-Black 트리 속성

1. 모든 노드는 red 혹은 black

2. 루트 노드는 black

3. 모든 nil(leaf) 노드는 black

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

4. red의 자녀들은 black 혹은 red가 연속적으로 존재할 수 없다.

5. 임의의(아무) 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

   • 노드 x의 black height

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

       

     • 5번째 속성을 만족해야 성립하는 개념

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

     rb트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다. → 삽입과 삭제를 할때 이 속성이 사용됨

RB트리 삭제 방식

삭제 순서

0. 삭제 전 RB트리 속성을 만족한 상태

1. 삭제 방식은 일반적인 BST와 동일

2. 삭제 후 RB 트리 속성 위반 여부 확인

3. RB트리 속성을 위반했다면 재조정

4. RB트리 속성을 다시 만족

결국은 RB트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요하다.

삭제하려는 노드의 자녀가 없거나 하나라면

삭제되는 색 = 삭제되는 노드의 색

삭제하려는 노드의 자녀가 둘이라면

삭제되는 노드의 successor의 색

속성 위반 여부 확인

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

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

삭제되는 색이 black일 때 특수한 상황을 제외하면 #5 속성을 항상 위반하게 된다.
(특수한 상황은 루트노드가 black인데 그것이 제거될때이다.)

extra black

#5속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다.
경로에서 black을 카운트할 때 extra black은 하나의 black으로 카운트된다.
extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다.

red-and-black 해결하기

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

위의 그래프에서 30을 삭제한다고 가정해보자
30은 자녀가 하나라서 삭제되는 색은 30의 black이다. → #5 위반
20과 25가 바로 연결된다. → #4 위반
삭제되는 색은 30의 black이었고, 30을 대체하는 25의 red에 extra black을 부여한다.
25는 red-and-black이 됐으니 25를 black으로 바꿔주면 종료된다.
그럼 #4, #5를 위반한 것을 동시에 해결할수있다.

doubly black 해결하기

doubly black의 extra black을 없애는 방법은 총 4가지 case로 분류된다.
4가지 case로 분류할때의 기준은 doubly black의 형제의 색과 그 형제의 자녀들의 색이다.

case 4

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

오른쪽 형제는 부모의 색으로,
오른쪽 형제의 오른쪽 자녀는 black으로,
부모는 black으로 바꾼 후에
부모를 기준으로 왼쪽으로 회전하면 해결된다.

case 3

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

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

case 2

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

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

case 1

doubly black의 형제가 red일때

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

🙋‍♂️ 오늘의 TMI

점점 추워진다. 🥶
전기장판을 살까..