c++ - BST の再帰的なバランス調整

Question

私はBSTのクラスを持っています。RotateBST のルートを引数として取り、バランスの取れた BST を返す再帰関数が必要です。

1つのノードだけバランスをとるコードが添付されていますが、ルートノードに対しては機能していません。

再帰的にしたいので、単一のノードではなくツリー全体のバランスを取ります。

/* rotate */
Node* BST :: Rotate(Node* root)
{
    // gets the balance factor
    int balance = getBalance(root);

    // 4 cases for unbalanced BST

    // Left Left Case
    if (balance > 1 && root->data < root->left->data)
        return rightRotate(root);

    // Right Right Case
    if (balance < -1 && root->data > root->right->data)
        return leftRotate(root);

    // Left Right Case
    if (balance > 1 && root->data > root->left->data)
    {
        root->left =  leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && root->data < root->right->data)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    /* return the (unchanged) node pointer */
    return root;
}