CLRS로 레드 블랙 트리 논하기 #1 : 이론

이번 주는 노선을 조금 달리 하려고 한다. 레드 블랙 트리는 깊이 알아두면 꼭 트리형태가 아니더라도 알고리즘 사고 확장에 도움이 될 수 있을 것이라고 생각했기 때문이다. 다른 할 것들이 즐비하니 마냥 노선이 다르다는 핑계로 조금 느릿느릿하게 할 생각은 관둬야겠다.

CLRS에서 전반적인 레드블랙 트리의 이해도를 높이고, 전반적으로 설명이 가능 할 정도가 되면 코드 구현도 길지 않은 시간에 이뤄질 것이다. 거기에 더해 책은 번역본 말고 원서 기반에다가 직접 번역을 해서 쓰는게 나을 것 같다.

내가 느낀것은 번역본은 그냥 한글로 번역한 사람의 큰 영역의 TIL일뿐이다. 나는 남의 TIL을 잘 못본다. 그러니까 원서를 봐야겠다.

레드블랙트리의 전반적인 정의를 포함한 다양한 부분은 다른 글에서 더 정리해서 연결 할 수 있도록 애쓰겠다.

Red Black Tree 보조정리 1.
n개의 내부 노드를 가지는 레드 블랙 트리는 최대 2 lg(n+1)의 높이를 가진다.

왜죠?

• 루트가 x으로 부를 서브트리가 하나 있다고 하자. 이 서브트리는 2^BlackHeight(x) - 1 개의 노드를 가진다.
  • x가 nil이라고 할 때도, BH(x)는 0이다. (자기 자신을 제외) 그래서 성립한다.
  • 그럼 x가 어떤 내부노드라고 하자. 양의 높이를 가지고, 양 쪽 자식을 가진 x이라고 하자.
    • x의 자식 노드들은 자신의 색이 빨갛냐 거멓냐에 따라 갈린다.
    • Red라면 자신의 bh는 자신의 부모 노드인 x가 매개로 쓰이는 bh(x)와 같다.
    • Black이라면, bh(x) - 1이다.
    • 즉, x 입장에선 바로 자식 노드가 black이었고, 자기 자신은 높이 계산에서 제외하니 x의 자식이 블랙인 것을 x 입장에서 반영을 한것이라고 볼 수 있다.
    • 나는 x의 자식의 색이 중요한데 bh(x)가 왜 나오는지에 대한 의문점이 있었고 이후에 나오는 문장들에도 의문이 있었으나, 팀원들과 논해본 끝에 어떤 식으로 시뮬레이션 해서 이해하면 좋을지에 대한 방법을 좀 만들어 낼 수 있었다.
      
      • bh는 위로 올라가면서 세어지는 방식이라서, 루트의 bh가 가장 높고, 보통은 이걸 기준으로 이것저것 판가름한다.
• 굿. 따라서, x의 자식의 높이는 x의 높이보다 같거나 작을 것이다. 우리는 bh(x) - 1을 논했는데, 이걸 다르게 생각하면 x의 자식이 루트인 서브트리는 적어도 2^(bh(x) - 1) - 1의 갯수만큼 내부 노드를 가진다고 결론 낼 수 있다.
  
  
• x를 루트로 하는 서브트리는 서브트리 중 어느 한쪽의 최소인 2^(bh(x) - 1)에 대해 두 번 계산 해야한다. (좌측과 우측)
  • 2 * (2^(bh(x) - 1) - 1) = 2^(bh(x)) - 2 가 되는데 여기에 x 까지 추가하면 + 1 해서 끝의 상수가 - 1로 된다.
  • 레드 블랙 트리의 4번 룰인 : 한 노드가 Red이면 그 자식은 Black이다. (Double Red 제한) 으로 인해
    • 루트에서 리프로 가는 경로에서 이미 검정색인 루트를 제외하고 봐도 해당 길이 절반 이상은 Black으로 구성되어있다. 즉 height / 2 이상이라는 것.
    • n개의 내부노드는 n >= 2^(h/2) - 1
    • 양 변에 1을 더한 다음, 그 다음에 로그를 씌운다.
    • 2 * log(n + 1) >= h
    • 이 정리를 통해, Search, Min, Max, Successor, Predecessor 등이  O(log(n))에 가능하다고 할 수 있다.

 

연습문제 1.
자연수 1부터 15까지 키가 15개 주어진다. 세가지 다른 방법으로 2, 3, 4 Black Height인 레드 블랙 트리를 만들어보기

ㅇㅋ. 1번부터 힘들었으면 걍..

연습문제 3.
Relaxed Red Black Tree가 있다고 하자. 룰이 조금 풀어졌는데, 루트는 색상 변경이 가능해진 것을 빼고 모든 룰이 준수되어야 한다.
여기서 root의 색은 빨갛게 될것이다. 여기서 아무것도 안 건들고 블랙으로 바꿔도 레드 블랙 트리인가?

예

빨강의 자식은 반드시 블랙들이다. 이 룰이 준수된 상태에서 root를 블랙으로 바꿔도 해당 트리는 레드 블랙 트리이다.

 

연습문제 5.
root에서 nil로 가는 제일 긴 simple path는 제일 짧은 길이에 비해 최대 2배차이 이상이 가능한가?

아니오.

일단 우리는 루트에서 nil까지 어느 경로를 선택해도 Black Height가 같아야한다는 룰이 있다는 것을 알고있다. 그렇다면 여기서의 simple path에서 길이에 영향을 미치려면 빨강 노드만이 영향을 미칠 수 있다는 것을 알 수 있다.

정말 간단하게 요약하면, 실제 배치가 가능한 갯수, 연속 배치 불가능 같은 제약들로 인해 길이에 영향을 미친다고 해봐야 2배까지라는 것. 불가능하다는것을 귀류법으로 적어내려가 보겠다.

검정 노드로만 구성된 최단 경로 b가 있다. 최장이 > 2b 라면, 해당 최장 경로엔  b보다 많은 갯수의 레드 노드가 위치 할 것이다. 검정 방문 갯수는 어떤 길을 가던 같아야 하기 때문에 레드 노드만이 직접 영향을 줄 수 있다.

• 레드끼리는 인접이 불가능하니 검정 노드 사이에 배치가 가능하다. 근데 룰을 준수하려면 검정 노드보다 적어야한다.
  • b보다 많은 레드 노드가 있었다고 했으니 말이 안맞게된다. 그래서 최장 경로는 2b를 넘어가는 것이 불가능하다.

연습문제 6.
Black Height만 주어지는 경우에서 내부노드의 최대 갯수, 최소 갯수를 구하는 공식은 무엇일까?

전개 1.

같은 구조의 레드블랙트리를 놓고 Black Height를 가장 크게, 가장 작게 만든다음 그에 따른 결과 값을 공식으로 반영하려 했다. 이 의도는 같은 크기의 트리에 대해 BH 조절이 가능하다는 것이 역으로 BH 고정 시 트리의 노드 수 범위를 알 수 있을 것이라 생각했다. 어느정도 일리가 있었다고 쳐주더라.

그래서 어떻게 했느냐?

전개 2.

좌측에 BH가 3인 것중 최소 트리를 배치하고, 거기에 넣을 수 있는만큼 레드 노드를 꽂아본다.
그럼 좌측은 7개, 우측은 31개가 나온다. 3을 통해 7을 얻을 방법은 2^3 - 1, 31을 얻을 방법은 2^(3*2) - 1이다.

따라서 :

BH가 x라고 하면, 2^x - 1 ~ 2^(x * 2) -1 범위 내의 내부노드 갯수를 가진다.

가 결론이다.

연습문제 7.
레드 노드 입장에서, 레드가 최대치가 되는 비율, 그리고 레드가 최소가 되는 비율을 구해보자

레드가 최소?
걍 레드를 안쓰는 레드 블랙 트리를 만들면 된다. 진짜임. 레드 0개인 (레드) 블랙 트리도 레드 블랙 트리이다.

레드가 최대?

우린 앞에서 레드가 블랙의 갯수를 넘기가 쉽지 않다곤 하지만, 순수하게 갯수를 세어 가보면 3분의 2정도에 가까워지는 경우는 있다. 이게 완전 이진 트리일 때나 가능한 내용인데, 앞에서 다룬 1번 문제에서 Black Height가 2인 트리를 보면 전체 노드 15개중 10개가 레드이다.

여기선 최대를 구하라고 했으니 그럼 R 2 : 1 B 이다.

너무 어렵다!