《数据结构》04-树5 Root of AVL Tree

悠悠 2022-04-22 04:52 128阅读 0赞

# 题目 #

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.  
![2018110212034740.jpg][]![20181102120430644.jpg][]  
![20181102120437670.jpg][]![20181102120443929.jpg][]  
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

# 分析 #

题目大意就是按顺序插入平衡二叉树，返回该 AVL 树的根结点值  
[数据结构（六）平衡二叉树][Link 1]  
看完你就懂了

#include<iostream>
    #include<malloc.h>
    typedef struct AVLNode *AVLTree;
    struct AVLNode{
        
    	int data;     // 存值 
    	AVLTree left;  // 左子树 
    	AVLTree right;  // 右子树 
    	int height;  // 树高 
    };
    using namespace std;
    
    // 返回最大值 
    int Max(int a,int b){
        
    	return a>b?a:b;
    }
    
    // 返回树高，空树返回 -1 
    int getHeight(AVLTree A){
        
    	return A==NULL?-1:A->height;
    }
    
    // LL单旋
    // 把 B 的右子树腾出来挂给 A 的左子树，再将 A 挂到 B 的右子树上去 
    AVLTree LLRotation(AVLTree A){
        
    	// 此时根节点是 A 
    	AVLTree B = A->left;  // B 为 A 的左子树  
    	A->left = B->right;   // B 的右子树挂在 A 的左子树上 
    	B->right = A;     //  A 挂在 B 的右子树上 
    	A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
    	B->height = Max(getHeight(B->left),A->height) + 1;
    	return B;  // 此时 B 为根结点了 
    }
    
    // RR单旋
    AVLTree RRRotation(AVLTree A){
        
    	// 此时根节点是 A 
    	AVLTree B = A->right;
    	A->right = B->left;
    	B->left = A;
    	A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
    	B->height = Max(getHeight(B->left),A->height) + 1;
    	return B;  // 此时 B 为根结点了 
    }
    
    // LR双旋 
    AVLTree LRRotation(AVLTree A){
        
    	// 先 RR 单旋
    	A->left = RRRotation(A->left);
    	// 再 LL 单旋 
    	return LLRotation(A);
    }
    
    // RL双旋
    AVLTree RLRotation(AVLTree A){
        
    	// 先 LL 单旋
    	A->right = LLRotation(A->right);
    	// 再 RR 单旋 
    	return RRRotation(A); 
    }
    
    AVLTree Insert(AVLTree T,int x){
        
    	if(!T){
          // 如果该结点为空，初始化结点 
    		T = (AVLTree)malloc(sizeof(struct AVLNode));
    		T->data = x;
    		T->left = NULL;
    		T->right = NULL;
    		T->height = 0;
    	}else{
          // 否则不为空， 
    		if(x < T->data){
          // 左子树 
    			T->left = Insert(T->left,x);
    			if(getHeight(T->left)-getHeight(T->right)==2){
          // 如果左子树和右子树高度差为 2 
    				if(x < T->left->data)  // LL 单旋 
    					T = LLRotation(T); 
    				else if(T->left->data < x)  // LR双旋
    					T = LRRotation(T); 
    			}
    		}else if(T->data < x){
        
    			T->right = Insert(T->right,x);
    			if(getHeight(T->right)-getHeight(T->left)==2){
        
    				if(x < T->right->data)  // RL 双旋 
    					T = RLRotation(T); 
    				else if(T->right->data < x)  // RR单旋
    					T = RRRotation(T); 
    			}
    		}
    	}
    	//更新树高 
    	T->height = Max(getHeight(T->left),getHeight(T->right)) + 1;
    	return T;
    } 
    
    
    int main(){
        
    	AVLTree T=NULL;
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++){
        
    		int tmp;
    		cin>>tmp;
    		T = Insert(T,tmp);
    	}
    	cout<<T->data;
    	return 0;
    }

[2018110212034740.jpg]: https://img-blog.csdnimg.cn/2018110212034740.jpg
[20181102120430644.jpg]: /images/20220422/b3869619aeb441329a020c1b3d6c809e.png
[20181102120437670.jpg]: https://img-blog.csdnimg.cn/20181102120437670.jpg
[20181102120443929.jpg]: /images/20220422/034ad97f588e4f77b1a563ee84fdd0c8.png
[Link 1]: https://blog.csdn.net/liyuanyue2017/article/details/83652743