red black tree

cpp로 공부하다 그림만 잇으면 js로도 구현이 잘 되어서 그림을 정리해 놓는다
red black tree는 이진 탐색 트리에서 몇가지 규칙을 추가해서 균형 잡힌 트리 구조를 만드는 알고리즘으로 배웠다.
그 규칙만 따라서 코드를 작성하면 잘 동작했다.

일단 red black tree의 규칙부터 알아둔다

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다. 
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

이진 탐색 트리에서 insert에서 균형 잡는 규칙의 함수를 추가한다
이진 탐색으로 insert와 동일하고 이 후 추가할 규칙은 다음과 같다

 1) parent = red , uncle = red
 -> 색상 변경
 2) parent = red , uncle = black (triangle)
 -> list 모양으로 펴준다
 3) parent = red , uncle = black (list)
 -> 색상 변경 및 회전을 해준다

아래는 1번 일 경우 그림
           [pp(B)]
[parent(R)]      [uncle(?)]
       [n(R)]
  
아래와 같이 색상을 바꿔준다
       [pp(R)]
 [p(B)]      [u(B)]
     [n(R)]

아래는 2번 일 경우 그림
letf rotate해서 삼각형 모양을 펴준다
      [pp(B)]
 [p(R)]      [u(B)] //[p(R)]을 대상으로 LEFT ROTATE 해준다
    [n(R)]
  
         [pp(B)]
    [n(R)]    [u(B)]
 [p(R)]

 list인 상황이 된 경우
            [pp(B)]
       [p(R)]   [u(B)]
   [n(R)]
   
 아래와 같이 색상부터 변경해준다
           [pp(R)]
       [p(B)]   [u(B)]
   [n(R)]
   
 이후 회전 R
       [p(B)]
   [n(R)] [pp(R)]
               [u(B)]
  결과적으로 말단 B 부모 R 조상B

추가로 Left Rotate 란?

그림1에서

       [x]
    [1]   [y]
        [2] [3]
        
그림2로 바꾼 모습을 가르킨다.

       [y]
    [x]   [3]
  [1] [2]
  
아래는 Right Rotate  

그림1에서

       [y]
    [x]   [3]
  [1] [2]

그림2로 바꾼 모습을 가르킨다.

      [x]
   [1]   [y]
       [2] [3]  

삭제 코드 로직 그림 정리중,,

 먼저 BST 삭제를 실행
 CASE 1) 삭제할 노드가 RED면 그냥 삭제하고 끝
 CASE 2) ROOT가 DOUBLE BLACK -> 추가된 BLACK을 삭제하고 끝
 CASE 3) DOUBLE BLACK의 sibling 노드가 RED면 
         - 1) s = black, p = red (s <-> p 색상을 교환) 2) DB방향으로 rotate(p)
 CASE 4) DB의 sibling 노드가 black && sibling 양쪽 자식도 black 이면 
         - 1) 추가된 black을 parent에게이전	 2) p가 red면 black이 됨 / p가 black면 DB가 됨 3) s=red 4) DB가 존재하면 다음 케이스 진행
 CASE 5) DB의 sibling 노드가 black && sibling의 near child = red, far child = black면 
         - 1) s <-> near 색상 교환 2) far 방향으로 rotate(s) 	
 CASE 6) DB의 sibling 노드가 black && sibling의 far child = red 면 
         - 1) p <-> s 색상 교환 2) far = black 3) rotate(p) DB방향으로 4) 추가된 black를 제거
         

삭제 코드를 그림으로 그려서 기억해둘까 하다가 삭제 코드를 외우고 있는건 크게 의미가 없다고 판단했다.
중요한건 red 노드를 삭제는 문제없지만 black노드 '삭제시 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.'
는 규칙에 어긋나서 그것을 보정해주는 로직을 실행한다. 이때 중요한 것은 삭제되는 노드의 sibling노드가 중요한 역할을 한다 정도로만 기억해두는게 맞다고 판단하여 red black 트리의 정리는 이것으로 마친다.