函数题：Building an AVL Tree

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.











Now given a sequence of insertions, you are supposed to build the AVL tree. Then given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

(1) A is the root
(2) A is the right child of B
(3) A is the left child of B
(4) A and B are siblings
(5) A is the parent of B

### Format of functions:
c++
Tree Build_AVL ( int insertion[ ], int n );
int Test ( Tree T, int type, int A, int B );

The function Build_AVL is supposed to build an AVL tree according to the input sequence.

Here Tree is defined as the following:


typedef struct TNode *Tree;
struct TNode {
int key; //key of the node
int height; //height of the subtree with this node as the root
Tree left, right; //pointing to the left and right children of this node
};

The array insertion contains n (a positive integer) distinct keys to be inserted in order into an initially empty AVL tree. The root pointer of the resulting tree is supposed to be returned by Build_AVL.

The function Test is supposed to test if a given statement for an AVL tree T is correct or not, and return 1 if the result is true, or 0 otherwise. The parameter type is an integer in [1, 5], which gives the index of a statement, as listed in the problem description; and A and B are the corresponging key values. For type 1, the value of B can be ignored. It is guaranteed that both A and B in the statements are in the tree.

### Sample program of judge:
c++
#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *Tree;
struct TNode {
int key; //key of the node
int height; //height of the subtree with this node as the root
Tree left, right; //pointing to the left and right children of this node
};

Tree Build_AVL ( int insertion[ ], int n );
int Test ( Tree T, int type, int A, int B );

int main()
{
int n, *insertion;
int m, type, A, B, i;
Tree T;

scanf("%d", &n);
insertion = (int *)malloc(sizeof(int) * n);
for (i=0; i<n; i++) scanf("%d", &insertion[i]);
T = Build_AVL(insertion, n);
scanf("%d", &m);
for (i=0; i<m; i++) {
scanf("%d %d", &type, &A);
if (type != 1) scanf("%d", &B);
if (Test(T, type, A, B)) printf("Yes\n");
else printf("No\n");
}
return 0;
}

/* Your function will be put here */



### Sample Input 1 (Figure 1):
in
3
88 70 61
8
1 70
1 61
2 88 70
3 88 70
4 61 88
4 88 70
5 88 70
5 70 61


### Sample Output 1:
out
Yes
No
Yes
No
Yes
No
No
Yes


### Sample Input 2 (Figure 2):
in
5
88 70 61 96 120
7
1 70
2 120 96
2 88 70
3 88 70
3 88 96
4 96 88
5 96 120


### Sample Output 2:
out
Yes
Yes
No
No
Yes
No
Yes


### Sample Input 3 (Figure 3):
in
6
88 70 61 96 120 90
8
1 70
1 88
2 90 88
2 96 88
3 90 96
4 90 61
5 70 61
5 96 70


### Sample Output 3:
out
No
Yes
No
Yes
Yes
No
Yes
No


### Sample Input 4 (Figure 4):
in
7
88 70 61 96 120 90 65
7
1 88
2 70 65
3 65 88
3 70 88
4 96 70
4 61 70
5 61 65


### Sample Output 4:
out
Yes
Yes
Yes
No
No
Yes
No









答案：若无答案欢迎评论