안녕하세요. 이번 주차에는 Red-Black 트리를 C언어로 구현하는 과제를 진행하고 있어요.
그래서 레드 블랙 트리의 기본 개념과 특징을 살펴보려고 해요.
Red-Black-Tree
레드 블랙 트리는 이진탐색트리의 한 종류예요.
이진탐색트리는 루트노드를 기준으로 왼쪽에는 자신보다 작은 값이, 오른쪽에는 자신보다 큰 값이 오는 트리예요.
이진탐색트리에는 단점이 있는데 그건 최악의 경우 시간복잡도가 O(n)이라는 겁니다. 위 트리기준으로 볼까요?
트리의 왼쪽 노드를 잠시 뺐어요.
만약 우리가 여기서 50이라는 값을 검색하려면 모든 노드를 순회해서 마지막까지 도달해야 50이라는 값을 찾을 수 있어요.
그래서 탐색할때 최악의 경우 시간복잡도가 O(n) 이예요.
Red-Black-Tree는 이런 단점을 해결하기 위해서 나왔어요.
스스로 균형 (balancing) 을 잡는 트리로 이진탐색트리의 최악의 경우 단점을 개선해서 복잡도를 O(logn) 으로 만드는 거예요.
Red-Black-Tree의 특징
1. 모든 노드는 Red 혹은 black 이다.
2. 루트 노드는 black 이다.
3. leaf 노드는 nil 노드이다.
nil 이란?
이건 레드 블랙트리의 고유한 특징 중 하나예요.
값을 가지고 있는 노드가 LeafNode 가아니라 nil 노드라는 특수한 노드로 자녀를 표기해요.
값이 있는 노드랑 동등하게 취급하기 때문에, RB트리에서 모든 leaf 노드는 nil 노드입니다.
근데 또 다른 특징이 하나 더 있는데 모든 nil 노드는 black이라는 겁니다.
4. red 의 자녀들은 black이다.
이건 무슨 말이냐면 red가 연속적으로 존재할 수 없다는 걸 뜻해요.
5. 임의의 노드에서 자손 nil 노드까지 가는 경로들의 black 수는 같다. ( 자기자신은 카운트에서 제외 )
어떤 임의의노드에서 nil 노드까지 가는 경우의 수끼리는 black 노드가 같은 수가 있어야 해요.
이건 black height 라는 개념에서 사용돼요.
어떤 임의의 노드에서 nil 노드 까지 갈때 , 만나는 black 의 수를 black height 라고 합니다.
그리고 이 개념을 만족한다면
부모와 자녀의 색을 바꿔줘도 만족할 수 있어요!
나중에 삽입하거나 삭제할 때 이 개념을 사용합니다.
RB트리는 어떻게 균형을 잡을까?
RB 트리는 삽입/삭제 할 때 보통 4번이나 5번 규칙을 위반해요.
그래서 그 위반된 규칙을 해결하려는 과정에서 자연스럽게 균형을 유지하게 됩니다.
RB 트리의 삽입 방식
- 삽입 전 RB 트리 속성을 만족한 상태여야 해요.
- 삽입 방식은 이진탐색트리와 동일해요!
- 삽입 후에 RB 트리의 위반 여부를 확인해요.
- RB 트리 속성을 위반했다면 재조정!
- RB 트리 속성을 다시 만족 ( 균형유지 )
insert(50) 노드를 삽입할 때, Red로 삽입하고 nil 노드는 Black 으로 해줍니다.
자연스럽게 3번 left 노드가 nil 노드라는 것을 만족하게 돼요.
근데 그거아세요? 2번 루트노드가 블랙이라는 것은 만족 못했어요!
그래서 루트노드를 블랙으로 바꿔줘야해요 ㅎㅎ
이러면 RB트리의 모든 속성을 만족하게 됩니다!
insert(20) 이진탐색트리의 특징으로 20을 삽입하게되면
자연스럽게 레드블랙트리의 특성을 모두 만족하게 되네요! 변경할 필요가 없습니다.
왜 삽입할 때 red를 삽입할까요?
그건 5번 속성을 만족하기 위해서예요.
5번은 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수가 같다는 거예요.
그래서 삽입은 black 을 하지 않고 red 를하고 실제로 규칙을 맞추기 위해서만 black 으로 변경이 일어나요.
insert(10)
2번 속성인 Red 의 "자녀들은 모두 black 이어야 한다" 를 위반했어요.
그래서 이걸 Red가 한쪽에 몰려있으니 반대쪽으로 보내면 어떨까? 로 해결할건데
그러면서 이진탐색트리의 특징도 만족해야 해요.
바로 이렇게요!
이렇게 구조를 바꾸면서도 이진탐색트리의 특징을 유지시키려면 "회전"이라는 방법을 사용해야 해요.
그 회전을 어떻게 사용할지가 바로 관건입니다.
- 20과 50의 색을 바꿔준다.
- 50을 기준으로 오른쪽으로 회전한다.
그럼 위 그림대로 트리가 만들어지게 돼요.
이렇게 기준을 맞추는 건 정말 여러가지가 있어서 여러 케이스를 고려해서 코드를 짜야해요.
마무리
RB 트리의 아주 기본적인 개념을 살펴봤고요.
이제 이걸로 삽입/삭제 해보러갈게요.....
