PAT-Root of AVL Tree (25)

题目来源

Root of AVL Tree (25)

题目描述点击链接自行查看

思路简介

就是一道平衡树的模板题
后续我会在另一篇文章中补上平衡树手推的过程

遇到的问题

无

代码

/** * https://www.nowcoder.com/pat/5/problem/4117 * 平衡树 */#include<bits/stdc++.h>usingnamespacestd;structNode{Node*left,*right;intkey;intheight;//结点的高度Node(int&k):key(k),left(nullptr),right(nullptr),height(1){}};intheight(Node*u){//获取结点的高度return(u?u->height:0);}voidupdateHeight(Node*u){//更新结点的高度if(!u)return;u->height=1+max(height(u->left),height(u->right));}intgetBalanceFactor(Node*u){//获取平衡因子，空结点因子为0return(u?height(u->left)-height(u->right):0);}Node*rotateRight(Node*y){Node*x=y->left;Node*T2=x->right;// 旋转x->right=y;y->left=T2;// 更新高度updateHeight(y);updateHeight(x);returnx;}Node*rotateLeft(Node*x){Node*y=x->right;Node*T2=y->left;// 旋转y->left=x;x->right=T2;// 更新高度updateHeight(x);updateHeight(y);returny;}// 平衡节点Node*balance(Node*node){if(!node)returnnullptr;// 更新高度updateHeight(node);// 检查平衡因子intbf=getBalanceFactor(node);// 左子树过重if(bf>1){// 左-右情况：先左旋左子树if(getBalanceFactor(node->left)<0){node->left=rotateLeft(node->left);}// 左-左情况：右旋returnrotateRight(node);}// 右子树过重if(bf<-1){// 右-左情况：先右旋右子树if(getBalanceFactor(node->right)>0){node->right=rotateRight(node->right);}// 右-右情况：左旋returnrotateLeft(node);}returnnode;}// 插入节点Node*insert(Node*node,int&key){if(!node){returnnewNode(key);}if(key<node->key){node->left=insert(node->left,key);}elseif(key>node->key){node->right=insert(node->right,key);}else{// 不允许重复插入returnnode;}// 平衡当前节点returnbalance(node);}voidsolve(){intn;cin>>n;Node*root=nullptr;for(inti=0;i<n;++i){intk;cin>>k;root=insert(root,k);}cout<<root->key;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());intT=1;//cin>>T;while(T--){solve();}return0;}