PAT-A-1066 Root of AVL Tree (25 分) 创建平衡二叉查找树 C++题解

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;
}