(알고리즘) 레드블랙트리
이번 포스팅은 레드 블랙 트리를 포스팅할 예정이다.
레드 블랙트리를 포스팅하는 이유는 Java를 더 잘 이해하기 위해서이다. Java의 HashMap 사이즈가 64가 넘을 때에 레드 블랙트리를 사용하고 TreeMap 또한 레드 블랙트리를 사용하기 때문에 해당 코드를 이해하기 위해서 우선적으로 레드 블랙트리에 대한 이해가 선행되어야 함을 깨달았다.
조금 힘들더라도 내실있는 포스팅을 해보도록 노력하겠다!
레드 블랙트리는 왜 쓰는가?
이진 탐색 트리의 단점을 보완하기 위해서 쓰는 자료구조이다.
만약에 정렬된 데이터를 이진 탐색 트리로 구현한다면 아래와 같은 구조일 것이다. (이미 정렬된 데이터에 대해서는 비효율적인 자료구조)
그렇다면 시간복잡도를 따진다면 O(n) 이 나오게 된다. 결코 좋은 시간 복잡도라고 할 수 없으므로 이를 개선하기 위해서 레드 블랙트리라는 자료구조가 탄생하게 되었다.
레드 블랙트리의 동작원리
레드 블랙트리는 이진 탐색 트리에 대한 단점을 개선하기 위한 자료구조이기 때문에 기본 동작 방식은 크게 다르지 않다.
(작으면 좌측하위노드로 크면 우측 하위 노드로)
하나 이진 탐색 트리와 다르게 여러 가지 까다로운 조건들이 붙는다.
이러한 조건들이 이해하는데 어려움을 준다. 어떠한 조건들이 있을까?
Condition
- 각 노드는 red 혹은 black 이다.
- 루트 노드 (최상단 노드)는 black 이다.
- 모든 리프 노드 (최하단 노드)는 black 이다.
- red 노드의 자식들은 모두 black이다. (red - red 가 연속되면 안 된다.)
- 모든 노드에 대해서 그 노도의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다.
1, 2, 3 번은 이해가 바로 되지만 4, 5번은 이해가 까다로웠다.
그래서 아래 예시를 준비하였다.
Red Red Violation with Rotation
3번의 케이스에서 "red - red 가 연속되면 안 된다." 고 언급하였다.
그러면 발생하는 경우에는 어떻게 처리를 해야 하는가?
이때는 좌우로 회전을 시킨다.
생각보다 회전을 이해 가기가 쉽지가 않았다. 필자가 이해하기 쉬웠던 방법을 공유하고자 한다. 좌 우 회전 중 하나만 이해하면 나머지는 어렵지 않기 때문에 좌 회전 만을 예시로 들겠다. (우는 한번 직접 그려서 해보시기를!)
위의 노드로 설명을 해보자 한다.
일단 좌회전을 하면 X 노드는 a를 가지고 아래로 내려가게 되고
Y노드는 b,c를 가지고 위로 올라가게 된다.
이때 Y는 b, c 를 가지고 있기 때문에 너무 무거워 버거움을 느낀다.
미안하게도 좌측에 있던 b 노드를 잘라내 버린다. (꼭 좌측 이어야 함)
배신감을 느낄 틈도 없이 b 노드는 떨어져 내리게 되고 간신히 X를 붙잡게 된다.
잡고 나서 보니 X의 하위의 우측 노드였던 것이었다.
X도 상주를 허락하였고 결국 b는 그곳에 정착하게 된다.
약간의 오해의 소지가 있을 수도 있으나 필자는 이러한 방식으로 이해하니깐 큰 틀을 익힐 수 있었다.
필요하신 분들은 이와 같이 이해에 도움을 받길 바라는 마음이다.
어떠한 기준으로 회전하는가 with 시뮬레이션
위에서 회전에 대해서 알아보았고 이제 구체적으로 언제 회전하는지에 대한
"기준"
이 필요하다.
기준에 대해서 부가적으로 설명하고 추가적으로 Color Change 과정을 설명하겠다.
마지막으로는 시뮬레이션을 통해서 위의 내용을 정리하면서 마무리하고자 한다.
이해하기 쉽게 노드 간의 관계를 자식 삼촌 부모 할아버지라고 표현하겠다.
Red - Red Violation Condition
- 삼촌이 레드일 때
- 부모와 삼촌의 색깔을 black 으로 바꾸고 할아버지의 색깔을 바꾼다.
- 삽입될 녀석이 부모의 오른쪽 자식인 경우
- 부모를 기준으로 좌회전한다.
- 삽입될 녀석이 부모의 왼쪽 자식인 경우
- 할아버지를 기준으로 우회전한다.
Basic Condition
- 각 노드는 red 혹은 black 이다.
- 신규로 삽입되는 노드는 red이다.
- 루트 노드 (최상단 노드)는
- 모든 리프 노드 (최하단 노드)는
- red 노드의 자식들은 모두 black이다. (red - red 가 연속되면 안 된다.)
- 모든 노드에 대해서 그 노도의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다.
예시 데이터
| 1 | 65 | 129 | 193 | 257 | 321 | 385 | 449 | 513 |
65 삽입
65는 1보다 크기 때문에 1의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
129 삽입
129는 65보다 크기 때문에 65의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(65)와 자신 (129) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드는 없고 삽입된 녀석이 우측이기 때문에 부모를 기준으로 좌회전한다. (Red - Red Violation Condition -2)
루트 노드는 항상 black 이어야 하기 때문에 65를 black으로 변경한다. (Basic Condition - 3)
자손인 리프 노드에 이르는 모든 경로가 동일하지 않기에 좌측 자식 노드인 1의 값을 red 로 변경한다. (Basic Condition - 5)
193 삽입
193은 129보다 크기 때문에 129의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(129)와 자신 (193) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드 1과 부모 노드 129가 모두 red 이므로 부모 노드와 삼촌 노드의 색깔을 black으로 변경하고 할아버지 색깔을 red로 변경한다.
(Red - Red Violation Condition -1)
루트 노드는 항상 black 이어야 하기 때문에 65를 black으로 변경한다. (Basic Condition - 3)
257 삽입
257은 193보다 크기 때문에 193의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(193)와 자신 (257) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드는 없고 삽입된 녀석이 우측이기 때문에 부모를 기준으로 좌회전한다. (Red - Red Violation Condition -2)
자손인 리프 노드에 이르는 모든 경로가 동일하지 않기에 좌측 자식 노드인 값을 red 로 변경하고 부모 노드를 black으로 변경한다.
(Basic Condition - 5)
321 삽입
321은 257보다 크기 때문에 257의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(257)와 자신 (321) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드 129와 부모 노드 257가 모두 red 이므로 부모 노드와 삼촌 노드의 색깔을 black으로 변경하고 할아버지 색깔을 red로 변경한다.
(Red - Red Violation Condition -1)
385 삽입
385는 321보다 크기 때문에 321의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(321)와 자신 (385) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드와 부모 노드는 색깔이 다르기 때문에 (Red - Red Violation Condition -1)을 성립하지 않는다.
삽입된 녀석이 우측이기 때문에 부모를 기준으로 좌회전한다. (Red - Red Violation Condition -2)
자손인 리프 노드에 이르는 모든 경로가 동일하지 않기에 좌측 자식 노드인 값을 red로 변경하고 부모 노드를 black으로 변경한다.
(Basic Condition - 5)
449 삽입
449는 385보다 크기 때문에 385의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삽입 후 부모 노드(385)와 자신 (449) 모두 red 이기에 red - red Violation이 생긴다.
삼촌 노드 257과 부모 노드 385가 모두 red 이므로 부모 노드와 삼촌 노드의 색깔을 black으로 변경하고 할아버지 색깔을 red로 변경한다.
(Red - Red Violation Condition -1)
이때 할아버지 노드를 red로 변경함으로써 할아버지(321)와 증조할아버지(193)가 모두 red 이기에 한번 더 red - red Violation이 생긴다.
할아버지의 삼촌 노드(1)가 현재 black이고 1 증조할아버지 (193)가 red 이므로 (Red - Red Violation Condition -1)는 성립하지 않는다.
현재 기준 노드인 할아버지 노드는 우측 노드기 때문에 (Red - Red Violation Condition -2)가 성립하며 좌회전을 한다.
자손인 리프 노드에 이르는 모든 경로가 동일하지 않기에 좌측 자식 노드인 값을 red로 변경하고 부모 노드를 black으로 변경한다.
(Basic Condition - 5)
513 삽입
513은 449보다 크기 때문에 385의 우측 하위 노드로 들어간다.
신규 노드이기에 들어가고 red 로 칠한다. (Basic Condition - 2)
삼촌 노드와 부모 노드는 색깔이 다르기 때문에 (Red - Red Violation Condition -1)을 성립하지 않는다.
삼촌 노드는 없고 삽입된 녀석이 우측이기 때문에 부모를 기준으로 좌회전한다. (Red - Red Violation Condition -2)
자손인 리프 노드에 이르는 모든 경로가 동일하지 않기에 좌측 자식 노드인 값을 red 로 변경하고 부모 노드를 black으로 변경한다.
(Basic Condition - 5)
결과
정리
레드 블랙트리는 좋은 자료구조이지만 그에 대한 조건이 너무 까다로워서 이해하기가 쉽지가 않았다.
가장 중요한 것은 기본 조건을 만족하는 것이고 레드 레드가 만났을 때 정렬 방법이다.
이론적으로는 와 닿았으나 실제로 해보니 만만한 작업이 아니었기 시뮬레이션을 첨부하여 부가설명을 진행하였다.
오늘도 나의 포스팅이 많은 분들에게 도움이 되길 바라며 포스팅을 마치도록 하겠다.