[Red-Black 트리]회전 rotation

rotation

---

📌레드블랙 트리의 다섯가지 속성

1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

 

📌회전(rotaion)

• 레드-블랙 트리의 삽입(insert), 삭제(delete) 연산 과정에서 트리가 수정되기 때문에 레드-블랙 트리의 특성을 위반할 수 있다. 이런 특성을 복구해주기 위해서 트리내의 일부 노드들의 색깔과 포인터를 변경해야 한다.
• 포인터를 변경하기 위해 회전을 사용하고, 이것으로 이진 검색트리 특성을 보전한다.

 ✏️삽입/삭제 과정에서 노드의 추가/삭제 과정이 일어난다. 단순 이진 검색트리는 키값의 비교를 통해 단순히 해당 위치에서 노드를 추가/삭제 하면되지만, 레드-블랙 트리는 이진 검색 트리의 특성을 유지하면서 레드-블랙 트리의 특성에 맞도록 적절히 노드의 색깔과 위치를 바꾸는 과정이필요하다. 이 과정에서, 회전을 통해 이진 검색트리의 특성을 보전하면서 트리의 구조를 수정할 수 있다.

📌과정

• 회전은 이진검색트리의 특성을 유지하면서 트리의 구조를 수정하는 과정이다. 좌회전이 일어난 후에도 이진 검색트리의 특성을 유지하는 것을 볼 수 있다.
• 좌회전 전 (중위순회 - 오름차순)
  • 𝛼 - x - β - y - 𝛾
• 좌회전 후(중위순회 - 오름차순)
  • 𝛼 - x - β - y - 𝛾

📌가정

• x의 오른쪽 자식이 리프노드가 아님.(x->right ! = T->nil)

📌로테이션 의사 코드

📌설명

📌코드

void left_rotation(rbtree *t, node_t *x) {
    node_t* y;
    y = x -> right;
    x->right = y ->left; 
    if (y->left != t->nil)
    {
        y->left->parent =x;
    }
    y->parent = x->parent; 
    if (x->parent == t->nil)
    {
        t->root = y; 
    }
    else if(x = x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }
    y -> left = x;
    x -> parent = y;
    return ;
}

📌정리

• 회전이 일어나도 이진탐색 트리의 특성을 유지한다
• 노드의 추가/삭제 과정에서, 레드-블랙 트리의 특성을 유지하기 위해 트리의 구조를 수정해야한다.
• 하지만, 이진 탐색트리의 특성 또한 유지되어야 하는데, 회전을 이용하면 이진탐색 트리의 특성을 유지하면서 트리의 구조를 수정할 수 있다.