avl就是优化二叉查找树
平衡因子不大于1
左 < 根 < 右
具体看代码
#include<bits/stdc++.h> using namespace std; typedef struct node; typedef node * tree; struct node { int v; int heigh; tree l,r; }; //获取以root为根结点的子树的当前height int getheigh(tree root) { if(root==null) return 0; return root->heigh; } //更新结点root的heigh void updataheigh(tree root) { //max(左孩子结点的height,有孩子结点的height)+1 root->heigh=max(getheigh(root->l),getheigh(root->r))+1; } //计算平衡因子 int getbalance(tree root) { //左-右 return getheigh(root->l)-getheigh(root->r); } //左旋 注意原理 对于rr是root的右孩子的平衡因子是-1 void l(tree &root) { tree temp; temp=root->r; root->r=temp->l; temp->l=root; updataheigh(root); updataheigh(temp); root=temp; } void r(tree &root) { tree temp; temp=root->l; root->l=temp->r; temp->r=root; updataheigh(root); updataheigh(temp); root=temp; } void insertt(tree &root,int v) { if(root==null){//当结点是空的时候 就是插入的时候 root=new node; root->v=v; root->heigh=1; root->l=root->r=null; return; } if(v<root->v){ insertt(root->l,v); updataheigh(root);//注意更新树高 if(getbalance(root)==2){ if(getbalance(root->l)==1){ r(root); } else if(getbalance(root->l)==-1){ l(root->l); r(root); } } } else{ insertt(root->r,v); updataheigh(root); if(getbalance(root)==-2){ if(getbalance(root->r)==-1){ l(root); } else if(getbalance(root->r)==1){ r(root->r); l(root); } } } } int main() { int n; scanf("%d",&n); int x; tree root; root=null; for(int i=0;i<n;i++){ scanf("%d",&x); insertt(root,x); } printf("%dn",root->v); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605901.html