1066. Root of AVL Tree (25)-PAT甲级真题(AVL树)左旋右旋四种类型

原题:https://www.patest.cn/contests/pat-a-practise/1066

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
	int v, height;
	node *lchild, *rchild;
};
int getheight(node *root) //获取高度
		{
	if (root == NULL)
		return 0;
	return root->height;
}
int getbalance(node *root) //获取平衡因子
		{
	return getheight(root->lchild) - getheight(root->rchild);
}
void L(node *&root) //左旋
		{
	node *temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void R(node *&root) //右旋
		{
	node *temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void insert(node *&root, int x) //建树并且调整
		{
	if (root == NULL) {
		root = new node;
		root->v = x;
		root->height = 1;
		root->lchild = root->rchild = NULL;
		return;
	}
	if (x < root->v) {
		insert(root->lchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == 2) {
			if (getbalance(root->lchild) == 1) //LL型
				R(root);
			else if (getbalance(root->lchild) == -1) //LR型
					{
				L(root->lchild);
				R(root);
			}
		}
	} else {
		insert(root->rchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == -2) {
			if (getbalance(root->rchild) == -1) //RR型
				L(root);
			else if (getbalance(root->rchild) == 1) //RL型
					{
				R(root->rchild);
				L(root);
			}
		}
	}
}
int main() {
	int n, x;
	node *root = NULL;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		insert(root, x);
	}
	cout << root->v << endl;
	return 0;
}

 

0

发表评论

邮箱地址不会被公开。 必填项已用*标注