php协会网站源码,长春做网站 长春万网,网站工作室设计,推广普通话的方法#xff08;附代码#xff0c;简洁好理解#xff09;
目录
什么是平衡二叉树#xff1f;
如何保证二叉树平衡#xff1f;
左旋/右旋
左右双旋/右左双旋
代码
树的结构#xff1a; 树的高度与平衡因子#xff1a;
左/右旋#xff1a;
平衡维护#xff1a;
…附代码简洁好理解
目录
什么是平衡二叉树
如何保证二叉树平衡
左旋/右旋
左右双旋/右左双旋
代码
树的结构 树的高度与平衡因子
左/右旋
平衡维护
构建树 什么是平衡二叉树
简单来说就是二叉搜索树的升级版。一般的二叉搜索树在建树时可能会建成一个长长的链比如依次插入key值12345。则建出来的二叉搜索树会是一条长链。这样不利于查找搜索。为了解决这个问题我们可以将二叉搜索树尽量建得平衡一些即限制二叉树与二叉树的所有子树的左右子树的高度差绝对值不能超过1。这样的树就是平衡二叉树。根结点的左右子树的高度差就称作平衡二叉树的平衡因子。即平衡因子左子树高度-右子树高度。
如何保证二叉树平衡
左旋/右旋
如果左子树高度-右子树高度1即平衡因子1那么该怎么办
我们可以将树整体向右“旋转”即右旋。也可以理解为把树的右半部分拉长把左半部分上提。这样就能够使树更加趋近平衡状态。如果平衡因子-1也是同理将树整体向左“旋转”即左旋。也可以理解为把树的左半部分拉长把右半部分上提。
具体操作就是如果左子树高度-右子树高度1那么我们将左子树的根结点作为现在的根节点整体往上提。然后为了保证二叉搜索树依然有序我们将原先的根结点变作现在的根结点的右子树根节点。原先的根节点的左子树变作原先的左子树的右子树。可能有点绕其实就是将树看作三部分[原先根结点的左子树原先的根结点原先根结点的左子树的右子树]这样或许会好理解一点。
代码可能更加直观
//右旋
void R(node* root){node* temproot-l;root-ltemp-r;temp-rroot;updateH(root);updateH(temp);roottemp;
}//左旋
void L(node* root){node* temproot-r;root-rtemp-l;temp-lroot;updateH(root);updateH(temp);roottemp;
}
可以这样想既然左子树变作了根结点那么我原先的根结点的左子树不就空出来了但是不能让它空着所以我们将选左子树的右子树作为原先的根节点的左子树因为左子树上的结点包括他的右子树都要小于原先的根结点所以这样换了之后能够依然有序。那左子树变作了根节点他的右子树又被原先的根结点抢走了他现在的右子树岂不是也空出来了没事让原先的根结点作你的右子树呗。于是这样调整后二叉树依然有序且平衡。 左右双旋/右左双旋
那么只需要这样左旋/右旋一次操作就能保持二叉树平衡嘛
不一定考虑一种情况左子树高度-右子树高度1并且左子树的右子树高于左子树的左子树那么我们进行一次右旋操作后是怎样的我们会发现由于左子树的右子树在进行右旋操作后变成了现在的右子树的左子树。深度不变那么也就意味着现在的左右子树的高度差变成了原先的左子树的左右子树高度差1因为左子树高度提高了所以1那么还不是高度差一样超过了1嘛。所以遇到这种情况我们不能直接进行右旋需要对左子树先进行一次左旋后调整左子树的左右子树高度差保证左子树的左子树高于或等于右子树再对整体进行右旋。这样的操作就叫做左右双旋。反之如果是左子树高度-右子树高度-1并且右子树的左子树高于右子树的右子树那么我们就需要进行右左双旋操作。这个操作只需要在进行维护平衡时判定一下就行。
代码
看代码更加直观
树的结构
struct node{int val;int h;//多出一个高度属性node* l;node* r;node(int x):val(x),h(1),l(nullptr),r(nullptr){}
}; 树的高度与平衡因子
//高度
int getH(node* root){if(rootnullptr)return 0;return root-h;
}
void updateH(node* root){root-hmax(getH(root-l),getH(root-r))1;
}
//平衡因子
int getB(node* root){return getH(root-l)-getH(root-r);
}
左/右旋
//右旋
void R(node* root){node* temproot-l;root-ltemp-r;temp-rroot;updateH(root);updateH(temp);roottemp;
}//左旋
void L(node* root){node* temproot-r;root-rtemp-l;temp-lroot;updateH(root);updateH(temp);roottemp;
}
平衡维护
//维护树的平衡
void keepB(node*root){if(getB(root)1){if(getB(root-l)0)L(root-l);//如果先进行左旋R(root);}else if(getB(root)-1){if(getB(root-r)0)R(root-r);//如果先进行右旋L(root);}
}
构建树
//插入结点
void insert(node* nod,int val){if(nodnullptr){nodnew node(val);return ;}if(valnod-val){insert(nod-l,val);updateH(nod);keepB(nod);}else {insert(nod-r,val);updateH(nod);keepB(nod);}
}
