레드 블랙 트리(red black tree)

레드 블랙 트리란

AVL와 비슷하게 자가 균형 이진 탐색 트리지만 다른 점이 있다. AVL에선 삽입, 삭제가 발생할 때마다 균형을 조정해야 하는 문제가 있다. 아무리 $\log(N)$의 시간 복잡도를 보장한다 해도 수천만의 쓰기 작업이 발생하면 $N\log(N) $ 시간 복잡도로 문제가 복잡해진다.

이런 문제를 해결하기 위해 레드 블랙 트리에선 삽입, 삭제 작업에서 발생하는 균형 조정을 느슨하게 대처한다. 하지만 이로 인해 탐색에선 AVL보다 균일한 시간 복잡도를 제공하진 않는다.

레드 블랙 트리의 성질

1. 루트 노드는 언제나 블랙 노드다.
2. Nil Node
   • 우리가 생각하는 말단 노드의 하위 노드에 암묵적으로 Nil Node가 생긴다고 보면 된다.
   • Nil Node는 실제 데이터가 아니기 때문에 트리의 높이 계산엔 적용되지 않지만. 밑에서 설명할 black depth를 구하는 과정에선 이를 포함해야 한다.
   • 루트의 부모를 Nil Node이나 null로 하는 경우가 있다. 이 글에선 Nil Node로 한다.
3. 레드 노드의 부모와 자식은 블랙 노드이다. (레드 노드가 연속 2번 나올 수 없다.)
   • 2번 항목하고 연계되는 내용인데 노드가 생성될 때 기본값은 레드 노드다. 이는 새로 생성된 노드의 하위에 리프 노드(null node)가 붙는다 가정하기 때문이다.
4. 모든 리프 노드는 동일한 black depth를 갖는다.
   • 모든 리프 노드는 루트 노드로 가는 동안 만나는 블랙 노드 개수가 동일하다.
   • AVL에 비해 수정이 느슨한 이유. 불균형이 발생해도 black depth가 동일하다면 조정하지 않는다.

black depth

레드 블랙 트리가 AVL에 비해 편향적임에도 동일한 시간 복잡도를 보장할 수 있는 이유. 여기서 레드 블랙 트리의 여러 특징들을 알 수 있다.

• 트리의 높이를 h라 할 때, black depth >= $\frac{h}{2}$ 보장
  • 요약하면 리프 노드(Nill Node)까지 가는 과정에서 블랙 노드를 더 많이 만난다.
  • 레드 블랙 트리에선 특수한 상황을 제외하고 레드와 블랙 노드가 번갈아 나온다.(어떠한 경우에도 레드 노드가 연속으로 나오진 않는다.)
  • 루트 노드와 리프 노드(Nil Node)는 언제나 블랙 노드라 블랙 노드를 하나 더 센다. 따라서 어떠한 경우에도 트리의 높이 h/2 이상의 값을 보장한다.
• 노드의 개수를 n이라 할 때, $h$ <= $2 \log(n + 1)$ 보장
  • $n >= 2^{black depth} - 1 >= 2^{\frac{h}{2}} - 1$ 이므로
    $n + 1 >= 2^{\frac{h}{2}} $는   $\frac{h}{2} <= \log(n + 1)$ -> $h = 2 \log(n + 1)$이 된다.
  • 이 계산식을 통해 리프 노드로 가는 경로엔 log(n + 1)개의 블랙 노드가 있고, 전체 노드 중 $ \frac{n}{2} $ 이상이 블랙 노드라고 볼 수 있다.

black depth == $\frac{h}{2}$를 만드는 경우가 있을까?

위에 black depth를 구하는 과정에선 리프 노드(Nill Node)까지 센다고 말했다. 이렇게 되면 언제나 black depth는 $\frac{n}{2}$ 보다 클 거 같다 생각을 했다.

여기에 대한 케이스를 만들기 위해 시뮬레이션 툴로 여러 경우를 만들어봤지만 black depth == $\frac{h}{2}$를 만족하는 케이스가 생각나지 않았고, chat gpt한테 시켜봐도 계속 잘못된 답을 알려줬다.

여기에 대해 좀 더 알아볼까 생각을 했지만 현재 수준에선 다루기엔 필요 이상으로 자원이 필요한 거 같아 검색한 것을 기반으로 정리한다.

geeks for geeks 를 참고해본 결과 다음 표현이 black depth에 대해 잘 표현을 해놨다 생각한다.

Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf.

해석하면 가장 먼 리프 노드까지 만나는 노드 수는 가장 짧은 리프 노드까지 만나는 노드 수의 $2$배를 넘지 않는다.

수식으로 표현하면 (${가장 먼 길이} <= \frac{가장 짧은 길이}{2}$) 이다.

삽입 과정

삽입 과정에선 조부모 노드가 Nil Node가 아닐 때부터 변화가 발생할 수 있다.
조정 작업은 AVL 트리와 같지만, 노드 색에 따라 수행이 달라진다.

새로 삽입된 노드부터 시작해, 부모 노드가 블랙 노드일 때까지 아래 과정을 수행하면서 올라간다.

1. 노드의 부모가 조부모 노드의 왼쪽에 있을 때

Case1 삼촌 노드가 레드인 경우

Case2 삼촌 노드가 블랙인 경우

• 삽입된 노드가 부모의 왼쪽 노드인 경우

• 삽입된 노드가 부모의 오른쪽 노드인 경우

2. 노드의 부모가 조부모 노드의 오른쪽에 있을 때

Case1 삼촌 노드가 레드인 경우

Case2 삼촌 노드가 블랙인 경우

• 삽입된 노드가 부모의 왼쪽 노드인 경우

• 삽입된 노드가 부모의 오른쪽 노드인 경우

삭제

삽입에 비해 꽤 복잡하다.

경우의 수가 많다 보니 한꺼번에 생각하기엔 구현도 복잡했고 테스트도 잘 안됐다. 이전 글들에선 작동 원리만 보고 충분히 구현할 수 있었지만, 이번엔 생각 외로 시간을 많이 들어서 Introduction to Algorithms 를 참고했다.

 

삭제 작업을 2가지로 나눈다.

• transPlant(이식 과정): 삭제할 노드의 부모와 교체할 노드를 서로 이어주는 작업.
• deleteBalance(조정 과정): 이식 과정에서 블랙 노드 위치에 변동이 생길 때 재귀적으로 black height를 조정하는 작업.

이 글에서는 삭제할 노드와 관련된 참조들을 교체할 노드에 연결하는 방식이다.

다른 글들을 보니, 이식 작업의 특징을 이용해 삭제할 노드와 교체할 노드의 값만 바꾼 뒤 교체할 노드가 있던 위치를 기준으로 트리를 조정하는 방식도 있었다.

개인적으로 이 방법이 좋다고 생각됐지만, 이식과 조정 과정을 같이 수행해야 하기 때문에 한꺼번에 이해하는 게 조금 힘들었다.

 

처음 하는 입장에선 조금 돌아가더라도 분할해 생각하는 게 이해하기 빠르다 생각했다.

이식 과정

Case1: 삭제할 노드 n이 자식이 없을 때

• n이 레드 노드
  • black height에 영향을 주지 않으므로 바로 삭제
• n이 블랙 노드
  • 이 경우 Nil Node들을 자식 노드로 간주하기 때문에 Case3으로 본다.
  • swapNode가 Nil Node가 되지만, Nil Node는 실제 노드로 간주하지 않기 때문에 조정 작업을 해야 한다.

Case2: 삭제할 노드 n의 자식이 하나일 때

• n의 부모와 자식을 서로이어준다. (transPlant)
• n과 직계 자식 중 하나 블랙 노드인 경우
  • 직계 자식을 블랙 노드로 바꿔준다.
• n와 직계 자식 둘 다 레드 노드인 경우
  • 레드 노드는 블랙 노드만을 자식으로 가지기 때문에 성립 불가
• n과 직계 자식 둘 다 블랙 노드인 경우
  • 조정 작업을 거쳐야 한다.

Case3: 삭제할 노드 n의 자식이 둘인 경우

• 다른 트리와 마찬가지로 삭제할 노드와 교체할 노드(swapNode)를 정한다. 교체할 노드는 2가지 중 하나를 택한다.
  • 전임 노드(PreSuccessor): 삭제할 노드보다 작은 수 중 가장 큰 수 (왼쪽 서브 트리 중 가장 큰 값)
    레드 블랙 트리를 시각화하는 사이트들은 전임 노드를 교체 노드로 사용한다.
  • 후임 노드(Successor): 삭제할 노드보다 큰 수 중 가장 작은 수 (오른쪽 서브 트리 중 가장 작은 값)
  • 이 글에선 후임 노드를 교체할 노드로 정한다.
• swapNode의 부모와 swapNode의 오른쪽 자식을 서로이어준다.
  • 후임 노드를 기준 swapNode는 왼쪽 자식을 가질 수 없다. 반대로 전임 노드라면 오른쪽 자식을 가질 수 없다.
• n의 왼쪽 서브 트리를 swapNode의 왼쪽 서브 트리에 붙인다.
• swapNode의 색을 n의 색으로 변경한다, 만약 swapNode가 블랙 노드였다면 조정 작업을 거쳐야 한다.

조정 과정

블랙 노드의 위치가 바뀌었다면, black height에 변동이 생긴다.

삭제 과정의 CASE 1, 2는 자식 노드에서 시작하고 CASE 3는 swapNode에서 시작하며 다음 조건을 만족할 때까지 루프를 반복한다.

기준 노드(node)가 루트가 아니면서, node가 블랙 노드

node의 형제 노드(sibling)이 어떤 노드인지 따라 경우가 나뉜다. 형제 노드를 구하는 설명은 생략한다.

 

이후 예시에서는 삭제할 노드가 부모의 오른쪽에 있는 경우만 본다.

왜냐하면 반대쪽의 경우 left, right 값만 바꿔주면 되기 때문이다.
(삽입 조정 과정도 한쪽이 되면 반대쪽도 left, right만 바꿔주면 된다.)

 

삭제 작업은 나열된 Case를 순서대로 확인하며, 조건을 만족하면 해당 작업을 수행한다.

 

Case1: 형제 노드가 레드 노드인 경우

Case2: 형제 노드가 두 자식(Nil Node 포함)이 블랙 노드일 때

Case3: Case2를 만족하지 않을 때

Case3-1: 형제 노드의 자식 중 삭제할 노드와 가장 먼 쪽의 노드가 블랙 노드

이게 무슨 말이냐면..

• 삭제할 노드가 부모의 오른쪽 -> 형제 노드의 왼쪽 노드가 블랙 노드인지 확인
• 삭제할 노드가 부모의 왼쪽 -> 형제 노드의 오른족 노드가 블랙 노드인지 확인 (이 케이스에선 이거임)

다시 돌아와서 수행순서는 다음과 같다. (이 케이스를 도저히 못만들겠어서 글로 쓴다...)

• 형제 노드의 오른쪽 자식 노드의 색을 블랙 노드로 변경
• 형제 노드를 레드 노드로 변경
• 형제 노드를 기준으로 Left Rotate 수행
• 형제 노드를 삭제할 노드의 부모의 왼쪽 노드로 덮어씌움

Case3-2: Case3-1을 만족하거나 만족하지 않아도 이 작업을 수행

Case4: 균형 조정 작업이 끝나면 node가 가리키는 노드를 블랙 노드로 변경

 

전체 코드

https://github.com/brorica/DataStructure/blob/master/src/RedBlackTree.java

GitHub - brorica/DataStructure: 수상할 정도로 나무를 좋아하는 레포

Refere