Red Black Tree

Red Black Tree는 RBT라고도 불린다. RBT는 BST(Binary Search Tree)를 기반으로하는 트리 형식의 자료구조이다. BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 등장하였다.

RBT의 삽입, 삭제, 검색 연산은 모두 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때 트리의 깊이를 최소화하여 시간 복잡돌르 줄이는 것이 RBT의 핵심적인 부분이다. 동일한 노드의 개수일 때 깊이가 최소가 되려면 Complete Binary Tree의 형태를 띄어야 한다.

Red Black Tree의 정의

Red Black Tree는 다음을 만족하는 Binary Search Tree이다.

• 각 노드는 Red 혹은 Black의 색을 가진다.
• 루트 노드는 Black이다.
• 각 단말 노드(Leaf Node)는 Black이다.
• 어떤 노드의 색깔이 Red라면 그 노드의 2개의 자식 노드는 모두 Black이다.
• 각 노드에 대해서 노드로부터 단말 노드(Leaf Node)까지의 단순 경로는 모두 같은 수의 Black Node들을 포함하고 있다. 이때 Black Node들의 수를 Black Height라고 한다. (시작 노드를 제외하고 Black Height를 계산)

Red Black Tree의 특징

• Binary Search Tree를 기반으로 하는 트리이므로 Binary Search Tree의 특징을 모두 가진다.
• 루트 노드로부터 단말 노드까지의 모든 경로 중 최소 경로와 최대 경로의 비는 2보다 크지 않아야 한다. 이러한 상태를 balanced 상태라고 한다.
• 노드의 자식 노드가 없을 때 자식 노드를 가리키는 포인터는 NIL값을 저장한다. 이때 NIL들을 단말 노드로 간주한다.

Red Black Tree의 삽입

BST의 특징을 유지하며 노드를 삽입한다. 삽입된 노드는 Black Height를 최소화 하기 위해 Red Node로 지정한다. 삽입 결과 RBT의 특성이 위배될 경우 삽입된 노드를 Black Node로 지정하고, Black Height가 위배되면 Rotation을 통해 Height를 조정한다. 이러한 과정을 통해 RBT의 동일한 Height에 존재하는 내부 노드들의 Black Height가 같아지게 되고 이로 인해 balanced 상태가 만들어지고 최소 경로와 최대 경로 간의 비가 2를 넘지 않는다.

Red Black Tree의 삭제

삭제도 삽입과 마찬가지로 BST의 특징을 유지하며 노드를 삭제한다. 석제될 노드의 자식 노드 개수에 따라 Rotation 방법이 달라진다. 만약 지워진 노드가 Black Node였다면 Black Height가 1 감소한 경로에 Black Node가 1개 추가되도록 Rotation하고 노드의 색을 조정한다. 지워진 노드가 Red Node라면 Violation이 발생하지 않으므로 RBT가 유지된다.

** Java Collection에서 ArrayList도 내부적으로 RBT로 이뤄져있고, HashMap에서의 Separate Chaining에서도 사용된다. 그만큼 효율이 좋고 중요한 자료구조이다.