[자료구조]탐색 2 (12-2-3) Rebalance 함수

리밸런싱에 필요한 도구들의 정의 : Rebalance 함수

이제 기본적인 도구들이 마련되었으니 이 많은 도구들을 사용하기 위한 도구의 사용순서 및 사용시기를 모두! 다음 도구를 하나 더 만들자!

BTreeNode * Rebalance(BTreeNode **pRoot)
{
    int hDiff = GetHeightDiff(*pRoot); // 균형 인수 계산
    
    //균형 인수가 +2 이상이면 LL/LR 상태이다.
    if(hDiff>1) // +2이상이면(왼쪽 서브 트리 방향으로 높이가 2 이상 크다면)
    {
        if(GetHeightDiff(GetLeftSubTree(*pRoot))>0)
            *pRoot = RotateLL(*pRoot);
        else
            *pRoot = RotateLR(*pRoot);
    }
    //균형 인수가 -2 이하이면 RR/RL 상태이다.
    if(hDiff<-1) // 오른쪽 서브 트리 방향으로 2 이상 크다면,
    {
        if(GetHeightDiff(GetRightSubTree(*pRoot))<0)
            *pRoot = RotateRR(*pRoot);
        else
            *pRoot = RotateRL(*pRoot);
    }
    
    return *pRoot;
}

+2 이상이면 LL/LR 이고 -2이하이면 RR/RL 이다.
그럼 이제 LL 와 LR을 구분하는 방법을 정리해보자 !

어떤가! 루트노드의 왼쪽 자식 노드의 균형 인수를 통해 만약 양수이면 LL상태 음수이면 LR상태임을 알아낸다.

이 또한 마찬가자이지만 역시나 반대!
오른쪽 인자가 음수이면 RR상태 양수이면 RL상태임을 알아낸다.

그러므로 이것을 구현하는 코드는 이렇게 작성된다.

if(GetHeightDiff(GetLeftSubTree(*pRoot))>0) //LL 상태라면
	*pRoot = Rotate(*pRoot); // LL회전
else //LR상태
	*pRoot = Rotate(*pRoot); // LR회전 

RR/RL은 굳이 적지 않아도 위의 Rebalance 함수에서 찾을 수 있을것이다.

그런데 회전 관련함수의 호출이

*pRoot = RotateXX(*pRoot);

return *pRoot;

와 같은 형식이 뜬다.
Rebalance함수도 루트 노드의 주소 값을 반환하는 이유는

회전의 과정에서 루트 노드가 변경될 수 있기 떄문이다.
따라서 함수를 호출할 때에는 루트 노드의 변경을 대비해서 이 함수가 반환하는 값을 루트 노드를 가리키는 포인터 변수에 저장해야한다.

이제 다음 포스트에서 구현해보자 !