AcWing 1552. AVL树的根(二叉树平衡旋转)
原题链接
困难
作者:
麦克斯韦妖_7
,
2021-08-26 17:29:57
,
所有人可见
,
阅读 268
#include <iostream>
using namespace std;
struct node{
int data;
int height;
node *left, *right;
};
node* newNode(int data){
node* Node = new node;
Node->data = data;
Node->height = 1;
Node->left = Node->right = NULL;
return Node;
}
int getHeight(node* root){
if(root == NULL) return 0;
else return root->height;
}
void updateHeight(node* root){
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}
int getFactor(node* root){
return getHeight(root->left) - getHeight(root->right);
}
void L(node* &root){
node* temp = root->right;
root->right = temp->left;
temp->left = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void R(node* &root){
node* temp = root->left;
root->left = temp->right;
temp->right = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insert(node* &root, int data){
if(root == NULL){
root = new node;
root->data = data;
root->height = 1;
root->left = root->right = NULL;
return;
}
if(data < root->data){
insert(root->left, data);
updateHeight(root);
if(getFactor(root) == 2){
if(getFactor(root->left) == -1){ //LR型
L(root->left);
R(root);
}else if(getFactor(root->left) == 1){ //LL型
R(root);
}
}
}
else{
insert(root->right, data);
updateHeight(root);
if(getFactor(root) == -2){
if(getFactor(root->right) == -1){ //RR
L(root);
}else if(getFactor(root->right) == 1){ //RL
R(root->right);
L(root);
}
}
}
}
int main(){
int n;
cin >> n;
node *root = NULL;
for(int i = 0; i < n; i ++){
int data;
cin >> data;
insert(root, data);
}
cout << root->data;
return 0;
}