平衡二叉树的平衡调整

四种类型 LL , RR ,LR , RL

四种插入情况，

LL 情况直接右旋
RR 左旋
LR 先对左孩子左旋，根节点右旋
RL 先对右孩子右旋，根节点左旋

int getHeight(BTreeNode* node) {
    if (node == nullptr)
    {
        return 0;
    }
    return node->height;
}

void rotate_rr(BTreeNode* node) {
    int J;
    if (node->parent != nullptr)
    {
        if (node->parent->left_child == node)
        {
            J = 1;
        }
        else
        {
            J = 0;
        }
    }
    BTreeNode* temp = node->right_child;
    node->right_child = temp->left_child;
    temp->left_child = node;

    temp->parent = node->parent;
    if (J == 1)
    {
        temp->parent->left_child = temp;
    }
    else
    {
        temp->parent->right_child = temp;
    }
    node->parent = temp;
    if (node->right_child != nullptr)
    {
         node->right_child->parent = node; 
    }
    if (node->right_child != nullptr)
    {
        node->right_child->height = max(getHeight(node->right_child->left_child), getHeight(node->right_child->right_child)) + 1;
    }
    node->height = max(getHeight(node->left_child), getHeight(node->right_child)) + 1;
    temp->height = max(getHeight(temp->left_child), getHeight(temp->right_child)) + 1;
}

void rotate_ll(BTreeNode* node) {
    int J;
    if (node->parent != nullptr)
    {
        if (node->parent->left_child == node)
        {
            J = 1;
        }
        else
        {
            J = 0;
        }

    }
    BTreeNode* temp = node->left_child;
    node->left_child = temp->right_child;
    temp->right_child = node;
    temp->parent = node->parent;
    if (J == 1)
    {
        temp->parent->left_child = temp;
    }
    else
    {
        temp->parent->right_child = temp;
    }
    node->parent = temp;
    if (node->left_child != nullptr)
    {
        node->left_child->parent = node;
    }
    if (node->left_child != nullptr)
    {
        node->left_child->height = max(getHeight(node->left_child->left_child), getHeight(node->left_child->right_child)) + 1;
    }
    node->height = max(getHeight(node->left_child), getHeight(node->right_child)) + 1;
    temp->height = max(getHeight(temp->left_child), getHeight(temp->right_child)) + 1;
}

void rotate_rl(BTreeNode* node) {
    rotate_ll(node->right_child);
    rotate_rr(node);
}


void rotate_lr(BTreeNode* node) {
    rotate_rr(node->left_child);
    rotate_ll(node);
}

插入新节点后需要判断其父节点的父节点(爷爷节点)的类型后选择

struct BTreeNode{
    int value{0};
    int height{0};
    BTreeNode* parent{nullptr};
    BTreeNode* left_child{nullptr};
    BTreeNode* right_child{nullptr};
    BTreeNode( int value ){
        this->value = value;
    }
    BTreeNode(){
        this->value = 0;
    }
};
int getHeight(BTreeNode* node) {
    if (node == nullptr)
    {
        return 0;
    }
    return node->height;
}


void show_insert_type(BTreeNode* node) {
    BTreeNode* par = node;
    int leftheight = 0, rightheight = 0;
    int J = 0;
    while (1) // 循环往上查找
    {
        par = par->parent;
        leftheight = getHeight(par->left_child);
        rightheight = getHeight(par->right_child);
        if (abs(leftheight - rightheight) > 1)
        {
            J = 1;
            break;
        }
    }
    if (leftheight > rightheight) // LL , LR
    {
        if (getHeight(par->left_child->left_child) > getHeight(par->left_child->right_child))
        {
            cout << par->value << " " << "LL" << endl;
        }
        else
        {
            cout << par->value << " " << "LR" << endl;
        }
    }
    else // RR , RL
    {
        if (getHeight(par->right_child->right_child) > getHeight(par->right_child->left_child))
        {
            cout << par->value << " " << "RR" << endl;
        }
        else
        {
            cout << par->value << " " << "RL" << endl;
        }
    }
    if (J == 0)
    {
        cout << "None" << endl;
    }
}

https://blog.csdn.net/ssf_cxdm/article/details/81607235