程序填空题:RL Rotation
The function `RL_Rotation` is to do right-left rotation to the trouble-finder tree node `T` in an AVL tree.
```c++
typedef struct TNode *Tree;
struct TNode {
int key, h;
Tree left, right;
};
Tree RL_Rotation( Tree T )
{
Tree K1, K2;
K1 = T->right;
K2 = K1->left;
@@[K1->left](2) = K2->right;
@@[T->right](2) = K2->left;
@@[K2->right = K1](2);
K2->left = T;
/* Update the heights */
K1->h = maxh(Height(K1->left), Height(K1->right)) + 1;
T->h = maxh(Height(T->left), Height(T->right)) + 1;
K2->h = maxh(K1->h, T->h) + 1;
return K2;
}
```
答案:
第1空:K1->left
第2空:T->right
第3空:K2->right = K1
```c++
typedef struct TNode *Tree;
struct TNode {
int key, h;
Tree left, right;
};
Tree RL_Rotation( Tree T )
{
Tree K1, K2;
K1 = T->right;
K2 = K1->left;
@@[K1->left](2) = K2->right;
@@[T->right](2) = K2->left;
@@[K2->right = K1](2);
K2->left = T;
/* Update the heights */
K1->h = maxh(Height(K1->left), Height(K1->right)) + 1;
T->h = maxh(Height(T->left), Height(T->right)) + 1;
K2->h = maxh(K1->h, T->h) + 1;
return K2;
}
```
答案:
第1空:K1->left
第2空:T->right
第3空:K2->right = K1