(작성중)
레드 블랙 트리란 Balanced Binary-Search Tree로, 모든 노드들을 빨간 색 혹은 검은 색으로 칠해 놓았기 때문에 레드-블랙 트리라고 부른다.
어이 없지만, 이런 이유로 Red-Black 트리이다. 트리를 처음 고안한 논문의 저자들이 사용할 수 있었던 프린터가 만들어낸 가장 "멋진"색이기 때문이라고 한다.
레드 블랙 트리는, 이런 빨강-검정으로 트리의 노드들을 색칠하고, 색에 대한 규칙을 세워 규칙을 어기는 경우 다시 균형을 맞춰 높이를 낮춘다.
균형을 맞추는 트리들이 균형을 맞추는 이유는 트리 Depth를 줄여 빠르게 탐색하기 위해서이다! 편향된 트리를 보면 알겠지만, 탐색 시간 복잡도가 O(N)이 된다.
가장 아래에 있는 데이터를 찾는 경우 데이터 전체 갯수만큼 탐색하게 된다.
균형을 맞췄을 때, 최악 탐색 시간 복잡도가 줄어들게 되기 떄문에, 균형을 맞추는 것이다.
어떤 데이터를 탐색해도 균일하게 빠르다. (시간 복잡도 증명은 3번 글에 기재)
레드 블랙 트리는 균형을 맞추기 위해 색을 칠한다고 했다. 색칠된 노드들의 규칙을 살펴보자.
- 모든 노드는 빨강 혹은 검정으로 색칠 되어 있다.
- Root는 Black이다.
- 모든 Leaf Node는 Black이다.
- 빨강 노드는 연속될 수 없다.
- Root 노드에서 모든 Leaf 노드까지 가는 경로의 Black Node 갯수는 같다!
- 새로 삽입되는 노드는 빨강이다.
보통 5번까지만 규칙으로 언급되고, 6번은 이해를 용이하기 위해 기재했다.
결국 새로운 노드는 무조건 빨강색으로 삽입되기 때문에, 빨강이 연속되는 순간이 나오게 되는 것이고, 빨강 노드가 연속되는 경우에 균형을 맞추는 작업이 이루어진다.
간단하게 위 그림을 살펴보면 정말로 5번 규칙 : Root 노드에서 모든 Leaf 노드까지 가는 경로의 Black Node 갯수는 같다를 확인할 수 있다.
왼쪽 끝 부터 살펴보자. K번 노드에 도착하기까지 Balck Node 갯수를 세어보자. 간단하게 노드가 가지고 있는 값으로 K번 노드 라고 칭하겠다.
1번 노드: 13, 1 노드 -> 2개6번 노드: 13, 1 노드 -> 2개11번 노드: 13, 11 노드 -> 2개15번 노드: 13, 15 노드 -> 2개22번 노드: 13, 25 노드 -> 2개27번 노드: 13, 25 노드 -> 2개
이렇게 직접 세어보면 5번 규칙을 만족하는 것을 확인할 수 있다.
검은 노드를 넣는 것보다 규칙을 맞추기가 더 쉽기 때문이다.
예를 들어 검은 노드를 넣는다면, 5번 규칙을 어기기 쉬울 것이다. 이때, 5번 규칙을 지키기 위해서는 복잡한 재정렬이 필요한데, 이것 보다는 빨간 노드를 넣고, 빨간 노드가 연속했을 때 고치는 과정이 쉽다고 한다. (안 쉽던데..)
Red-Black Tree가 균형을 맞추는 방식은 2가지이다.
Recoloring: 주변 노드들의 색을 변경해 균형을 맞춘다.Rotation: 노드들을 회전 시켜 균형을 맞춘다. AVL Tree처럼 회전시킨다. Restructring이라고 표현하는 한글 아티클도 많은데, 이는 Recolor를 포함하는 표현인듯 하다.
두 가지 방법을 좀 더 자세히 살펴보자. 그다음 삽입과 삭제시에 무슨 일이 일어나는지 두 가지 방법을 통해 설명하겠다. 그리고 Java 라이브러리의 구현을 살펴보자.
- NIL 노드 : 아무 데이터가 없는 Black 노드이다. Red-Black Tree에서 규칙을 지키기 위해 데이터가 없는 검은 리프 노드를 NIL 노드로 사용한다.
- NIL로 채워져 있는 Leaf : Red-Balck Tree의 Leaf Node들은 NIL로 채워져 있다 (위 그림 참고..)
- Grand Parent 노드 : 부모의 부모 노드이다.
- Parent Sibling 노드 : 말 그대로 부모 노드의 형제 노드이다. Grand Parent Node의 자식 노드 중 부모 노드가 아닌 노드를 이렇게 부르겠다.
- 균형은 여러번 맞춰질 수 있다 : 균형을 맞추는 작업을 1회 실시하더라도, 빨간 노드가 연속하는 상황이 벌어질 수 있다.
그런 경우 균형을 맞추는 작업은 여러번 반복된다.
Recoloring은 말 그대로 노드들의 색을 다시 칠하는 것이다.
위 그림에서 파란색 동그라미로 표시한 것이 새 노드이다. 위 그림처럼 노드들의 색을 바꾸는 것인데, 삽입과 삭제시 색 변경이 다르게 진행될 수 있다.
Recoloring은 삽입시 부모와, 부모의 형제 노드가 둘 다 빨간색인 경우 발생한다.
- 부모 노드와 Parent Sibling 노드를 검은 색으로 변경한다.
- 이후 Grand Parent Node를 빨간 색으로 변경한다.
- 만약 Grand Parent Node가 루트였다면 검은 색으로 변경한다.
- 만약 Grand Parent Node가 빨간색이 되면서, "빨간색 노드는 연속으로 2개가 올 수 없다"규칙이 깨지는 경우, Recoloring 혹은 Rotation을 진행한다.
노드들을 회전시킨다.
AVL Tree의 Rotation을 안다면 그것과 동일하다.
설명을 너무 복잡하게 하는 곳이 많은데, 그림과 코드를 먼저 보는게 훨씬 쉽다. 코드는 짧지만 상상하면 머리가 복잡해진다. 종이에 직접 그려보면 괜찮다.
마치 핸들을 돌리듯이 x와 y를 잡고 왼쪽, 오른쪽으로 돌리는 모습을 상상하면 된다!
x, y, 감마를 잡고 왼쪽으로 회전한다고 생각해보면 된다. 위와 같은 상황에서 y에 자식이 있다면, 그 값은 x보다 크고, y보다 작은 것이므로, x의 오른쪽에 가게 된다. 간단한 c++ 코드로는 아래와 같이 구현할 수 있다.
x->rightChild = y->leftChild;
y->leftChild = x;
Left Rotate와 반대이다.
코드로는 아래와 같이 구현할 수 있다 (c++)
y->leftChild = x->rightChild;
x->rightChild = y;AVL Tree처럼 LR, RL 회전도 있다.
LR 회전은 위와 같이 수행되는데, 더 아래에 있는 xy먼저 잡고 Left Rotate를 한 다음, yz를 잡고 Right Rotate한다. 보통 새로 삽입된 노드가 부모의 오른쪽 자식이고, 부모는 Grand Parent Node의 왼쪽 자식일 대 발생한다.
RL 회전은 반대 상황에서 발생한다.
이렇게 균형을 맞추기 위한 연산들을 알아봤다. 이제, 균형을 맞추는 두 연산 Recolor와 Rotate를 통해 Red-Black Tree의 삽입 연산과 삭제 연산을 알아보자. 그리고 코드를 살펴본 다음, Java 라이브러리에서 어떻게 사용하는지 살펴보자 (HashMap과 TreeSet, TreeMap에서 사용)
이제 Red-Black Tree의 삽입과 삭제를 알아보자.
간단하게 동작을 그림과 함께 살펴본 다음, Java Code를 읽으며 이해해보자.
나도 각종 블로그에서 설명만 보며 공부했을 때 보다 코드와 함께 공부했을 때 훨씬 이해가 잘 됐었다.
삽입 삭제를 설명하기에 앞서 검색 연산을 먼저 설명하고 싶다.
왜냐하면 삽입과 삭제 과정에선 항상 검색 연산이 선행되기 때문이다. 이 노드가 들어갈만한 위치를 찾아야, 지우고 싶은 값이 트리상에서 어디에 있는지를 알아야 삽입하고 삭제할 수 있다.
검색 연산은 간단하다. 레드 블랙트리는 정렬된 이진트리인 만큼, 루트에서 부터 시작해서 대소비교를 통해 현재 노드보다 넣어야 할 value가 작으면 왼쪽, 크면 오른쪽으로 이동하면 된다. (오름차순 정렬로 가정했을 때)
정렬된 트리의 검색을 아는 사람이라면 지루하겠지만, 한번 살펴보자..
예를 들어 위 그림에서 파란색 동그라미로 표시된 22 노드를 찾는다고 생각해보자.
- 탐색은 루트에서 시작한다
- 22는 13보다 크므로, 오른쪽 자식으로 이동한다.
- 22는 17보다 크므로, 오른쪽 자식으로 이동한다.
- 22는 25보다 작으므로, 왼쪽 자식으로 이동한다.
- 완성! -> 아래 표시한 루트대로 이동할 것이다.
찾기 연산은 간단하고, 꼭 레드 블랙 트리만의 특징이 아니므로, 코드로 나타내지 않겠다.
삽입은 앞서 언급한 Red-Black Tree의 규칙과 정렬 트리의 규칙대로 삽입된다.
- 노드가 들어갈 위치를 찾는다.
- 빨간 노드를 넣는다.
- 만약
빨간 노드는 연속해서 놓일 수 없다규칙을 어기는 경우, 규칙을 만족할 때까지 Recoloring이나 Rotation을 적용한다.
단순히 삽입하는 과정은 어렵지 않다. 복잡한 것은 균형을 맞추는 과정이다. 보통 insert이후 현재 노드와 부모 노드가 빨간색인 경우 빨간 노드 연속을 제거한다. 제거 과정에서 색도 바꾸고 돌리고 하다 보면 또 빨간 노드 연속이 발생할 수 있는데, 재귀적으로 처리한다.
아래 항목을 "현재 노드"와 그 "부모 노드"가 빨간 노드인 동안 반복한다.
- 만약
부모 노드가조부모 노드(부모의 부모)의 왼쪽 자식인 경우Case 1: 만약부모의 형제 노드가 빨간색인 경우 (부모 형제가 모두 빨간 색인 경우)부모 노드와부모의 형제노드를 둘 다 검은색으로 칠한다.- 그리고
조부모 노드를 빨간색으로 칠한다. 이들은 앞서 소개한 Recoloring 방식에 해당한다. - 이후
현재 노드를조부모 노드로 설정한다. (재귀 호출을 위한 과정)
Case 2:Case 1이 아닌 경우부모 노드를 검은 색으로 칠한다.- 그리고 조부모 노드를 빨간 색으로 칠한다.
- Right Rotate를 수행한다.
Case 2 - 1:Case 2를 적용하기 전의 전처리이다, 만약현재 노드가부모 노드의 오른쪽 자식인 경우현재 노드를부모 노드로 설정한다.- Left Rotate를 수행한다.
- 만약
부모 노드가조부모 노드의 오른쪽 자식인 경우 - 위 과정을 모두 반대로 수행하면 된다.
머리가 너무 아프다. 특히 인터넷에 올라온 코드들이 죄다 복잡 복잡하다.
가장 깔끔하고 읽기 좋은 코드는 java util에 있었다.
역시 형이야! 구하러 와줬구나? Red-Black Tree.. 그 유명한 Java HashMap 거기지?
-> 절대 아니다 일단 변수명이 너무하다. 아래와 같다.
의외로 잘 쓰이지 않는 TreeMap에도 Red-Black Tree가 있는데, (PS할떄 가끔 TreeSet을 쓴다) 이게 아주 읽기 좋게 만들어져 있다. 그래서 Java TreeMap을 기준으로 설명하겠다.
put Method는 Map에 데이터를 삽입하는 메서드로, 우리가 찾는 insert 연산을 구현했다.
가장 윗 부분을 보자. 기본적으로, Tree가 비어있는 경우 addEntryToMap을 호출하는데, 그 메서드는 바로 위에 있다. 단순히 루트에 새 노드를 할당해주고, 사이즈와 연산 횟수를 센다.
put의 3번째 파라미터 replaceOld는 대체 여부를 따지는데, Map의 put과 putIfAbsent를 구분하는데에 쓰인다.
나머지 부분은 역시 들어가게 될 위치를 찾는 과정이다. TreeMap은 생성자를 통해 Comparator를 넣어 생성할 수 있는데, 그런 Comparator가 있는 경우엔 그것을 사용하고, 없는 경우엔 key를 Comparable로 변환해 찾는다.
앞서 설명한 탐색과정 처럼 대소비교를 통해 왼쪽, 오른쪽으로 이동한다. 이후 최하단을 보면 addEntry를 호출하는데, 여기가 실제 삽입이 발생하는 곳이다. 마지막 파라미터를 통해 왼쪽과 오른쪽 중 어느 곳에 넣을지 또한 전달한다.
꽤나 심플하게 삽입하는 모습이다. 사이즈를 체크하고, 연산 횟수를 센다. 중요한 것은 fixAfterInsertion() 인데 여기서 앞서 설명한 균형 맞추기가 이뤄진다.
이 fixAfterInsertion은 아주 잘 짜여져 있다.. 한번 java HashMap의 균형을 맞추는 부분인 balanceInsertion()를 보고 오면 이해할 것이다. 정말 어질어질 하다..
앞서 설명한 삽입 이후 균형을 맞추는 과정이 while문 안에서 이루어지고 있다.