Red-Black Tree

각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추는 트리

Red-Black Tree 정의

1. 모든 노드는 Red이거나 Black이다.
2. 루트 노드는 Black
3. 리프 노드(NIL)는 Black
4. Red 노드의 자식은 모두 Black (Black노드의 자식이 Red 노드는 아님)
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 Black노드를 포함한다.(Black-Height : 노드 X로부터 노드 X를 포함하지 않은 리프노드까지의 경로상에 있는 Black 노드의 개수)

Red-Black Tree 특징

• Binary Search Tree의 일종으로 BST의 특징을 모두 갖는다.
• 루트 노드부터 리프 노드까지의 모든 경로 중 최소/최대 경로의 비율이 2보다 크지 않다.
• 자식 노드가 없을경우 포인터는 NIL 값을 저장
• 4번 속성에 따라, 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때,
  최장 경로는 블랙 노드와 레드노드가 번갈아 나오는 것이 된다.
• 5번 속성에 따라, 모든 경로에서 블랙 노드의 수가 같다고 했기때문에
  존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로 거리의 두배 이상이 될 수 없음
• 삽입, 삭제, 검색시 최악의 경우에서는 시간복잡도가 트리의 높이(logN)에 따라 결정되기때문에 이진탐색 트리에 비해 효율적

삽입

BST 특성을 유지하면서 노드 삽입
삽입된 노드의 색을 Red로 지정(Black-Height 변경을 최소화하기 위해서)
삽입 결과 RBT 특성에 위배될 시에는 노드 색깔 조정
Black-Height가 위배 되었다면 회전을 통해 height 조정

삭제

BST 특성을 유지하면서 노드 삭제
지워진 노드 색이 Black이라면 Black-Height가 1 감소한 경로에
Black 노드 1개가 추가 되도록 회전하고 색깔 조정
지워진 노드색이 Red라면 위배가 발생하지 않으므로 RBT 그대로 유지

회전

• 오른쪽 회전
  루트가 10으로 변경, 13이 10의 오른쪽 자식으로 들어간다
  13이 10의 오른쪽 자식으로 변경되면서 13이 12의 왼쪽 자식으로 옮겨진다.

• 왼쪽 회전
  루트가 13으로 변경, 10이 13의 왼쪽 자식으로 들어간다
  10이 13의 왼쪽 자식으로 변경되면서 12가 10의 오른쪽 자식으로 옮겨진다.