[자료구조]탐색 2 (12-2-2) LR/RL회전 도구

리밸런싱에 필요한 도구들의 정의 : LR,RL회전

도구를 구현하기 앞서 우리는

• LR회전 : 부분적 RR회전에 이어서 LL회전을 진행한다.
• RR회전 : 부분적 LL회전에 이어서 RR회전을 진행한다.

그럼 바로 LR회전을 담당하는 함수의 구현을 보자

BTreeNode * RotateLR(BTreeNode*bst) // LR회전을 담당하는 함수
{
    BTreeNode * pNode; // parent Node
    BTreeNode * cNode; // child Node
    
    //pNode, cNode 가 LR회전을 위해 적절한 위치를 가리키게한다.
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    //실제 LR회전을 담당하는 두 개의 문장
    ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR회전
    return RotateLL(pNode); // LL회전
}

어떤가!
생각보다 간단하지 않는가?!
앞서 LR회전을 위해서는 부분적RR회전후 전체적인 LL회전을 해야한다고 했다.
그 부분적 회전을 담당하는 코드가 마지막에서 두번째 줄 코드이다.
이를 통해
이르케 떼어내서 RR회전을 해주고
다시 붙인다!
그리고 LL회전을 해주면 리밸런싱이 완료된다

그렇다면 RL회전은 반대로 부분적 LL회전 후 RR회전을 해주면 된다는것을 눈치 챘는가?
코드로 보자

BTreeNode * RotateRL(BTreeNode*bst) // LR회전을 담당하는 함수
{
    BTreeNode * pNode; // parent Node
    BTreeNode * cNode; // child Node
    
    //pNode, cNode 가 LR회전을 위해 적절한 위치를 가리키게한다.
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    //실제 LR회전을 담당하는 두 개의 문장
    ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 RR회전
    return RotateRR(pNode); // LL회전
}

이로써 회전에 필요한 도구들을 모두 마련했다.

이제 남은것은 적절한 시기에 적절한 도구를 선택하여 활용하는 것!!
이것을 다음포스트에서 알아보자.