リソース構造ナビゲーション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;
}

+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は必ずしも少なくないとは限らないが,上のResbalance関数でも見つけることができる.
ただし、回転関連関数の呼び出し

*pRoot = RotateXX(*pRoot);

return *pRoot;

似たような形が現れる.
Resbalance関数もルートノードのアドレス値を返す理由は
回転中にルートノードが変化する可能性があるためです.
したがって、関数を呼び出すときは、ルートノードの変更を防ぐために、その関数が返す値をルートノードを指すポインタ変数に格納する必要があります.
次の文章で実現しましょう.