[2022.05.03 ]TIL - RB트리 개념

RB 트리란?

자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees).

(개념 중간에 삼촌, 부모, 조부모 등 다양한 가족들이 나오니 집중하자)

 

RB 트리의 특성

1. 노드는 'red' 혹은 'black' 중 하나이다.
2. 루트 노드는 'black'이다.
3. 모든 리프 노드(NIL)들은 'black'이다.
4. 노드가 'red'일 때, 자식 노드 양쪽은 언제나 모두 'black'이다. (즉 레드 노드는 연달나 나타날 수 없다)
5. 각 노드에 대해 해당 노드에서 리프 노드를 제외한 자식 노드까지의 모든 경로들은 같은 수의 'black' 노드 개수를 가진다.

용어

사촌노드: 같은 높이에 있는 옆 노드

삼촌노드: 사촌의 부모노드

조부모노드: 부모노드의 부모노드

일반적으로( N: 삽입하는 원소, P: 부모노드, U: 삼촌노드 G: 조부모 노드)

삽입(insertion)

단순 이진 탐색트리에서 하는 것과 같이 노드를 삽입하고, 붉은 색으로 정하는 것으로 시작한다.

case1

N  이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. 이 경우, 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검은색이다)을 만족하기 위해서, N 을 검은색으로 표시한다.

case2

새로운 노드의 부모 노드 P가 검은색이라면, 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식 노드는 검은색이다)은 유효하다

case3

만약 부모 노드 P와 삼촌 노드 U가 모두 붉은색 노드라면, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)을 유지하기 위해서, P와 U를 모두 검은색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다

case4

부모 노드 P가 붉은색인데, 삼촌 노드 U는 검은색이다; 또한 새로운 노드 N은 P의 오른쪽 자식 노드이며, P 는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 한다

case5

부모 노드 P는 붉은색이지만 삼촌 노드 U는 검은색이고, 새로운 노드 N이 P의 왼쪽 자식 노드이고, P가 할아버지 노드 G의 왼쪽 자식 노드인 상황에서는 G에 대해 오른쪽 회전을 한다.

삭제(Deletion)

case1

N 이 새로운 루트가 될때. 이 경우에는 더 할게 없다. 우리는 모든 경로에서 하나의 검은 노드를 삭제했고, 새로운 루트 노드는 검은색이므로 모든 특성이 보존된다.

case2

S 가 빨강일 경우. P의 자식인 S가 빨강색이므로 P가 검은색임이 명확하다.이 경우 P와 S 의 색을 바꾸고, P에서 왼쪽으로 회전 하면, S가 N의 할아버지 노드가 된다. 모든 경로에서의 검은 노드의 수가 같지 않으므로 아직 끝나지 않았다. 이제 N이 검은색 형제노드와 붉은색 부모 노드 갖고 있으므로, case 4, 5, 6을 진행할 수 있다.

case3

P, S, 그리고 S의 자식들이 검은색인 경우. 이 경우, 우리는 간단히 S를 빨강으로 칠하면 된다. 그 결과, S를 지나는 모든 경로들(N 지나지 않는 경로)은 하나의 검은노드를 적게 갖고 있게 된다. 하지만, N의 원래 부모노드를 삭제하는 과정에서 N을 지나는 모든 경로들은 하나의 검은 노드를 적게 갖게 되므로, 양쪽은 같은 수의 검은 노드를 갖게 된다. 그러나, P를 지나는 모든 경로들은 P를 지나지 않는 모든 경로에 대해 검은 노드를 한 개 적게 지니게 되므로, 특성 5(특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다.)를 위반하게 된다. 이를 바로잡기 위해서, 우리는 P에다 case 1부터 시작하는 rebalancing 과정을 수행해야 한다.

case4

S와 S의 자식들은 검은색이지만, P는 빨강인 경우. 이 경우, 우리는 단순히 S와 P의 색을 바꾸면 된다. 이는 S 를 지나는 경로의 검은 노드 개수에 영향을 주지 않지만, N을 지나는 경로에 대해서는 검은 노드의 개수를 1개 증가시킨다. 이는 원래 삭제된 검은 노드의 개수를 보충해준다.

case5

S가 검정, S의 왼쪽 자식이 빨강, S의 오른쪽 자식이 검정이며, N이 부모의 왼쪽 자식인 경우. 이 경우 우리는 S 를 오른쪽으로 회전시켜서 S의 왼쪽 자식이 S의 부모노드이자 N의 새로운 형제 노드가 되도록 만든다. 그리고 나서 우리는 S의 색을 부모 노드의 색깔과 바꾼다. 모든 경로는 여전히 같은 수의 검은 노드수를 가지나, 이제 N 이 오른쪽에 붉은 노드를 자식으로 둔 검은색 형제노드를 갖게 되었으므로, 6번째 case로 진행하면 된다. N 이나 N의 부모노드는 이 변형에 아무런 영향을 받지 않는다. (다시 말하지만, N의 새로운 형제 노드를 6번째 case에서 S라고 부르도록 할 것이다.)

case6

 

RB 트리 시뮬레이션

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

참고교재

ntroduction to Algorithms(third edition)

참고 강의

https://www.youtube.com/watch?v=gF20ZSplxZE&ab_channel=권오흠

https://www.youtube.com/watch?v=45jz_f5si4A&ab_channel=권오흠

https://www.youtube.com/watch?v=98g_cnvbyqA&t=879s&ab_channel=권오흠

참고 사이트

https://ko.wikipedia.org/wiki/레드-블랙_트리