[Algorithm] Red Black Tree(미완성…)

★Red Black Tree란 이진 탐색 트리의 치우침 문제(?)를 해결하기 위해 insert와 delete의 알고리즘을 수정한 이진 탐색 트리의 일종이다. 레드 블랙 트리는 어느정도 균형이 잡혀있는데, 여기서 균형이 잡혀있다는 말은 자료가 한쪽으로 쏠리지 않도록 어느 깊이의 노드가 꽉 찰 때까지 다음 깊이로 내려가지 않는다는 의미이다. 그래서 치우침이 없고, 탐색 연산의 시간 복잡도는 O(log n)임이 유지된다.

★각 노드는 키, 왼쪽 자식, 오른쪽 자식, 부모 노드의 주소를 저장한다.

★자식노드가 null일 경우 NIL노드라는 특수한 노드가 있다고 가정한다.(설명의 편의를 위한 노드이므로 코딩할 때 구현하지 않아도 됨)

★따라서 모든 리프 노드는 NIL노드이다. 데이터를 갖고있으면 리프 노드가 아니라는 의미. 모든 노드는 부모의 주소도 갖고있으므로 루트의 부모도 NIL 노드라고 가정한다.

★노드들은 내부노드(데이터를 갖고있는 노드)와 NIL노드로 분류한다.

★Red Black Tree의 조건

1. 모든 노드는 red 혹은 black이다.
2. 루트 노드의 색은 Black.
3. 모든 리프 노드(NIL 노드)는 Black.
4. Red 노드가 연속으로 나올 수 없다(No Double Red). 따라서 red의 자식은 항상 black이다.
5. 모든 리프 노드의 Black Depth는 같다. 즉 어떤 노드에서 리프까지의 경로에서 Black 노드의 수는 같다.

★4번 조건에 의해 리프에서 루트까지 Black Depth는 일치해야 한다. 따라서 가장 짧은 경로를 가진 노드나 가장 긴 경로를 가진 노드의 Black Depth는 일치한다. 가장 짧은 경로의 경우는 결국 Black Node만으로 구성된 경로이고, 가장 긴 경로는 모든 Black Node의 사이사이에 Red Node가 하나씩 있는 경우인데, 둘의 차이는 길어도 2배가 채 안된다. 그래서 이진 탐색 트리보다 훨씬 균형잡힌 트리가 되는 것이다.

★노드의 높이(height) : 해당 노드에서 NIL노드까지 가는 경로중 가장 긴 경로에 포함된 에지의 갯수이다.

★노드의 블랙 높이(Black Height) : 해당 노드에서 NIL노드까지 가는 가장 긴 경로에 포함된 Black 노드의 갯수이다. 이 때 자신은 갯수에 포함하지 않는다.

★높이가 h인 노드의 블랙 높이(bh)는 bh >= h/2이다. 조건 4에 의해 red노드는 연속될 수 없기 때문.

★노드 x를 루트로 하는 부분 트리는 적어도 2^bh(x) - 1개의 내부 노드를 포함한다.

★n개의 내부 노드를 가지는 레드 블랙 트리의 높이는 2log(n+1) 이하이다. n >= 2^bh - 1 >= 2^(h/2) - 12. 즉 5개의 조건만 만족한다면 트리의 높이는 자동으로 O(log n)이 된다.

★탐색 알고리즘 : 이진 탐색 트리와 같다.

★Left/Right Rotation : 서브트리를 서브 트리의 루트를 기준으로 왼쪽 또는 오른쪽으로 회전하는 것. 자세한 원리는 그림을 찾아보자. 이진 탐색 트리에서 Left/Right Rotation을 실행하더라도 여전히 이진 탐색 트리임이 유지된다. 단 레드 블랙 트리임이 항상 유지되는 것은 아니다. 이 연산의 시간 복잡도는 O(1이다)

★삽입 알고리즘 : 일단 이진 탐색 트리와 같은 알고리즘으로 삽입한다. 단 새로 삽입 된 노드는 모두 red노드가 된다(루트라면 black으로 바꾼다). 때문에 자료를 넣다보면 레드 블랙 트리의 조건을 언젠가 반드시 위반하게 된다. 그래서 추가적인 작업을 해 줘야 한다. 삽입으로 인해 위반될 수 있는 조건은 2개가 있다. 2번 조건은 새로 입력된 노드(z)가 루트라면 위반되고, 아니면 위반되지 않는다. 이 때는 간단히 색깔만 바꿔주면 된다(Red -> Black). 4번 조건은 z의 부모인 p[z]가 red면 위반 된다(Double Red Violation).

★Double Red를 해결하기 위해 조건에 따라 두 가지 전략을 사용한다.

1. 현재 삽입된 노드의 삼촌 노드(부모의 형제 노드)가 Black일 때 : Restructuring
2. 삼촌 노드가 Red일 때 : Recoloring

★Restructuring : 삽입된 노드 z가 부모의 오른쪽 자식인 경우 부모 노드를 기준으로 Left Rotation한다. 원래 z의 부모였던 노드를 새로운 z로 삼으면 z는 부모의 왼쪽 자식이 된다. 그런 다음 조부모 노드를 기준으로 Right Rotation을 수행한 후 z의 부모 노드와 삼촌 노드의 색을 교환한다. 이 연산은 다른 서브트리에 영향을 주지 않으며, 연산 전후의 Black Depth의 변화가 없고, 한번의 수행으로 끝난다. Restructuring의 시간복잡도는 O(1)이지만, 기본적으로 삽입연산 후에 일어나므로 O(log n)가 총 수행시간이다.

★Recoloring : z의 부모와 삼촌노드를 Black으로, 조부모를 Red로 한다. 조부모가 루트 노드가 아니면 Double Red가 다시 발생할 수 있다(루트 노드일 경우는 black으로 칠하면 2번 조건에 위배되지 않으므로 문제 없음). Double Red가 발생했다면 그 지점에서 다시 삼촌 노드를 확인해 Restructuring이나 Recoloring을 수행한다. 연산의 시간 복잡도 자체에는 (1)이 걸린다. 그러나 최악의 경우 Root로 갈때까지 계속 발생할 수 있으므로 O(log n)의 시간이 걸린다. 삽입시간까지 합쳐 총 O(log n)의 시간 복잡도를 갖는다.

★실제로 코딩할 때는 6가지 경우의 수를 갖는다.

1. 부모가 조부모의 왼쪽 자식이고 삼촌이 red일 때
2. 부모가 조부모의 왼쪽 자식이고 삼촌은 black이고 z는 부모의 오른쪽 자식일 때
3. 부모가 조부모의 왼쪽 자식이고 삼촌은 black이고 z는 부모의 왼쪽 자식일 때
4. 부모가 조부모의 오른쪽 자식이고 삼촌이 red일 때
5. 부모가 조부모의 오른쪽 자식이고 삼촌은 black이고 z는 부모의 오른쪽 자식일 때
6. 부모가 조부모의 오른쪽 자식이고 삼촌은 black이고 z는 부모의 왼쪽 자식일 때

★1, 2, 3과 4, 5, 6은 좌우 대칭이다.

★결국 삽입하는 경우에 O(log n)이라는 결론이 나온다.

★삭제 알고리즘 : 기본적인 이진 탐색 트리의 삭제 알고리즘을 먼저 수행한다. 삭제 노드를 대체 노드가 대체했을 때 삭제 노드의 키 값만 대체되고 색은 변하지 않으며 실제로는 대체 노드가 삭제된다. 이 때 대체 노드가 red라면 double red가 발생할 가능성이 없으므로 추가적인 작업이 필요하지 않다. 따라서 추가적인 작업이 필요한 경우는 삭제된 대체 노드가 black인 경우이다. 삭제 알고리즘이 수행되면 대체 노드의 하나뿐인 자식 노드를 black으로 칠하면 문제가 해결되지만 이 자식놈이 원래부터 black이었다면(즉 사라진 대체 노드와 그의 자식이 둘다 black인 경우다) 자식 노드는 double black 노드가 되어 문제가 발생한다. 이 double black을 해결하기 위해 경우에 따라 다음 전략을 따른다.

★관계가 복잡하므로 용어 정리를 하고 넘어간다.

1. x : double black이 된 대체 노드의 자식 노드. 대체 노드가 자식이 없다면 NIL이므로 코딩할 때 조심해야 한다.
2. w : x의 형제 노드. NIL일 수 없다. w가 삭제 알고리즘 시작 전부터 이미 5번 조건에 위반된 상태이다.

★DELETE FIX

1. w가 red인 경우 : 이 경우 w의 자식들은 모두 black이다. w를 black으로, x의 부모 노드를 red로 칠한 후 x의 부모 노드에 대해 left rotate하고, x의 새로 생긴 형제를 새로운 w로 한다. 이렇게 하면 이 새로운 w가 반드시 black이 되는데, 아직 double black이 해소되지 않았으므로 경우2~4로 넘어간다.
2. w와 그 자식이 모두 black인 경우 : 이 경우는 x의 부모 노드는 black일 수도, red일 수도 있는 gray상태이다. w를 red로 하고, x의 black 하나를 부모에게 전달한다. 이 때 x의 부모 노드가 black이었다면 double black이 또 발생하는데, x의 부모를 새로운 x로 하고, 삽입의 recoloring연산처럼 root에 도달해 끝날 때 까지 반복한다. 경우 1에서 2로 넘어온 경우에는 x의 부모 노드가 항상 red이므로 한번의 작업으로 끝나게 되지만 바로 경우 2로 넘어온 경우에는 gray이므로 루프를 돌게 될 수 있다.
3. w가 black, w.left가 red, right가 black인 경우 : w를 red로, w.left를 black으로 한 후 w에 대해 right rotate한다. 이러면 double black노드의 새로운 형제(새로운 w)의 right는 red가 되어 경우 4로 넘어간다.
4. w가 black, w.right가 red인 경우 : x의 부모노드의 색을 w로 넘긴다. 부모노드와 w.right를 검은색으로 칠한 후 부모노드에 대해 left rotate한다. 이후 x의 black 하나를 그냥 제거하고 종료. 경우 4를 만나면 DELETE FIX가 바로 종료된다.

★실제로 코딩할 때는 삽입 알고리즘 처럼 4가지 경우의 수는 x가 부모의 left인 경우와 right인 경우로 나뉘어 총 8가지 경우의 수를 갖게 된다. 위의 1~4는 x가 left인 경우이다.

★삭제 알고리즘의 시간 복잡도 : 이진 탐색 트리의 삭제연산 O(log n) + delete fix작업의 최악의 경우(2번 루프가 최대한 반복되는 경우) O(log n) = O(log n)

★이 Red Black Tree를 직접 구현해 보자.

조따복잡하네다음에구현해보자.