リソース構造ナビゲーション2(12-2-3)Resbalance関数

再バランスに必要なツールの定義さいへいこうに必要なつーるのていぎ:再バランス関数さいへいこうかんすう

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;
}

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

*pRoot = RotateXX(*pRoot);

return *pRoot;