04-树5 Root of AVL Tree (25分)---AI那点小事

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 NN (le 20≤20) which is the total number of keys to be inserted. Then NN 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

AC代码:

#include <iostream> #include <algorithm> #include <stdlib.h> using namespace std; typedef struct AVLNode* AVLTree ; struct AVLNode{ int val; AVLTree left; AVLTree right; int height; }; //求数的深度的函数 int getHeight(AVLTree t) { if (t) return max(getHeight(t->left) , getHeight(t->right)) + 1; else return 0; } //左旋 AVLTree SingleLeftRotation(AVLTree a) { AVLTree b = a->left; a->left = b->right; b->right = a; a->height = max(getHeight(a->left),getHeight(a->right))+1; b->height = max(getHeight(b->left), a->height)+1; return b; } //右旋 AVLTree SingleRightRotation(AVLTree t) { AVLTree b = t->right; t->right = b->left; b->left = t; t->height = max(getHeight(t->left), getHeight(t->right)) + 1; b->height = max(getHeight(b->right),t->height) + 1; return b; } //左右旋 AVLTree DoubleLeftRightRotation(AVLTree t) { t->left = SingleRightRotation(t->left); return SingleLeftRotation(t); } //右左旋 AVLTree DoubleRightLeftRotation(AVLTree t) { t->right = SingleLeftRotation(t->right); return SingleRightRotation(t); } //插入函数 AVLTree AVL_Insertion(int x, AVLTree t) { /* 插入X到AVL中 并返回调整后的AVL树 */ if (!t) { t = (AVLTree)malloc(sizeof(struct AVLNode)); t->val = x; t->height = 0; t->left = t->right = NULL; } else if (x < t->val) { t->left = AVL_Insertion(x, t->left); if (getHeight(t->left) - getHeight(t->right) == 2) { /*需要左旋*/ if (x < t->left->val) { t = SingleLeftRotation(t);/* 左单旋 */ } else { t = DoubleLeftRightRotation(t); /* 左右双旋 */ } } } else if ( x> t->val) { t->right = AVL_Insertion(x, t->right); if (getHeight(t->right) - getHeight(t->left) == 2) { /*需要左旋*/ if (x > t->right->val) { t = SingleRightRotation(t);/* 左单旋 */ } else { t = DoubleRightLeftRotation(t); /* 右左双旋 */ } } } t->height = max(getHeight(t->left), getHeight(t->right)) + 1; return t; } //递归先序遍历 void preOrder(AVLTree avl) { if (avl) { cout << avl->val << " "; preOrder(avl->left); preOrder(avl->right); } } int main() { int N; cin>>N; AVLTree avl = NULL; for ( int i = 0 ; i < N ; i++){ int t; cin>>t; avl = AVL_Insertion(t,avl); } cout<<avl->val; return 0; }

---来自腾讯云社区的---AI那点小事