PAT (Advanced Level) Practice

1066 Root of AVL Tree (25分)

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 tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:

5 88 70 61 96 120

Sample Output 1:

70

Sample Input 2:

7 88 70 61 96 120 90 65

Sample Output 2:

88

个人代码:

#include <stdio.h> #include <algorithm> // #define LOCAL using namespace std; typedef struct AVLNode { //AVL树结点 int height, val; struct AVLNode *lchild, *rchild, *parent; } AVLNode, *AVLTree; // void InitAVLTree (AVLTree &T) { //初始化 // T -> lheight = 0; // T -> rheight = 0; // T -> lchild = NULL; // T -> rchlid = NULL; // T -> parent = NULL; // } AVLNode *AVLTreeInsert (AVLTree &T, int val) { //插入新的结点 if (T == NULL) { T = (AVLTree)malloc(sizeof(AVLNode)); T->val = val; T->lchild = NULL; T->rchild = NULL; T->parent = NULL; return T; } else if (val < T->val) { return AVLTreeInsert(T->lchild, val); } else { return AVLTreeInsert(T->rchild, val); } } int AVLTreeHeight (AVLTree &T) { //求高度 if (T == NULL) { return 0; } else { int lheight, rheight; lheight = AVLTreeHeight(T->lchild); rheight = AVLTreeHeight(T->rchild); T->height = max(lheight + 1, rheight + 1); // printf("%d*\n", T -> height); return T->height; } } void SetParent (AVLTree &T) { //设置双亲结点 if (T == NULL) { return; } if (T->lchild != NULL) { T->lchild->parent = T; SetParent(T->lchild); } if (T->rchild != NULL) { T->rchild->parent = T; SetParent(T->rchild); } } void AVLTreeLrevov (AVLTree &p, AVLTree &T) { //左旋操作 if (p->parent->parent != NULL) { if (p->parent->val < p->parent->parent->val) { p->parent->parent->lchild = p; } else { p->parent->parent->rchild = p; } } p->parent->rchild = p->lchild; p->lchild = p->parent; if (p->lchild->val == T->val) { T = p; T->parent = NULL; } } void AVLTreeRrevov (AVLTree &p, AVLTree &T) { //右旋操作 if (p->parent->parent != NULL) { //首先判断该结点 if (p->parent->val < p->parent->parent->val) { p->parent->parent->lchild = p; } else { p->parent->parent->rchild = p; } } p->parent->lchild = p->rchild; p->rchild = p->parent; if (p->rchild->val == T->val) { T = p; T->parent = NULL; } } // void visit (AVLTree T) { //前序遍历 // if (T != NULL) { // printf("T->val=%d,T->height=%d--\n",T->val, T->height); // visit (T->lchild); // visit (T->rchild); // } // } int main () { #ifdef LOCAL freopen("./in.txt", "r", stdin); // freopen("./out.txt", "w", stdout); #endif int n; scanf("%d", &n); AVLTree T = NULL; AVLNode *p = NULL; // InitAVLTree (T); for (int i = 0; i < n; i++) { int lheight = 0, rheight = 0, value = 0; //左子树高度、右子树高度、值 int revov = 0; //标志需要进行的旋转操作，0-4代表结点类型，不操作，LL，LR，RL，RR scanf("%d", &value); p = AVLTreeInsert(T, value); AVLTreeHeight(T); SetParent(T); while (p != NULL) { //找到第一个不平衡结点 if (p->lchild != NULL) { //左子树高度 lheight = p->lchild->height; } else { lheight = 0; } if (p->rchild != NULL) { //右子树高度 rheight = p->rchild->height; } else { rheight = 0; } if (abs(lheight - rheight) < 2) { //从插入点往上寻找双亲结点，使p为第一个不平衡结点 p = p->parent; } else break; } if (abs(lheight - rheight) >= 2) { //p可能为NULL，可能为第一个不平衡结点 if (value < p->val) { p = p->lchild; //需要进行LL/LR旋转操作 if (value < p->val) { revov = 1; //LL旋转操作 } else { revov = 2; //LR旋转操作 } } else { p = p->rchild; //需要进行RL/RR旋转操作 if (value < p->val) { revov = 3; //RL旋转操作 } else { revov = 4; //RR旋转操作 } } } switch (revov) { //根据不平衡点类型选择旋转操作，旋转后注意重新设置双亲结点 case 0: //不是不平衡点，不进行操作 break; case 1: //LL类型进行右旋操作 AVLTreeRrevov(p, T); SetParent(T); break; case 2: //LR类型先进行左旋操作再进行右旋操作 p = p->rchild; AVLTreeLrevov(p, T); SetParent(T); AVLTreeRrevov(p, T); SetParent(T); break; case 3: //RL类型先进行右旋操作再进行左旋操作 p = p->lchild; //旋转的对象是 AVLTreeRrevov(p, T); SetParent(T); AVLTreeLrevov(p, T); SetParent(T); break; case 4: //RR类型进行左旋操作 AVLTreeLrevov(p, T); SetParent(T); break; } // visit(T); //遍历一遍AVL树，检查是否正确 } printf("%d", T->val); //已经成功构建AVL树，选择自己的操作 return 0; }

思路提示:

建立AVL树的步骤如下：

首先定义AVL树的结点，包含高度、值、指向孩子结点和双亲结点的指针等信息每读入一个结点，就要将他按照BST的排序规则插入AVL树中每个结点插入后，检查AVL树中每个结点是否满足左右子树高度相差的绝对值不超过1，方法是从刚插入的结点往上找他的双亲结点（设置双亲结点的好处）找到最近的一个不满足平衡条件的结点，根据LL、LR、RL、RR四种类型确定需要进行旋转的操作和对象注意，当树的高度和双亲节点变化后，需要及时的通过函数更新