CLRS로 레드 블랙 트리 논하기 #2 : 연습 문제

회전!

• R rotate
  • 부모 노드가 자식의 R로 이동한다.
    • y parent를 x parent로 대입하고 그 다음 기존 y parent는 x right랑 연결.
    • 만약 x right가 있을 경우 x right parent는 y가 되고, y left에 위치하게 된다.자식은 새로운 부모 노드가 된다.

Left Rotation | Right Rotation

1. 바꿀 애를 지정해준다.
   • y = x.right
   • x = y.left
2. 지정한 애의 자식들을 옮겨준다. 이것을 양쪽에 대해 연결 해 주어야 한다.
   • x.right = y.left
   • if y.left != T.nil
     • y.left.parent = x
   • y.left = x.right
   • if x.right !== T.nil
     • x.right.parent = y
3. 우선 부모 노드를 동일하게 맞추어 본다.
   
   • y.p = x.p
   • x.p = y.p
4. 이제 위치에 대해 논하게 된다.
   • 부모 노드 있나? 있다면, x는 부모 입장에서 어디에 있나? | 앞 순번에서 했던 작업의 결과를 참고해야해서 3번이 앞에 된 것.
   • if x.parent == T.nil
     • T.root = y
   • else if x == x.parent.left
     • x.parent.left = y
   • else x.parent.right = y
   • if y.parent == T.nil
     • T.root = x.parent
   • else if y == y.parent.left
     • y.parent.left = x
   • else y.parent.right = x
5. 바꿀 당사자들끼리 양쪽에 대해 연결 해준 뒤에 종료한다.
   • y.left = x, x.parent = y
   • x.right = y, y.parent = x

지금 논하고 있는 이 내용은 CLRS 연습문제 : 오른쪽 회전 구현을 포함한 그냥 양쪽에 대한 psudo일 뿐이다. ㅇㅋ. 맞춤

연습문제 2.
n개의 이진 탐색트리에서 n - 1번의 회전이 가능함에 대해 논하기

손가락이 5개이면 연달아 붙은 손가락 쌍은 4개가 만들어진다. 이런 식으로 생각하면 이진 탐색트리도 연달아 붙은 식으로 가능하다.

 

연습문제 3.
맨 위에 있는 사진에 서브트리 에이, 비, 씨를 보자. 좌방향 회전을 수행하면 높이가 어떻게 바뀌게?

에이는 깊이가 한 칸 증가, 비는 유지, 씨는 한 칸 감소한다.

 

연습문제 4.
n개의 노드가 주어진 이진 검색 트리에서 O(n)의 회전을 통해 구성은 같되 형태가 다른 트리를 만들 수 있는가?

1부터 15까지 자연수가 들어있는 이진 검색 트리를 어떻게 잘 구워 삶은 회전을 하면 15부터 좌측 편향 14 13 12.... 1까지 만들 수 있다.
회전만해서 가능하다.

삽입

레드 블랙 트레이 삽입은 O(log n) 의 시간이 소모 되는 것을 안다. 사실 이 값은 이진 탐색 트리에서 오긴 했다. 레드 블랙 트리에는 조금 더 할 일이 있긴 하지만, 그걸 감안해도 이 시간이다. 뭘 하는지 한번 보자.

연습문제부터..

연습문제 1.
레드블랙트리 삽입의 psudo에는 새로운 노드를 red 로 삽입한다. 그냥 검정으로 삽입해도 레드 블랙트리의 4번 룰을 위반하지 않을텐데,
그렇게 하지 않는 이유는 뭐게?

트리의 효율적 유지와 간결한 균형 복구를 위한 것이다. Black Height 개념이 트리를 이런 제약을 만들게끔 하여 다소 복잡하게끔 만들 수있다. 다만 궁극적으론 이후 균형 조정도 국소적인 수정으로 이룰 수 있기 때문에 red로 삽입을 진행해서, 차라리 룰 위반을 전제하고 접근하여 해결 하는 과정에서 균형 조절이 이루어지게끔 의도한 것이다.

 

연습문제 2.
41 38 31 12 19 8을 차례대로 삽입한 레드블랙 트리는 어떻게 생겼게?

 

연습문제 4.
권교수는 삽입 후 교정 과정에서 NIL의 색이 빨강으로 배치 될 지도 모름을 우려하고 있다. 권교수를 설득하자. 

• 삽입 후 교정을 수행하는 RB-INSERT-FIXUP은 속성 위반을 해결하는 과정이다.
  루트는 항상 검정이어야하고, 자식 노드는 레드 블랙 트리의 속성에 맞게 일부 조정된다.
• NIL은 사실 상 비어있는 statement를 말하고, 색이 없어도 되는건 아니지만 룰 준수를 위해 기본적으로 검정색이다.
• 루트의 부모가 nil 일 경우 루트가 레드로 설정되는 일은 없다. (룰 #2 로 인해)
• 이런 이유로, NIL이 레드로 존재하는 경우는 있을 수 없다.

 

연습문제 5.
2개 이상의 노드를 가진 레드블랙트리가 Red를 한 개 이상 가짐을 논하자.

Black height 개념을 생각하면 말이 된다. 자식이 모두 블랙이라면 Black Height는 모두 동일해야 하면서, 최단 - 최장 경로의 높이 차이 제한을 유지하기가 어려워진다. 이렇기 떄문에 레드 노드의 존재는 반드시 필요하다.

 

연습문제 6.
parent pointers를 선언하지 않고 동일한 삽입 함수를 작성 하는 두 가지 방법

1. 레벨 추적 : 상위 경로를 따로 저장해두는 prev를 선언하는 경우를 말한다.
2. 자료구조 사용 : 스택을 사용하여 각 노드의 진행 정도를 저장하는 방법이다.