1066 Root of AVL Tree (25 分)

题目传送门：1066 Root of AVL Tree (25 分)

一、题目大意

给定一个数列，创建平衡二叉查找树

二、解题思路

这道题就是一个赤裸裸的构建平衡树的问题，然而我之前一直没有写过平衡树的代码，因为对平衡树的旋转不太理解。这次我不想绕过这个知识盲点了，在网上搜了博客学习平衡树的知识。

平衡树（AVL）的旋转操作参考了这篇博客：AVL平衡二叉树中旋转操作的本质及其实现
这篇博客写的非常好，我看完之后就理解了AVL的旋转过程并用代码实现了出来。

三、AC代码

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int val, height;
	Node *left, *right;	
	Node(int val):val(val), height(0){
		left=NULL;
		right=NULL;
	}
};
int getHeight(Node* root){
	if(root == NULL)return -1;
	return root->height;
}
Node* singleRotateWithRight(Node* root){// 右子树左旋
	Node* k = root->right;
	root->right = k->left;
	k->left = root;
	root->height = max(getHeight(root->left), getHeight(root->right))+1;
	k->height = max(getHeight(k->left), getHeight(k->right))+1;
	return k;
}
Node* singleRotateWithLeft(Node* root){// 左子树右旋
	Node* k = root->left;
	root->left = k->right;
	k->right = root;
	root->height = max(getHeight(root->left), getHeight(root->right))+1;
	k->height = max(getHeight(k->left), getHeight(k->right))+1;
	return k;
}
Node* doubleRotateWithRight(Node* root){// 右子树的左子树先右旋，然右子树左旋
	root->right = singleRotateWithLeft(root->right);
	return singleRotateWithRight(root);
}
Node* doubleRotateWithLeft(Node* root){// 左子树的右子树先左旋，然后左子树右旋
	root->left = singleRotateWithRight(root->left);
	return singleRotateWithLeft(root);
}
Node* insert(Node* root, int val){
	if(root == NULL){
		return new Node(val);
	}
	if(val < root->val){
		root->left = insert(root->left, val);
		if(getHeight(root->left) - getHeight(root->right) == 2){// 不平衡
			if(val < root->left->val){// 插入到了左子树的左子树， 单旋转
				root = singleRotateWithLeft(root);
			}else{// 插入到了左子树的右子树，双旋转
				root = doubleRotateWithLeft(root);
			}
		}
	}else{
		root->right = insert(root->right, val);
		if(getHeight(root->right) - getHeight(root->left) == 2){// 不平衡
			if(val >= root->right->val){// 插入到了右子树的右子树，单旋转
				root = singleRotateWithRight(root);
			}else{// 插入到了右子树的左子树，双旋转
				root = doubleRotateWithRight(root);
			}
		}
	}
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
	return root;
}
int main(){
	int n;
	cin >> n;
	int x;
	cin >> x;
	Node* root = new Node(x);
	for(int i = 1; i < n; i++){
		int x;
		cin >> x;
		root = insert(root, x);
	}
	cout << root->val << endl;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/100075136