平衡二叉树的平衡调整
四种类型 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;
}
}