알고리즘 ch6 (2) Red-black tree

Binary Search Tree

- Binary Tree + Binary invariant(왼쪽 subtree는 더 작은 값 , 오른쪽 subtree는 더 큰 값)

- 각각의 노드들의 key는 unique하며, 완쪽자식의 key는 부모보다 작으며 오른쪽 자식의 key는 부모보다 큰 값이다.

- complexity    평균    최악

   Insert        O(logn)  O(n)

   Remove     O(logn)  O(n)

   Search       O(logn)  O(n)

  사슬모양처럼 긴 모양을 경우 최악의 경우고, balanced 모양일 경우 평균의 경우다.

- 중회순회(inorder traversal) 시에 오름차순으로 정렬된 key값을 얻을수 있다.

Red Black Tree

- Binary search Tree 이면서 Balanced Tree이다.

- 트리 높이는 log n에 바운드된다. search연산은 O(logn)의 시간복잡도를 가진다.

- Red black tree는 4가지 조건을 만족해야만 한다.

 1) Root property : 루트 노드의 색깔은 검정(black)이다.

 2) External property : 모든 external node(=leaf)들은 검정(black)이다.

 3) Internal property : 빨강(Red)노드의 자식은 검정(black)이다.

 4) Depth property : 모든 리프노드에서의 black depth는 동일하다.

+ black depth : 리프토드에서 루트노드까지 가는경로에서 만나는 black edge의 개수

    root의 black depth = 0

 위 네가지 조건을 통해 red-black tree의 높이가 log n에 바운드 

- Insertion : 삽입되는 노드의 색깔은 무조건 red이다. root&external&depth property를 지키기 위해서이다.

     따라서 이 때 Internal property를 위반할 수 있는데 이는 tree의 구조나 node들의 색을 변경시키는 작업이 필요하다.

=> internal property 위반 : red - red 일경우. 이를 double red 라고 한다.

  Remedying a double red , double red 해결법은 2가지

  -> 부모의 형제노드 즉 uncle node의 색깔에 따라 해결하는 방법이 다르다.

  

  1) Restructuring : uncle node가 black일 때

과정

① 현재 삽입된 노드와 부모노드, 부모의 부모노드를 오름차순으로 정렬한다.

② 가운데 있는 값을 부모로 만들고 크기에 맞게 나머지를 자식으로 배치한다.

③ 부모를 black, 자식을 red로 색깔을 바꾼다.

  2) Recoloring : uncle node가 red일 때

과정

① 현재 삽입된 노드와 부모와 부모의 형제를 black으로 바꾸고, 부모의 부모는 red로 바꾼다.

=> 문제발생 : Restructuring과 다르게 1번으로 끝나지 않을 수 있다.

  부모의 부모가 Root node가 아닐 경우, double red가 발생할 수 있기 때문이다.

  다시 한번 더 restructuring이나 recoloring을 수행해야 될 수도 있다.

  즉, recoloring은 restructuring과 다르게 propagate해서 root node까지 갈지도 모른다.

  Insertion의 시간복잡도

위치 찾는 시간    삽입 시간    double red 해결 시간

  1) Restructuring  =      O(logn)      +    O(1)    +    O(1)

  2) Recoloring     =      O(logn)      +    O(1)    +     O(1) ~ O(logn)     

  ∴ 삽입하는 경우, restructuring을 하든 recoloring을 하든 O(logn)의 시간이 걸린다.