Red Black Tree

BST (이진 탐색 트리)를 기반으로 둔 Tree.

Tree의 Rebalancing 방법 중 하나로 balanced한 트리이다.

각 노드는 값(key)말고도 색을 갖고 있으며, 색은 레드 or 블랙 2종류다.



1. Red Black Tree가 갖는 특성


Root Property : 루트(root)노드는 블랙(black)이다.

External Property : 모든 외부 노드 (external node)는 블랙이다.

Depth Property : 모든 단말 노드(leaf node)의 경우 루트부터 외부 노드 까지 방문하는 블랙 노드의 수가 같다.

Internal Property : 빨강 노드의 자식은 블랙이다.
== No Double Red : 레드 노드는 두개가 연속해서 올 수 없다.



2. 특징


  • BST의 모든 특징을 갖는다.

  • 노드의 자식이 없는 경우 자식을 가리키는 포인터는 NULL값을 저장 ( NULL을 leaf node로 간주)

  • 루트 노드 부터 단말 노드(leaf node)까지 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. ( balanced 상태 )

  • AVL Tree 에 비해 덜 깐깐하기에 탐색속도는 느릴 수 있으나, 삽입 / 삭제 속도는 더 빠르다.

  • 삽입, 삭제, 탐색의 시간복잡도는 O(log n)



3. 사용 예


  • Java Collection의 ArrayList
  • HashMap의 Separate Chaining
  • C++ map



4. 해시와 비교해서 본 장점


  • 순서가 있는 자료일 경우 좋다. ( 해쉬는 순서가 없음 )

  • 일관성있는 퍼포먼스를 보여준다. ( 해쉬는 rehashing시 비정상적 시간이 걸릴 수 있음 )

  • 해쉬는 페이지폴트를 일으킬 수 있다.

  • 연속된 삽입간의 공간 지역성을 유지하기 쉽다. ( 더 적은 I/O 발생)

  • 트리는 부정확한 검색에 사용될 수 있다.



5. 구현시 살펴볼 경우의 수



◾ Insert ( 삽입 )

BST 특징대로 삽입 후, 삽입 노드의 색깔을 RED로 설정. 삽입 후 RBT의 특징을 위배할 시 노드의 색깔을 조정하고, Black-Height가 위배되었다면, rotation을 통하여 height을 조정.

이때, 여러 case가 존재하는 데, 새로 삽입한 노드를 z라고 할때, 부모 노드인 p[z]가 부모 노드의 부모 노드인 할아버지 노드 p[p[z]]의 왼쪽 자식인지 오른쪽 자식인지에 따라 case가 나뉘게 된다. 두개의 경우가 서로 대칭이다.

크게 보면 아래와 같이 2가지의 경우일 때, red-black tree의 규칙이 위배가 된다.

🔴 case 1 : z 삼촌이 레드  ➡ 색상 변환 ( Recoloring )

    - z의 부모와 z의 삼촌 노드를 레드에서 블랙으로 바꾸고, z의 할아버지 노드를 블랙에서 레드로 바꾼다.
    - z의 할아버지 노드의 부모노드가 레드인 경우 이 경우를 반복 한다.
    - z의 부모가 블랙을 만날때 종료 되며, 루트까지 올라가게 되면 루트노드를 블랙으로 바꾸고 종료한다. (루트노드까지 올라가게 되면 black-height는 1 증가하게 된다.)
 🔴 case 2 : z의 삼촌이 없거나 블랙 ➡ 회전 ( rotation , restructuring)

  2(1) 부모노드 (p[z])가 할아버지 노드 (p[p[z]]) 의 왼쪽 자식일때
    - case 2-1 : z가 p[z]의 오른쪽 자식
        -> p[z]를 중심으로 왼쪽으로 회전 시키고, 여전히 레드 블랙트리 특성을 위반하므로 case 2-2를 수행한다.
    - case 2-2 : z가 p[z]의 왼쪽 자식
        -> p[p[z]]를 중심으로 오른쪽 회전 시키고, p[z]와 p[p[z]]의 색상을 바꾼다. (부모노드는 블랙으로, 할아버지 노드는 레드로)


  2(2) 부모노드 (p[z])가 할아버지 노드 (p[p[z]]) 의 오른쪽 자식일때
    - case 2-1 : z가 p[z]의 왼쪽 자식
        -> p[z]를 중심으로 오른쪽으로 회전 시키고, 여전히 레드 블랙트리 특성을 위반하므로 case 2-2를 수행한다.
    - case 2-2 : z가 p[z]의 오른쪽 자식
        -> p[p[z]]를 중심으로 왼쪽 회전 시키고, p[z]와 p[p[z]]의 색상을 바꾼다. (부모노드는 블랙으로, 할아버지 노드는 레드로)

z를 할아버지 노드 ( p[p[z]] )로 바꿔주고 할아버지의 부모가 Red가 아닐때까지 위의 case를 반복해준다.



◾ Delete (삭제)

BST의 특성을 유지하면서 삭제한 후, 삭제할 노드의 자식노드 개수에 따라 rotation 방법이 달라진다. 또한, 지워진 노드의 색깔이 Black이라면, Black-Height가 1감소한 경로에 black node가 1개 추가되도록 rotaion한다.

NULL node(leaf node) 역시 black 이다.

 🔴 case default : 삭제할 노드를 z라 할때, z가 RED라면 그냥 삭제하고, (z의 자식이 두개인 경우는 오른쪽 자식의 가장 작은 key와 key값을 교환 후 z->right의 minimum 노드를 삭제하게 되므로 이 노드의 색이 RED라면)
 BLACK이라면,  black-height가 안맞게 되므로 fix up을 수행한다. (이때, double-black개념이 등장한다.)

 삭제도 삽입과 마찬가지로 삭제한 노드 z대신 위치할 노드 x가 p[x]의 왼쪽 자식인지 오른쪽 자식인지에 대해 대칭한다.
 삭제한 노드 z대신 새로 위치한 노드를 x, 그 형제 노드를 s라고 할때,
 🔴 case 1 : s가 RED인 경우 ➡
     이때는 s의 자식들은 leafNode 일 수 없다.(조건 5 위반) => 한개라도 leafnode일 시 black-heigh가 달라지므로 무조건 두개를 가지고 있다.

   -> x가 부모노드 p[x]의 왼쪽 자식일때
     - s를 BLACK으로 p[x]를 RED로 바꿔준다.
     - p[x]를 left-Rotate 시켜준다.
     - x의 새로운 형제노드를 달아준다. (s = p[x]->right) ==> x의 새로운 형제노드는 원래 s의 왼쪽 자식노드 (left-Rotate시켜주었기 때문)

   -> x가 부모노드 p[x]의 오른쪽 자식일때
     - s를 BLACK으로 p[x]를 RED로 바꿔준다.
     - p[x]를 right-Rotate 시켜준다.
     - x의 새로운 형제노드를 달아준다. (s = p[x]->left) ==> x의 새로운 형제노드는 원래 s의 왼쪽 자식노드 (left-Rotate시켜주었기 때문)

   아직 double-black이 남았기 때문에 case 2/3/4를 진행한다.
 🔴 case 2 :s가 BLACK, s의 자식들도 BLACK일때 ➡
     - x의 double-blackd을 지우고 s를 RED로 바꾼다.
     - p[x]를 x로 해서 계속 한다.
     - 만약, case 1을 거치고 case 2로 왔다면, p[x]는 red였기때문에 종료된다. ( => s의 자식들이 모두 black인 채로 있기 때문에 black-height는 유지)
 🔴 case 3 : s는 BLACK, s의 왼쪽 자식이 RED, 오른쪽 자식이 BLACK 인 경우 ➡

    -> x가 부모노드 p[x]의 왼쪽 자식일때
     - s를 RED, s의 왼쪽 자식을 BLACK으로 바꿔준다.
     - s를 중심으로 right-Rotate 시켜준다.
     - x의 새로운 형제노드를 달아준다. ( s = p[x]->right)

    -> x가 부모노드 p[x]의 오른쪽 자식일때
     - s를 RED, s의 왼쪽 자식을 BLACK으로 바꿔준다.
     - s를 중심으로 left-Rotate 시켜준다.
     - x의 새로운 형제노드를 달아준다. ( s = p[x]->left)

     case 3의 경우는 위의 과정을 끝내고 case 4를 이어서 수행한다.
 🔴 case 4 : s는 BLACK, s의 오른쪽 자식이 RED인 경우 ➡

   -> x가 부모노드 p[x]의 왼쪽 자식일때
     - s의 색을 p[x]의 색으로 바꿔준다.
     - p[x]의 색을 BLACK, s의 오른쪽 자식을 BLACK으로 바꿔준다.
     - p[x]에 대해서 left-rotate를 시켜준다.
     - x의 double-black을 제거하고 종료한다.

   -> x가 부모노드 p[x]의 오른쪽 자식일때
     - s의 색을 p[x]의 색으로 바꿔준다.
     - p[x]의 색을 BLACK, s의 왼쪽 자식을 BLACK으로 바꿔준다.
     - p[x]에 대해서 right-rotate를 시켜준다.
     - x의 double-black을 제거하고 종료한다.

 x가 root이거나 double black이 깨질때까지 반복해준 후, x를 black으로 바꿔준다.



◾ Search (탐색)

Red Black Tree는 BST의 일종이기 때문에 탐색의 밥법은 일반적인 Bianry Tree의 탐색 방법과 다르지 않다.

찾는 값이 해당 노드보다 작다면 왼쪽으로 크다면 오른쪽으로 내려가며 값을 탐색



아래에서 그림을 통해 동작하는 원리를 한번 살펴보자.


1. 삽입

📌 case 1 : z 삼촌이 레드 ➡ 색상 변환 ( Recoloring )

아래와 같은 트리에 5를 추가한다고 하자. 그러면 오른쪽 같이 될 것이다. i1

이는 leafnode부터 루트까지 black-height는 모두 동일 하나 double-red로 규칙에 위배가 된다. recoloring을 통해 색깔을 바꾸어 규칙을 만족시켜주어야 한다.


i3

Recoloring을 통해 부모와 삼촌을 블랙으로 바꾸고 할아버지 노드를 레드로 바꾸고 할아버지를 z로 두고 루트이거나, case1조건을 위배 안 할때 까지 반복해주면 된다.

만일 root에 도달했다면, 빨간색으로 바뀐 루트블랙으로 바꿔주면 이중 red는 해결이 된다. i4 결국, 한 level이 red에서 black이 되었으므로, black-height는 1이 증가하게 된다.



📌 case 2 : z의 삼촌이 블랙 ➡ 회전 ( rotation , restructuring)

i2

위 와 같은 트리에서 5를 삽입하려 할 때 삼촌이 블랙이면 (없어도 leafnode는 black) case1과 같이 recoloring은 black-height가 깨지기 때문에 다른 방법을 이용해야 한다. (recoloring시 왼쪽은 black-height가 2, 오른쪽은 black-height가 1)

이 때는, AVL Tree에서 썼던 rotate개념을 이용하여 트리의 구조를 바꿔 줌으로써, recoloring을 수행하여 double-red를 해결한다.

AVL-Tree와 같이 삽입한 노드 z가 왼쪽에 있냐, 오른쪽에 있냐에 따라 경우가 나뉘며, 왼쪽과, 오른쪽에 있는 방법은 서로 대칭이다.


◾ L : 부모노드가 할아버지 노드의 왼쪽 노드일때

  • case 2-1 : z가 부모노드의 오른쪽 자식

부모노드를 중심으로 왼쪽으로 회전시키고, 여전히 RBT특성을 위반하므로 case2- 2를 수행한다. i2-1

Case2는 삽입할 노드의 부모 노드는 자식을 2개를 갖고 있을 수 없기 때문에, rotate시에 문제없이 10이 부모 노드가 되면서 왼쪽자식으로 부모노드가 올 수 있다.

삼촌이 블랙이면, 무조건 부모는 red이어야 한다.(black-height를 만족시키기 위해)
그때, 자식을 삽입시에 아래와 같은 case로 restructing이 일어나기 때문에 새로운 노드 삽입 시 case2의 경우에는 무조건 부모 노드는 하나의 자식을 갖는다.

이중 레드에, black-height가 여전히 다르고 현재 상태가 case2와 동일 하기 때문에 case2를 진행 하면 된다.


  • case 2-2 : z가 부모노드의 왼쪽 자식

할아버지를 중심으로 오른쪽 회전시키고 i2

부모 노드는 블랙으로, 할아버지 노드는 레드로 서로 색상을 바꾼다. i3 이렇게 되면, 삽입한 z부터 할아버지 노드까지는 규칙에 위배되지 않으니, 할아버지 노드를 기준으로 다시 case에 위배 되지 않는지 검사하면서 root까지 검사하여 balancing을 해주면 된다.


◾ R : 부모노드가 할아버지 노드의 오른쪽 노드일때

이 경우는 부모 노드가 할아버지 노드의 왼쪽 자식인 경우와 대칭으로 rotate 방향만 바꿔주면 방법은 동일하다.

  • case 2-1 : z가 부모노드의 왼쪽 자식

i4 부모노드를 중심으로 right-rotate시키고, 여전히 RBT특성을 위반하고 case 2-2 와 모양이 같기 때문에 부모노드를 z로 기준으로 2-2를 수행한다,

  • case 2-2 : z가 부모노드의 오른쪽 자식

i4 할아버지 노드를 중심으로 왼쪽 회전시키고, 부모와 할아버지의 색상을 바꾼다.

z를 할아버지 노드로 바꿔주고 할아버지의 부모가 Red가 아닐 때까지 위의 case를 반복해준다. 만일 z가 root이라면 root를 black으로 바꾸고 종료한다.

결과적으로 black-height가 증가한다.



2. 삭제

📌 case default : 무조건 실행하는 케이스

삭제할 노드를 z라 할 때, z가 RED라면 그냥 삭제하고, BLACK이라면, 그 자리를 대체하는 노드를 검은색으로 칠한다. 새로 대체하는 노드가 red인경우 black으로 바꿔 주면, 문제가 해결 되지만, 새로 대체하는 노드가 black인 경우 이중 black이 되는 경우로 이를 이중 흑색 노드라고 부르고 아래의 case에 따라 balancing을 해결하면 된다.

깨진 이중 흑색 노드는 black-height를 맞추기 위해 한 노드가 black색을 두개 가지고 있는 노드로 결국 black-height규칙이 깨졌다는 소리이므로 fix-up을 해주어야 한다.

삭제한 노드 z대신 새로 위치한 노드를 x, 그 형제 노드를 s라고 하자.


📌 case 1 : s가 RED인 경우

이때는 s의 자식들은 leafNode 일 수 없다. 조건 5를 위반하기 때문에 한개라도 leafnode이면 black-height가 달라지므로 무조건 두개를 가지고 있다.

◾ L : x가 부모 노드 p[x]의 왼쪽 자식일때

d1

위 트리에서 5를 삭제하려고 한다면, 대체되는 노드 x는 leafnode가 대체되며, 이중 흑색 노드가 되어 black-height가 깨지기 때문에 rotate와 recoloring을 통해 규칙을 바로잡아주어야 한다.


d1-2 s를 BLACK으로 부모를 RED로 바꿔주고 부모기준으로 left-Rotate 시켜준다. rotate시켜줌으로써, x(leafnode)의 형제 노드s가 red(20)에서, black(15)로 바뀌었다.

d1-3 그래도 여전히 이중 흑색 노드를 갖고 있기 때문에, 다른 case들을 수행해주어야 한다.


◾ R : x가 부모 노드 p[x]의 오른쪽 자식일때

d1-4 40을 삭제한다고 한다면, null이 x, 10이 s가 되고 x는 이중 흑색 노드가 되므로 rebalancing을 해주어야 한다.

d1-5 s를 BLACK으로 p[x]를 RED로 바꿔준 후 px를 right-Rotate 시켜준다. 아직 이중 흑색 노드가 남았기 때문에 다른 case를 진행한다.



📌 case 2 : s가 BLACK, s의 자식들도 BLACK일때

d2 case1을 거치고 온 경우도 이에 속하며, 이중 흑색 노드가 존재하기 때문에 recoloring을 통해 balancing을 해주어야 한다.


d2-1 x의 double-black을 지우고 s를 RED로 바꾼후

d2-2

부모를 black으로 칠해준다. 만약, case 1을 거치고 case 2로 왔다면, p[x]는 red였기 때문에 종료되고, x의 부모 노드가 black이라면 다시 이중 흑색 노드가 생기기 때문에 부모를 기준으로 다시 다른 case를 수행해준다



📌 case 3

◾ L : x가 부모 노드 p[x]의 왼쪽 자식일때 x가 부모 노드 p[x]의 왼쪽 자식일때, s는 BLACK, s의 왼쪽 자식이 RED, 오른쪽 자식이 BLACK 인 경우

d3 case2와 같은 방법으로 s(15)를 red로 부모(10)를 black으로 바꿔줄 경우 double-red가 되므로 recoloring을 할 수 없다. 그래서 rotate를 하여 구조를 바꿔준 후 recoloring을 수행해야한다.


d3-1 s를 중심으로 right-Rotate 시켜준 후, s와 s의 왼쪽 자식의 색을 바꿔준다. 그러면, s는 15(black)에서 12(black)으로 바뀌고 s의 자식은 오른쪽으로 이동하게 되는 것을 볼 수 있다.

여전히, 이중 흑색 노드는 존재하므로 다른 case를 반복 수행하는 데, case3을 마치고 나면 case4의 모양이 되기 때문에, 바로 case4를 수행한다.


◾ R : x가 부모 노드 p[x]의 왼쪽 자식일때 x가 부모 노드 p[x]의 오른쪽 자식일때, s는 BLACK, s의 오른쪽 자식이 RED, 왼쪽 자식이 BLACK 인 경우

d3-2 case 3-L의 대칭으로 똑같이 rotate를 하여 구조를 바꿔준 후 recoloring을 수행해야한다.


d3-3 s(25)를 중심으로 left-Rotate 시켜준 후, s와 s(28)의 오른쪽 자식의 색을 바꿔준다. 그러면, s는 25(black)에서 28(black)으로 바뀌고 s의 자식은 왼쪽으로 이동하게 되는 것을 볼 수 있다.

이경우에도, 여전히 이중 흑색 노드는 존재하므로 다른 case를 반복 수행하는 데, case3을 마치고 나면 case4의 모양이 되기 때문에, 바로 case4를 수행한다.



📌 case 4

◾ L : x가 부모 노드 p[x]의 왼쪽 자식일 때 s는 BLACK, s의 오른쪽 자식이 RED인 경우

d4 s의 색을 부모의 색으로 부모의 색을 BLACK, s의 오른쪽 자식을 BLACK으로 바꿔준다. Recoloring을 해주면 black-height가 여전히 깨져있기 때문에, rotate를 시켜줘야 한다.


d4-1 p[x]에 대해서 left-rotate를 시켜주고 x의 double-black을 제거해주면, 모든 규칙이 성립하게 되어 끝난다.


◾ R : x가 부모 노드 p[x]의 오른쪽 자식일 때 s는 BLACK, s의 왼쪽 자식이 RED인 경우

d4-2 이는 4-L의 대칭으로 s의 색을 p[x]의 색으로 p[x]의 색을 BLACK, s의 왼쪽 자식을 BLACK으로 바꿔준다.


d4-3 부모에 대해서 right-rotate를 시켜주고 x의 double-black을 제거해주면, 모든 규칙이 성립하게 되어 끝난다.



추가)

구현시에 leafnodeblack임을 명시해주기 위해 비어 있는 자식 포인터에 color를 black으로 초기화한 leafnode를 가리켜야 구현이 수월한데, 새 노드를 삽입할 때 마다 leafnode를 생성해서 붙여주는 것은 메모리적으로 봐도 매우 비효율적이고, leafnode인지 확인하기 위해 ‘==’ 연산을 수행해도 메모리주소가 다르기 때문에 leafnode가 아니라고 할 수 있다.

그래서, 모든 leafnode들을 가리키는 포인터는 하나의 leafnode를 가리키게 함으로써, 메모리 절약과, 연산의 효율을 더하는 방법으로 구현을 하면 수월하다.

leaf




구현 코드

github에서 보기

📃 구현 코드 (c++) ( 접기 / 펼치기 )
/*
* C++ 이용하여 Red Black Tree 구현하기
*
* 목적 : Red Black Tree 공부 하기 위해 작성했으며,
*       C++ 이용하여 작성하시는 분들에게 도움이 되고자 했다.
*
* 설명 : key 값은 int만 가능 하며 중복 key는 허용 x
*       이중 연결 리스트로 구현
*       Red / Black은 식별하기 쉽게 enum이용 했으며, bool 이용시 데이터 크기 절약
*
*       class RBTree
*
*       변수 :   root node => root노드는 항상 black
*               leaf node => 끝에 해당하는 노드들은 leaf node들을 가지고 있다.
*                            leaf node라는 것만 알면 되기 때문에 새로운 노드 삽입 때마다 leaf node를 생성 해줄 필요없이
*                            모든 말단 노드들은 이 leaf node를 가리키는 식으로 구현
*                            leaf node는 항상 black
*
*       생성자 : RBTREE =>  node 구조체 생성후
*                          색은 black 초기화
*                          모든 자식은 nullptr로 초기화.
*
*       함수 :   IsKey => key값이 있는지 검사하는 함수
*               Insert => 삽입 함수
*               InsertFixUp => 삽입 후 규칙 깨졌을 시 재조정 함수
*               Delete => 삭제 함수
*               DeleteFixUp => 삭제 후 규칙 깨졌을 시 재조정 함수
*               Transplant => 삭제 시 이용하며, 삭제할 노드의 자식 노드를 부모노드에 연결해주는 함수
*               RotateRight(x) => x기준 오른쪽으로 회전
*               RotateLeft(x) => x기준 왼쪽으로 회전
*
*               Inorder,Preorder,Postorder => 순회 함수
*               tree_minimum(x), tree_maximum(x) => 노드 x 기준으로 가장 왼쪽, 오른쪽 return 함수
*
*               DisplayMenu, SelectMenu => 초기 Menu판 print 함수
*               Insert_helper,Delete_helper,order_helper,print_helper => 각각 수행시 입력받고 조건 에러 처리 위한 함수 와 tree print 해주는 함수
*
* 작성자 : gowoonsori
* github : https://github.com/gowoonsori/my-tech/tree/master/dataStructure/Tree
* 해당 source gist : https://gist.github.com/gowoonsori/a725e29ef1880f0592fe5760f4908c6b
*/

#include <iostream>

enum Color {
    RED,
    BLACK
};
struct node {
    int key;
    node *left = nullptr;
    node *right = nullptr;
    node *parent = nullptr;
    Color color = BLACK;
};

typedef node *NodePtr;

class RBTREE {
   private:
    NodePtr root;      //루트 노드
    NodePtr leafNode;  //단말노드

    //key값이 있는지 없는지 검사 있으면 pointer 값, 없으면 nullptr
    NodePtr IsKey(int item) {
        NodePtr t = root;
        NodePtr parent = NULL;

        /*key값을 찾거나 없다면 break*/
        while (t != NULL && t->key != item) {
            parent = t;
            t = (item < parent->key) ? parent->left : parent->right;
        }
        return t;
    }

    void Insert(int item) {
        // x : 삽입할 곳 찾기위한 포인터 | y : 삽입할 곳의 부모노드
        NodePtr x = this->root, y = nullptr;
        NodePtr z = new node();
        z->key = item;
        z->color = RED;
        z->parent = nullptr;
        z->left = leafNode;
        z->right = leafNode;

        /*BST의 일반 삽입 연산*/
        while (x != leafNode) {
            y = x;
            if (x->key < item)
                x = x->right;
            else
                x = x->left;
        }

        z->parent = y;

        if (y == nullptr)
            root = z;
        else if (z->key > y->key)
            y->right = z;
        else
            y->left = z;

        //z가 root노드라면
        if (z->parent == nullptr) {
            z->color = BLACK;
            return;
        }
        // z의 부모노드가 root노드라면 Fix Up 필요없이 red컬러로 붙여주면 된다.
        if (z->parent->parent == nullptr) {
            return;
        }
        InsertFixUp(z);

        return;
    }

    void InsertFixUp(NodePtr z) {
        /*root 노드가 아니고 부모 색이 red라면*/
        while (z != root && z->parent->color == RED) {
            NodePtr grandparent = z->parent->parent;
            NodePtr uncle = (z->parent == grandparent->left) ? grandparent->right : grandparent->left;
            bool side = (z->parent == grandparent->left) ? true : false;  //if p[z]가 p[p[z]]의 왼쪽 자식이면 1 / 오른쪽이면 0

            /*case 1*/
            if (uncle && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                z = grandparent;
            }

            /*case 2
                side == true ) p[z]는 p[p[z]]의 왼쪽 자식 인 경우이다.
                side == false ) p[z]는 p[p[z]]의 오른쪽 자식 인 경우이다. */
            else {
                /*case 2-1*/
                if (z == (side ? z->parent->right : z->parent->left)) {
                    z = z->parent;
                    side ? RotateLeft(z) : RotateRight(z);
                }
                /*case 2-2*/
                z->parent->color = BLACK;
                grandparent->color = RED;
                side ? RotateRight(grandparent) : RotateLeft(grandparent);
            }
        }
        root->color = BLACK;
    }

    bool Delete(int item) {
        NodePtr z = IsKey(item);
        if (!z)
            return false;
        else {
            NodePtr x, y;
            Color OriginalColor = z->color;

            /*자식이 없거나 1개인 경우
                    삭제할 노드(z)가 블랙이면 doulbe red이므로 fix*/
            if (z->left == leafNode) {
                x = z->right;
                Transplant(z, z->right);
            } else if (z->right == leafNode) {
                x = z->left;
                Transplant(z, z->left);
            } else {
                y = tree_minimum(z->right);
                OriginalColor = y->color;
                x = y->right;  //y의 왼쪽 자식은 없다.

                if (y->parent == z) {  //z의 오른쪽 자식이 가장 작은 key
                    x->parent = y;     // x가 leafnode일 때, fix하게 될 때 사용
                } else {
                    Transplant(y, y->right);
                    y->right = z->right;
                    y->right->parent = y;
                }
                Transplant(z, y);
                y->left = z->left;
                y->left->parent = y;
                y->color = z->color;
            }
            delete z;
            if (OriginalColor == BLACK) {
                DelteFixUp(x);
            }
        }
        return true;
    }

    void DelteFixUp(NodePtr x) {
        NodePtr s;  //형제노드 s

        //root이거나 double black 이 깨질때 까지
        while (x != root && x->color == BLACK) {
            /* x가 p[x]의 왼쪽자식인 경우 */
            if (x == x->parent->left) {
                s = x->parent->right;
                // case 1
                if (s->color == RED) {
                    s->color = BLACK;
                    x->parent->color = RED;
                    RotateLeft(x->parent);
                    s = x->parent->right;
                }

                // case 2
                if (s->left->color == BLACK && s->right->color == BLACK) {
                    s->color = RED;
                    x = x->parent;
                } else {
                    // case 3
                    if (s->right->color == BLACK) {
                        s->left->color = BLACK;
                        s->color = RED;
                        RotateRight(s);
                        s = x->parent->right;
                    }

                    // case 4
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->right->color = BLACK;
                    RotateLeft(x->parent);
                    x = root;
                }
            }

            /*x가 p[x]의 오른쪽 자식인 경우*/
            else {
                s = x->parent->left;
                // case 1
                if (s->color == RED) {
                    s->color = BLACK;
                    x->parent->color = RED;
                    RotateRight(x->parent);
                    s = x->parent->left;
                }

                // case 2
                if (s->left->color == BLACK && s->right->color == BLACK) {
                    s->color = RED;
                    x = x->parent;
                } else {
                    // case 3
                    if (s->left->color == BLACK) {
                        s->right->color = BLACK;
                        s->color = RED;
                        RotateLeft(s);
                        s = x->parent->left;
                    }
                    // case 4
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->left->color = BLACK;
                    RotateRight(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
        root->color = BLACK;
    }

    /* u의 위치에 v를 이식 */
    void Transplant(NodePtr u, NodePtr v) {
        if (u->parent == nullptr)
            root = v;
        else if (u == u->parent->left)
            u->parent->left = v;
        else
            u->parent->right = v;

        v->parent = u->parent;
    }
    /*x를 중심으로 왼쪽으로 회전*/
    void RotateLeft(NodePtr x) {
        NodePtr y;

        y = x->right;
        x->right = y->left;
        if (y->left != leafNode) {
            y->left->parent = x;
        }
        y->parent = x->parent;

        if (!x->parent) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        x->parent = y;
        y->left = x;
    }
    /*x를 중심으로 오른쪽으로 회전*/
    void RotateRight(NodePtr y) {
        NodePtr x;

        x = y->left;
        y->left = x->right;
        if (x->right != leafNode) {
            x->right->parent = y;
        }
        x->parent = y->parent;

        if (!y->parent) {
            root = x;
        } else if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
        y->parent = x;
        x->right = y;
    }

    /*show tree*/
    void print_helper(NodePtr root, std::string indent, bool last) {
        // print the tree structure on the screen
        if (root != leafNode) {
            std::cout << indent;
            if (last) {
                std::cout << "R----";
                indent += "     ";
            } else {
                std::cout << "L----";
                indent += "|    ";
            }

            std::string sColor = (root->color == RED) ? "RED" : "BLACK";
            std::cout << root->key << "(" << sColor << ")" << std::endl;
            print_helper(root->left, indent, false);
            print_helper(root->right, indent, true);
        }
    }

    /*중위순회*/
    void Inorder(NodePtr target) {
        if (target == leafNode)
            return;
        Inorder(target->left);
        std::cout << target->key << " ";
        Inorder(target->right);
    }
    /*후위순회*/
    void Postorder(NodePtr target) {
        if (target == leafNode)
            return;
        Postorder(target->left);
        Postorder(target->right);
        std::cout << target->key << " ";
    }
    /*전위순회*/
    void Preorder(NodePtr target) {
        if (target == leafNode)
            return;
        std::cout << target->key << " ";
        Preorder(target->left);
        Preorder(target->right);
    }

   public:
    RBTREE() {
        leafNode = new node;
        leafNode->color = BLACK;
        leafNode->left = nullptr;
        leafNode->right = nullptr;
        leafNode->parent = nullptr;
        root = leafNode;
    }
    //최솟값 찾기
    NodePtr tree_minimum(NodePtr x) {
        while (x->left != leafNode) {
            x = x->left;
        }
        return x;
    }
    //최댓값 찾기
    NodePtr tree_maximum(NodePtr x) {
        while (x->right != leafNode) {
            x = x->right;
        }
        return x;
    }

    void DisplayMenuBoard() {
        std::cout << "      ** Red Black Tree **  " << std::endl;
        std::cout << "                            " << std::endl;
        std::cout << "              Menu          " << std::endl;
        std::cout << "          1. Insert Key     " << std::endl;
        std::cout << "          2. Delete Key     " << std::endl;
        std::cout << "          3. Show Tree      " << std::endl;
        std::cout << "          4. choose order   " << std::endl;
        std::cout << "          5. show Menu      " << std::endl;
        std::cout << "          6. clear Display  " << std::endl;
        std::cout << "          7. exit           " << std::endl;
        std::cout << std::endl;
    }
    void SelectMenu() {
        DisplayMenuBoard();
        int i = -1;

        while (i != 8) {
            std::cout << "--> select   :   ";
            std::cin >> i;
            switch (i) {
                case 1:
                    Insert_helper();
                    break;
                case 2:
                    Delete_helper();
                    break;
                case 3:
                    print_helper(root, "", true);
                    break;
                case 4:
                    Order_helper();
                    break;
                case 5:
                    DisplayMenuBoard();
                    break;
                case 6:
                    system("cls");
                    DisplayMenuBoard();
                    break;
                case 7:
                    return;
                default:
                    std::cout << " !!! Wrong entered !!!\n"
                              << std::endl;
            }
        }
    }

    void Insert_helper() {
        int item;
        std::cout << "Key to insert  :  ";
        std::cin >> item;
        if (IsKey(item)) {
            std::cout << "!!! " << item << " is already exists !!!\n";
            return;
        }
        Insert(item);
    }
    void Delete_helper() {
        int item;
        std::cout << "Key to delete  :  ";
        std::cin >> item;
        if (!Delete(item)) {
            std::cout << "!!! " << item << " is not exists !!!\n";
            return;
        }
        return;
    }
    void Order_helper() {
        int i;
        std::cout << "         == Order Menu ==" << std::endl;
        std::cout << "          1. PreOrder" << std::endl;
        std::cout << "          2. InOrder" << std::endl;
        std::cout << "          3. PostOrder" << std::endl;
        std::cout << "          4. exit" << std::endl;
        std::cout << " --> select  :  ";

        std::cin >> i;
        switch (i) {
            case 1:
                Preorder(this->root);
                std::cout << std::endl;
                break;
            case 2:
                Inorder(this->root);
                std::cout << std::endl;
                break;
            case 3:
                Postorder(this->root);
                std::cout << std::endl;
                break;
            case 4:
                return;
            default:
                std::cout << " !!! Wrong enter !!!\n"
                          << std::endl;
                break;
        }
        return;
    }
};

int main() {
    RBTREE tree;
    tree.SelectMenu();

    return 0;
}