平衡二叉树的旋转及其代码实现

平衡二叉树的构造问题以及为了维护它的平衡所要进行的LL旋转、RR旋转、LR旋转、RL旋转。

一、平衡二叉树的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
node *insert(node *root, int x) {
if (root == 0) {
root = &all[total++];
root->left = root->right = 0;
root->val = x;
root->height = 0;
} else if (x < root->val) {
root->left = insert(root->left, x);
if (height(root->left) - height(root->right) == 2) {
root = (x < root->left->val) ? LL(root) : LR(root);
}
} else {
root->right = insert(root->right, x);
if (height(root->right) - height(root->left) == 2) {
root = (x > root->right->val) ? RR(root) : RL(root);
}
}
root->height = max(height(root->left), height(root->right)) + 1;
return root;
}

二、LL旋转

所谓LL旋转并不是指旋转方向,而是指新插入导致不平衡的元素位于左子树的左儿子位置,也就是LeftLeft。

看一下这种旋转的示意图:
ll_rotate

1
2
3
4
5
6
7
8
node *LL(node *k2) {
node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
return k1;
}

三、RR旋转

同样LL旋转是指新插入导致不平衡的元素位于右子树的右儿子位置,也就是RightRight。

看一下这种旋转的方式示意图:

rr_rotate

1
2
3
4
5
6
7
8
node *RR(node *k1) {
node *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->left), height(k2->right)) + 1;
return k2;
}

四、LR旋转和RL旋转

LR和RL则分别表示位于左子树的右儿子和右子树的左儿子。

1.对于LR旋转,首先将最近的不平衡结点k3的左子树进行RR旋转,再将k3本身进行LL旋转。

1
2
3
4
node *LR(node *k3) {
k3->left = RR(k3->left);
return LL(k3);
}

2.对于RL旋转,首先将最近的不平衡结点k3的右子树进行LL旋转,再将k3本身进行RR旋转。

1
2
3
4
node *RL(node *k1) {
k1->right = LL(k1->right);
return RR(k1);
}

THE END.

评论