[ Algorithm ] Red & Black tree란?

Red & Black tree란?

          - Red & Black tree는 AVL tree에 색상이 입혀진 것이다.

          - 모든 노드는 빨강색 혹은 검정색으로 이루어져 있습니다.
             또한, 리프 노드(Externel node)들은 모두 검정색으로 이루어져 있습니다.

Red & Black tree's Properties

          1. 루트 노드와 리프 노드는 모두 검정색 노드로 구성되어 있습니다.
          2. 루튼 노드에서, 리프 노드까지의 경로에는 연속적으로 빨강색 노드가 존재할 수 없습니다.
          3. 루트 노ㅌ드에서, 리프 노드까지의 모든 경로에는 동일한 검은색 노드의 개수가 존재합니다.

* Red-Black Tree를 만들 때, node를 insertion할 때, Red를 우선적으로 삽입합니다.

Red & Black tree's Insertion

* 만약, Node를 삽입할 때, Double Red가 발생하는 경우,
   -  Uncle Node가 Black이라면, -> Restructuring을 수행하면 됩니다.
   -  Uncle Node가 Red라면, -> Recoloring을 수행하면 됩니다.

Red & Black tree's Restructuring

       1. 새로운 노드와 부모 노드, 조상 노드를 오름차순으로 정렬합니다.
       2. 셋 중 중간값을 부모로 만들고, 나머지 둘은 자식으로 만듭니다.
       3. 새로운 부모노드는 검은색으로 만들고, 나머지 자식 노드들을 빨강색으로 변환합니다.

* 중간 노드인 3을 부모 노드로 변환하고, 나머지 노드를 변환합니다.

* 중간 노드인 3을 부모 노드로 변환하고, 나머지 노드를 변환합니다.
   이후, 새롭게 부모가 된 3의 색상을 검은색으로 변환해주고, 나머지 두 자식 노드를 빨강색으로 변환합니다.

Red & Black tree's Recoloring

   1. 새로운 노드인 부모 노드와 삼촌 노드를 검은색으로 바꾸고, 조상 노드를 빨강색으로 변환합니다.
          1-1. 조상 노드 G가 루트노드라면, 검은색으로 다시 변환합니다.
          1-2. 조상 노드 G를 빨강색으로 변환하였을 때, Double Red가 발생한다면,
                   다시 Restructuring 혹은 Recoloring을 Doble Red가 발생하지 않을 때까지 반복합니다.

* 루트 노드는 검은색이라는 조건을 만족해야 하므로, 루트 노드의 색상을 변환합니다.
* Recoloring은 간단해 보이지만, 조상 노드(G)가 루트 노드가 아닐 때, 문제가 발생합니다.

참고자료

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기