Red-Black Tree

Red - black tree (자가 균형 이진 탐색 트리)

red - black tree는 이진 탐색 트리를 기반으로 하고, 기존 이진 탐색 트리에서의 Worst case를 보완한 트리.

Node들은 값이 외에도 color값을 가지게 된다. (black or red)

Red - Black Tree는 아래의 규칙을 따라야 한다.

1. Root property : 루트 노드의 색깔은 항상 검정(black)이다.
2. External Property : 모든 리프(NIL)들은 검정(black)이다.
3. Internal Property : 빨강 노드의 자식은 항상 검정이다 == 빨강색 노드가 연속될 수 없다.
4. Depth Property. : 모든 리프노드에서 black depth는 같다. == 리프노드에서 루트노드까지 가는 모든 경로에서, 만나는 블랙 노드의 개수는 같다.

삽입 , insert

*새로 삽입된 노드는 항상 빨강색이다.

새로 삽입된 노드의 부모가 검정색이면 상관이 없지만, 삽입된 노드의 부모가 빨강색이면 빨간 노드의 자식으로 빨간 노드가 들어가기 때문에 규칙 3(internal property)를 위반하게 된다. double red가 발생하게되면 상황에 맞게 처리해주어야 한다.

case 1. newNode의 삼촌 노드가 빨강색인 경우.

step 1. 우선 double red를 피하기 위해 부모를 검정색으로 칠한다.

step 2. 부모를 검정색으로 칠하게 되면 black depth가 1이 늘어나기 때문에 조부모를 빨강색으로 칠한다.

step 3. 조부모가 빨강색으로 바뀌게 되면서 uncle쪽 black depth가 1 줄었기 때문에 uncle을 빨강으로 칠한다.

이렇게 처리를 하면 조부모가 빨강색이 되면서 또다시 double red가 발생할 수 있다. (기존 조부모가 검정색이었기 때문에 조부모의 부모가 빨강색일 수 있음). 그러면 조부모를 기준으로 다시 double red를 처리한다. double red가 발생 안하거나 root 노드에 도달하면 종료.

case 2. new node의 삼촌노드가 검정색일때.

case 2-1. 본인이 부모의 오른쪽 자식인 경우.

step 1. 부모 기준으로 왼쪽 회전을 시켜준다.

step 2. 회전을시켜주면 case 2-2의 형태를 이루기 때문에 case 2-2의 절차를 진행하면 됨.

case 2-2 본인이 부모의 왼쪽 자식일 때

step 1. 우선 double red를 방지하기 위해 parent를 검정색으로 칠한다.

step 2. parent를 검정색으로 칠하면 black depth가 1 늘어났기 때문에 조부모를 red로 칠한다.

step 3. 조부모를 기준으로 오른쪽 회전을 한다.

case 1에서는 uncle이 red여서 부족한 black1개를 uncle을 검정색으로 칠함으로 처리가 가능했지만 지금같은경우에는 uncle이 이미 black이기 때문에 다른 방법으로 black 1개를 추가해줘야 한다. 그 방법이 오른쪽 회전.

삭제, erase

삭제된 node가 빨강색일때는 아무런 추가작업이 필요하지 않다. (빨강색이 없어져도 black depth에 영향이 없음)

삭제된 node가 검정색일 때는 black depth가 1개 줄어들기 때문에 상황에 맞게 black을 추가해줘야함.

Default case.

Default case는 삭제된 노드가 검정색일때 무조건 실행하는 동작.

삭제된 노드를 대체하는 노드를 검정색으로 칠한다. 여기서도 문제가 발생할 수 있다.

대체하는 노드가 빨강색이면, 그냥 빨강 → 검정으로 바꿔서 부족한 black depth를 채우면 된다. 하지만 대체하는 노드가 검정이면 다시 검정색을 칠한다고 해도 black depth가 늘어나지 않는다(이미 검정색이었기 때문). 그래서 임시로 대체하는 노드에 검정색을 한 개 더 추가했다고 가정을 하고, 해당 노드를 이중 흑색 노드라고 부르자.

이중 흑색 노드는 임의로 해당 노드에 흑색이 2개가 있다고 가정을 한거지 실제로 흑색이 2개가 있는것은 아니기 때문에 흑색 1개를 적절한 곳에 넘겨줘야 한다. 이를 해결하려면 케이스 별로 처리방식이 다르다.

case 1. 이중 흑색 노드의 형제가 빨강색인 경우.

step 1. 형제를 검정색으로 칠한다.

step 2. 부모를 빨강색으로 칠한다.

step 3. 부모를 기준으로 왼쪽 회전을 실행한다.

step 4. 다음 케이스를 수행한다.

case 2. 이중 흑색 노드의 형제가 검정색이고, 형제의 자식 둘 다 검정색인 경우.

step 1. double black의 black 1개를 부모에게 전달한다.

step 2. 형제 쪽에 black depth가 1 늘어났기 때문에 형제의 색깔을 빨강색으로 칠한다.

step 3. double black을 계속해서 부모에게 넘겨가며 위 동작을 수행하다가, black을 넘겨받은 부모가 빨강색이면, 빨강을 버리고 검정색으로 칠하게 되면 종료. 또는 루트노드까지 올라가게 되면 그대로 종료.

case 3. 이중 흑색 노드의 형제가 검정색이로, 형제의 왼쪽 자식이 빨강색인 경우

step 1. 형제노드를 빨강색으로 칠한다.

step 2. 형제의 왼쪽 자식을 검정색으로 칠한다.

step 3. 형제를 기준으로 오른쪽 회전을 한다.

step 4. case 4를 진행한다.

case 4. 이중 흑색 노드의 형제가 검정이고, 형제의 오른쪽 자식이 빨강색인 경우.

step 1. 부모 노드의 색깔을 형제에게 넘긴다.

step 2. 부모 노드와, 형제의 자식을 검정색으로 칠한다.

step 3. 부모노드를 기준으로 왼쪽 회전을 한다.