[자료구조] 레드 블랙 트리(Red-Black Tree) 정리 (1) - 삽입
레드-블랙 트리(Red-Black Tree) 공부하기
전에 게임 프로그래밍 면접에서 레드-블랙 트리에 대한 질문을 받았는데 답변을 못해서 매우 당황했던 기억이...
학교 다니면서 AVL트리에 대해서만 공부했기 때문에 레드-블랙 트리 질문이 나올줄은 상상도 못했음..
그렇게 레드-블랙 트리에 대해 정리를 시작하게 됐습니다
아래 포스트를 참고하여 작성했습니다.
https://code-lab1.tistory.com/62
레드-블랙 트리를 공부해야하는 이유
C#에서 SortedDictionary<K, V>와 SortedSet 가 내부적으로 레드-블랙 트리로 구현되어 있다.
우선 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 이진 트리가 스스로 균형을 맞춘다는 말인데 이게 왜 필요한지 알아보자
일반 이진 탐색 트리(BST)의 단점은 데이터가 정렬된 순서로 들어오면 다음과 같이 한쪽으로 쭉 늘어진 이진 편향 트리가 된다.
이렇게 되면 탐색 시간이 O(n)으로 떨어져 연결리스트와 다를 바가 없어진다. 이 문제를 해결하기 위해 자기 균형 이진 탐색 트리가 등장했다. 레드-블랙 트리는 그 중 가장 널리 사용되는 구조로, 어떤 순서로 데이터를 삽입하더라도 트리의 높이를 O(log n)으로 유지한다.
레드-블랙 트리의 5가지 규칙
레드-블랙 트리는 이진 탐색 트리에 다음과 같은 5가지 규칙을 추가한다
이 규칙들이 모두 만족될 때 트리는 "유효한 레드-블랙 트리"가 된다
- 모든 노드는 빨간색 혹은 검은색이다.
- 루트 노드는 검은색이다
- 모든 리프 노드는 검정색이다 (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타냄)
- 빨간색 노드의 자식은 검은색이다 = No Double Red(빨간색 노드가 연속으로 나올 수 없다)
- 모든 리프 노드에서 Black Depth는 같다 = 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다
레드-블랙 트리 삽입 과정
레드 - 블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다
위의 예시에서는 3을 넣었을 때 Double Red가 발생한다
레드-블랙 트리는 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다
N : 새로 삽입할 노드
P : 부모 노드
U 삼촌 노드(부모 노드의 형제)
G : 조부모 노드
Double Red가 발생했을 때
- 삼촌 노드가 검은색 : Restructuring
- 삼촌 노드가 빨간색 : Recoloring
Restructuring
Resturcturing의 과정
- 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다
- 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다
- 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다
1단계 - 3(N)을 넣었을 때 Double Red가 발생한다
이때 7(U)가 검은색이라 Restructuring을 수행한다
2단계 - 먼저 3(N), 2(P), 5(G)를 오름차순으로 정렬한다 -> 3이 중간값이 된다
중간값인 3을 부모 노드로 바꾸고 나머지 2(P)와 5(G)를 자식 노드로 바꾼다 (이때 회전으로 진행)
이때 5(G)의 오른쪽 자식 노드였던 7(U)는 그대로 5(G)의 오른쪽 자식 노드가 된다
3단계 - 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식의 2, 5의 색을 빨간색으로 바꿔준다
여기서 2는 규칙 3을 만족하지 않는것처럼 보이지만 빨간색이 리프노드처럼 보일때는 NIL을 2개 가지고 있다고 생각하면 된다
Recoloring
Recoloring의 과정
- 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다
- 조상(G)이 루트 노드라면 검은색으로 바꾼다
- 조상(G)을 빨간색으로 바꿨을 때 또 다시 Double Red가 발생하면 또 다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다
1단계 - Double Red가 발생했을 때 삼촌 노드가 빨간색이기 때문에 Recoloring을 수행한다
2단계 - 먼저 부모(P)와 삼촌(U)을 검은색으로 바꾸고, 조상(G)을 빨간색으로 바꾼다
이때 루트 노드는 검은색이라는 조건을 지켜야하므로, 루트 노드를 검은색으로 바꾼다
(이때 검은색 노드는 연속 2번 나와도 상관 없다. - 빨간색만 아니면 됨)
뭐가 문제일까?
Recoloring은 간단해 보이지만 문제는 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 다시 Double Red 문제가 발생하는 경우다
위 상황에서 왼쪽 트리에서 Recoloring을진행하면 오른쪽 트리가 된다 -> 또 다시 Double Red가 발생한다
이때 또 14(U)가 빨간색이므로 Recoloring을 진행하면 Double Red 문제를 해결한다
(만약 14(U)가 검은색이었다면 Restructuring진행
삭제까지 정리하고 싶었는데 유튜브로 좀 더 공부해보고 나중에 2편으로 정리하는게 나을 것 같다..