深圳红钻足球俱乐部,动态搞笑qq表情大全,生命的托举
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("%d\n",root->v);
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论