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
题目大意: 给出一串序列, 建立一颗平衡二叉树, 理解了平衡二叉树的构造过程 该题就比较简单了
给出两种建立的方法, 第一种是最先接触到的建立方法, 第二种是推荐的建立方法
1 #include<iostream> 2 using namespace std; 3 class node{ 4 public: 5 int val; 6 node *left, *right; 7 node(){left=NULL; right=NULL;} 8 }; 9 10 node* rightRoate(node* root){ 11 node* temp=root->left; 12 root->left=temp->right; 13 temp->right=root; 14 return temp; 15 } 16 17 node* leftRoate(node* root){ 18 node* temp=root->right; 19 root->right=temp->left; 20 temp->left=root; 21 return temp; 22 } 23 24 node* leftRightRoate(node* root){ 25 root->left=leftRoate(root->left); 26 return rightRoate(root); 27 } 28 29 30 31 node* rightLeftRoate(node* root){ 32 root->right=rightRoate(root->right); 33 return leftRoate(root); 34 } 35 36 int getHeight(node* root){ 37 if(root==NULL) return 0; 38 int l=getHeight(root->left), r=getHeight(root->right); 39 return l>r? (l+1):(r+1); 40 } 41 42 node* insert(node* root, int val){ 43 if(root==NULL){ 44 node *newnode=new node(); 45 newnode->val=val; 46 return newnode; 47 } 48 if(root->val>val){ 49 root->left=insert(root->left, val); 50 if(getHeight(root->left)-getHeight(root->right)>1){ 51 if(getHeight(root->left->left)>getHeight(root->left->right)) root=rightRoate(root); 52 else root=leftRightRoate(root); 53 } 54 } 55 else { 56 root->right=insert(root->right, val); 57 if(getHeight(root->right)-getHeight(root->left)>1){ 58 if(getHeight(root->right->right)>getHeight(root->right->left)) root=leftRoate(root); 59 else root=rightLeftRoate(root); 60 } 61 } 62 return root; 63 } 64 65 66 67 int main(){ 68 node *root=NULL; 69 int i, n, t; 70 scanf("%d", &n); 71 for(i=0; i<n; i++){ 72 scanf("%d", &t); 73 root=insert(root, t); 74 } 75 printf("%d ", root->val); 76 return 0; 77 }
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 struct Node{ 5 int val, height; 6 Node *left, *right; 7 Node(int v){val = v; left=right=NULL; height=1;} 8 }; 9 10 int getHeight(Node *root){ 11 return root==NULL ? 0 : root->height; 12 } 13 14 void updateHeight(Node *root){ 15 int l = getHeight(root->left), r = getHeight(root->right); 16 root->height = l>r ? l+1 : r+1; 17 } 18 19 int getBalanceFactor(Node* root){ 20 return getHeight(root->left) - getHeight(root->right); 21 } 22 23 void leftRoate(Node* &root){ 24 Node *temp = root->right; 25 root->right = temp->left; 26 temp->left = root; 27 updateHeight(root); 28 updateHeight(temp); 29 root = temp; 30 } 31 32 void rightRoate(Node* &root){ 33 Node *temp = root->left; 34 root->left = temp->right; 35 temp->right = root; 36 updateHeight(root); 37 updateHeight(temp); 38 root = temp; 39 } 40 41 void insertNode(Node* &root, int val){ 42 if(root==NULL){ 43 root = new Node(val); 44 return; 45 } 46 if(val<root->val){ 47 insertNode(root->left, val); 48 updateHeight(root);//插入新节点后不要忘记更新根节点的高度 49 if(getBalanceFactor(root)==2){//调节不平衡的二叉树 50 if(getBalanceFactor(root->left)==1) rightRoate(root); 51 else{ 52 leftRoate(root->left); 53 rightRoate(root); 54 } 55 } 56 }else{ 57 insertNode(root->right, val); 58 updateHeight(root); 59 if(getBalanceFactor(root)==-2){ 60 if(getBalanceFactor(root->right)==-1) leftRoate(root); 61 else{ 62 rightRoate(root->right); 63 leftRoate(root); 64 } 65 } 66 } 67 } 68 int main(){ 69 int n, i; 70 scanf("%d", &n); 71 Node *root=NULL; 72 for(i=0; i<n; i++){ 73 int val; 74 scanf("%d", &val); 75 insertNode(root, val); 76 } 77 printf("%d ", root->val); 78 return 0; 79 }