레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binarytree)라 부른다. 자가 균형 이진트리는 대표적으로 자식의 Depth를 이용하는 AVL 트리와, 노드의 색을 이용하는 Red Black Tree 등이 있다.
이중 노드의 색을 이용한 Red Black Tree (이하 RB 트리)에 대한 설명을 하고자 한다.
트리에 대해 알고 있어야 하며, AVL 트리와 비교하기 좋으므로 이 부분은 더보기를 참고하자.
일반적인 이진 탐색 트리에 [1] [2] [3] [4] [5] [6] 값을 순서대로 삽입하게 되면 아래와 같이 한쪽으로 치우친 형태가 나온다.
이경우 루트인 1 노드에서 임의의 노드를 찾기 위해서는 최대 6회 (= 트리의 크기가 N일 때, N회)의 탐색이 필요하다.
하지만 꼭 루트가 1이라는 보장이 없어도 된다면, 다음과 같이 트리를 재 배열할 수도 있을 것이다.
루트를 고정하지 않은 채, 원소를 6개 갖는 이진 탐색 트리를 최대한 효율적을 배치한다면 아래와 같은 형태가 나올 것이다.
이렇게 할 경우 루트인 4에서 임의의 노드를 찾기 위해서는 최대 3회 (= 트리의 레벨이 L일 때, L회)의 탐색이 필요하다. 트리의 레벨 기준이 아니라 트리의 노드 기준으로는 log N의 탐색이 필요하다. 이진트리에서 레벨이 L인 트리는 2^L - 1 개의 노드를 담을 수 있다. 정수부만 취할 때, L = log2 N 이 된다.
즉 좌우에 균형이 잡혀서 트리의 레벨을 최소화한다면, 탐색 효율이 한 단계 상승한다. 이진트리 : O(N) 균형 이진트리 : O(log N)
어떻게 보면 너무 당연하다. 트리를 압축해서 빈틈없이 꽉꽉 채워 넣으면 탐색 횟수는 당연히 줄어든다.
사용단계에서 트리의 상태를 고려하며 균형 트리를 만들어가며 사용할 수도 있다. 하지만 현실적으로 저장, 삭제 작업은 트리의 상태를 보며 하는 작업이 아니다. 아무 값이든 들어올 수 있고, 어떤 값이든 나갈 수 있어야 한다.
이러한 압축된 트리, 균형 잡힌 트리를 삽입 삭제 단계에서 스스로 구성할 수 있도록 고안된 트리가 자가 균형 이진 탐색 트리이다. 이번 포스팅에서는 그중에서 RB트리에 대해 살펴본다.
다음과 같은 조건을 만족하는 트리를 RB트리라고 부른다.
모든 노드는 red 또는 black의 색을 갖는다.
모든 NIL 노드는 black이다. (= null은 black으로 간주한다.)
모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.)
임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다.
규칙에 대해 약간의 설명을 추가한다.
모든 노드는 red 또는 black의 색을 갖는다.
왼쪽은 옳게된 RB 트리이다. 그에 비해 오른쪽의 2번 노드는 RB트리의 규칙에 맞지 않는 색이다. 모든 노드가 red 또는 black으로 구분된다는 간단한 규칙이다.
모든 NIL 노드는 black이다. (= null은 black으로 간주한다.)
NIL 노드는 일반적인 트리에서 null을 대체하는 임의의 노드이다. 이는 null은 black으로 취급한다는 뜻인데, 이후 진행될 RB트리의 구현에서 부모의 형제나, 형제의 자식 노드를 확인해야 하는 경우가 있다. 이때 형제에게 자식이 없다던지 하는 예외를 매번 처리하게 되면 구현 양이 많아진다. (모든 색 체크에서 if null? -> black, else -> check color를 해야 한다)
그래서 먼저 RB트리를 만드신 분들이 정말 엄청난 아이디어인, null을 의미하는 노드를 하나 만들어두고 그 친구의 색을 black으로 만드는 방법을 만들어 두셨다. NIL 노드 덕분에 항상 check color 가능하다. 정말 심플하면서도 동일한 동작을 할 수 있게 하는 강력한 아이디어이다.
NIL 노드의 위치 자체는 위와 같이 되어있다. 새로운 노드를 만들 때도 우선 새로운 노드의 부모 자식을 모두 NIL로 채우고 연결하는 방식으로 구현한다.
하지만 매번 NIL을 그리는 것은 힘들기 때문에 이후 이어질 포스팅에서 NIL 노드는 생략된 채 그려질 예정이다.
모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.)
RB 트리의 부모 자식 연결은 아래의 3가지가 가능하다.
red - red 연결이 존재할 경우, 그 트리는 RB 트리가 아니다.
오른쪽 트리는 올바른 RB 트리가 아니다.
임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다.
조금 헷갈릴 수 있는 부분이다.
위와 같은 트리가 있다고 했을 때, 시작 노드에서 이동 가능한 경로는 다음과 같다.
이 모든 경로에 대해, 만나는 black의 개수를 세보자.
모두 같은 값 (여기서는 1) 이 되어야 한다는 성질이다.
이러한 성질이 임의의 노드에 대하여 만족해야 한다는 의미인데. 예를 들어 아래와 같은 트리는 black 개수 규칙을 어긴 케이스이다.
이상의 4개 규칙은 Introduction to Algorithms 서적에서 제안된 규칙이며 몇 가지 추가적인 규칙을 주장하는 사람들도 있다.
예를 들면 "루트가 항상 black이어야 한다.", "루트에서 시작하는 가장 긴 경로는, 루트에서 시작하는 가장 짧은 경로의 2배를 초과하지 않는다." 등의 규칙이 있지만 이것들 또한 틀린 것은 아니다.
다만 루트가 항상 black 이어야 한다는 규칙은 정상적인 RB트리에서도 루트가 red가 될 수 있고, red가 된 루트를 black으로 바꾸더라도 위에서 제기한 4가지 규칙에 영향이 없다. 그러므로 root가 red라면 black으로 바꾼 뒤 진행하는 식 등으로 큰 동작에선 차이가 없다.
또, 루트에서 시작하는 가장 긴 경로는, 루트에서 시작하는 가장 짧은 경로의 2배를 초과하지 않는다. 는 규칙은 사실 규칙이라기보단 RB트리의 특징이다.
모든 경로에서 black의 숫자가 같기 때문에 가장 짧은 경로는 모두 black으로만 이루어진 경로가 된다.
가장 긴 경로는 red가 연달아 나올 수 없기 때문에 red, black이 번갈아 나오는 경로가 가장 길게 될 것이다.
"black의 개수가 정해져 있으므로, 그 정해진 개수 미만의 경로가 나올 경우 RB트리가 아니다." + "red가 연속으로 나올 수 있기 때문에 red black이 연속으로 나오는 것 이상의 길이가 나온다면 black이 정해진 개수 이상이 있거나 red가 연속으로 나온 것이므로 RB 트리가 아니다."의 조합으로 탄생된 특징이다.
여하튼 추가적인 조건은 위의 4가지 조건에서 파생된 조건에 가깝기 때문에. 4가지가 만족된다면 삽입, 삭제 과정에서 다른 형태가 나타나더라도 모두 RB 트리라고 볼 수 있다.
