RB Tree 삽입

출처: https://www.geeksforgeeks.org/red-black-tree-set-2-insert/?ref=lbp

Red-Black Tree의 삽입

RB의 삽입에 대해 알아보자.
색 변환과 rotate를 제외하면 Binary Search Tree의 삽입과 같다. (BST를 이해하고 오자!)

 

위 그림과 같이 insert 하려는 node를 X, X의 부모를 P, 부모의 부모는 G, 부모의 형제인 삼촌노드는 U로 표현하자.

그리고 BST의 insert 과정이 끝났다고 생각하자.  (즉, x가 어디에 위치할지 찾고 삽입한 것이다!)

X는 항상 빨간색이다!

1. X가 루트인 경우 
   X노드가 루트라면, RB의 특성 1을 유지하기 위해 BLACK으로 변경해준다.
   
   
2. X가 루트가 아닌 경우
   
   1.  부모가 검은색인 경우
      X는 항상 RED이므로 부모가 BLACK이면 삽입해도 RB가 깨지지 않는다!! (5가지 특성이 모두 지켜진다.)
      때문에 검은색인 경우는 BST의 삽입과 동일하다. (추가 작업이 없다)
      
   2. 부모가 붉은색인 경우
      1. 삼촌이 붉은색
         

         

         부모와 삼촌을 검은색으로 칠한 후 !!! G -> X 로 하여 다시 1번과정을 반복한다.

         
          
      2. 삼촌이 까망
         
         
         1. X는 오른쪽 자식
            

            

            부모를 pivot으로 왼쪽으로 회전한다!! 

            그 후, 다시 G를 기준으로 오른쪽 회전한다!! (왜냐면 현재, G를 기준으로 좌/우 경로의 Black depth가 맞지 않는다. 때문에 rotate한다.
            
            위 사진은, 오른쪽 회전 후 recolur까지 진행한 것이다.
            결국, 모든 rotate, recolur 과정은 RB의 특성 5가지를 만족하기 위함이다. 이를 생각하며 따져보면
            당연한 과정임을 알 수 있다!
            (** rotate과정에서 자식이 옮겨지거나 하는 이유는, BST를 만족하기 위함이다. rotate에 관해서는 따로 포스팅 해보자!)
            
            
            
         2. X는 왼쪽 자식
            이 경우는, 위 그림에서 2번째 와 같다.

위 경우가 전부는 아니다. 현재 다룬 경우는
1. 부모가 검은색인 경우 전부
2. 부모가 빨강인데 삼촌도 빨강인 경우 전부
3. 부모가 빨강인데 삼촌이 검은색!! ( + 부모는 왼쪽 자식) 인 경우
이다. 즉, 3번에서 부모가 오른쪽 자식인 경우만 고려하지 않았다.

이 경우는 3.의 경우와 완전히 반대로 생각하면 동일하다.

정리하자면,
1, 2번의 경우 이해하기 쉽다.
3번의 경우, 먼저 G - P - X 의 노드가 linear하게, 일직선에 놓이게끔 회전하고 (이미 일직선이라면 회전할 필요 없다)
그 후에 G를 기준으로 회전시킨다!!
그럼 G를 기준으로 회전시키는 이유는 뭘까??
이 G 회전(이라고 하겠다)를 할 때 상황을 생각해보면, U와 P의 색이 다르다 (정확히는 U가 까맣다.)
그래서 black depth가 U쪽이 1개 높고, 때문에 G를 기준으로 회전하면 U 쪽은 그대로, P쪽은 -1 이 된다 (빨강 노드만 두개니까!)

그럼 문제가 생긴다. 그래서, 빨강 노드인 P와 검은 노드인 G를 교환한다. 그러면 U쪽은 그대로, P쪽은 + 1이 된다. ( 더 높은 경로에 검은색이 생겼으므로!) 때문에 black depth를 맞출 수 있다.  (설명이 똥같다....)

더 자세히 하고 싶었지만... 쉽지가 않다 ㅠㅠㅠ 삭제는 가능할지 모르겠다 휴

이해하기 매우 좋은 사이트를 추천합니다!!
https://www.geeksforgeeks.org/red-black-tree-set-2-insert/?ref=lbp