PAT-Root of AVL Tree (25)

题目来源Root of AVL Tree (25)题目描述点击链接自行查看思路简介就是一道平衡树的模板题后续我会在另一篇文章中补上平衡树手推的过程遇到的问题无代码/** * https://www.nowcoder.com/pat/5/problem/4117 * 平衡树 */#includebits/stdc.husingnamespacestd;structNode{Node*left,*right;intkey;intheight;//结点的高度Node(intk):key(k),left(nullptr),right(nullptr),height(1){}};intheight(Node*u){//获取结点的高度return(u?u-height:0);}voidupdateHeight(Node*u){//更新结点的高度if(!u)return;u-height1max(height(u-left),height(u-right));}intgetBalanceFactor(Node*u){//获取平衡因子空结点因子为0return(u?height(u-left)-height(u-right):0);}Node*rotateRight(Node*y){Node*xy-left;Node*T2x-right;// 旋转x-righty;y-leftT2;// 更新高度updateHeight(y);updateHeight(x);returnx;}Node*rotateLeft(Node*x){Node*yx-right;Node*T2y-left;// 旋转y-leftx;x-rightT2;// 更新高度updateHeight(x);updateHeight(y);returny;}// 平衡节点Node*balance(Node*node){if(!node)returnnullptr;// 更新高度updateHeight(node);// 检查平衡因子intbfgetBalanceFactor(node);// 左子树过重if(bf1){// 左-右情况先左旋左子树if(getBalanceFactor(node-left)0){node-leftrotateLeft(node-left);}// 左-左情况右旋returnrotateRight(node);}// 右子树过重if(bf-1){// 右-左情况先右旋右子树if(getBalanceFactor(node-right)0){node-rightrotateRight(node-right);}// 右-右情况左旋returnrotateLeft(node);}returnnode;}// 插入节点Node*insert(Node*node,intkey){if(!node){returnnewNode(key);}if(keynode-key){node-leftinsert(node-left,key);}elseif(keynode-key){node-rightinsert(node-right,key);}else{// 不允许重复插入returnnode;}// 平衡当前节点returnbalance(node);}voidsolve(){intn;cinn;Node*rootnullptr;for(inti0;in;i){intk;cink;rootinsert(root,k);}coutroot-key;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}