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