网站建设网络推广广告语,高级ppt模板免费下载,wordpress 图片站主题,中级平面设计师证书有用吗AVL树
平衡二叉树的缺点 由于平衡二叉搜索树的search(), insert(),remove()接口的运行时间与二叉树的高度成正比,所以若不能有效控制树高, 从平均复杂度来看,二叉平衡搜索树并不能让人满意
理想平衡 二叉树的性能取决于树的高度,只有当左右子树的高度接近时才能达到理想平衡…AVL树
平衡二叉树的缺点 由于平衡二叉搜索树的search(), insert(),remove()接口的运行时间与二叉树的高度成正比,所以若不能有效控制树高, 从平均复杂度来看,二叉平衡搜索树并不能让人满意
理想平衡 二叉树的性能取决于树的高度,只有当左右子树的高度接近时才能达到理想平衡, 高度为o(logn); 就比如完全二叉树与满二叉树
AVL树 由于从平常状态转变为理想状态下,所耗费的资源较多, 所以就设定适度的平衡标准, 就此提出AVL树, AVL树可保证树的高度始终保持在O(logn)内 AVL树的平衡标准: 任一节点都具有平衡因子(其值balFac(v) height(lc(v)) - height(rc(v)) )的绝对值不能超过1 AVL继承平衡二叉搜索树, 对search(), insert(), remove()接口进行重写
//以下宏定义用于简化节点的平衡性判断
//stature表示当前节点的高度
#define Balanced(x)(stature((x).lChild) stature((x).rChild)))//理想状态
#define BalFac(x)(stature((x).lChild) - stature((x).rChild))//平衡因子
#define AVBalanced(x) ((-2BalFac(x)) (BalFac(x)2 ))//AVL树条件
注:空树的高度取-1, 单节点子树高度取0 例: 如图所示节点的平衡因子(皆为左子树高度-右子树高度) 节点的插入以及删除都将影响节点的平衡度
重平衡 在插入x后, AVL失衡, 可沿x出发向上寻找首次出现失衡的节点, 将其确定为祖父节点(g(x)),然后根据g(x),找到g(x)的儿子节点, 孙子节点, 将其设置为p,v, 由于原树为平衡的,所以在整个向上查找g的过程只需O(logn)的时间 ; 针对g, p, v三个节点的位置进行zig(顺时针旋转节点,使后代上升为父节点), zag(逆时针)旋转,用于重平衡
//将确定p, v的过程写为宏定义;
//根据插入过程不平衡的出现可得查找原则:左右孩子取高度更高的为p,左右孩子等高,取父亲同侧,v同上
//根据上图可知2为g,p为-1,v为1
#define tallerChild(x) ( stature((x)-lChild)stature((x)-rChild))?(x)-lChild:( (stature((x)-rChild)stature((x)-lChild))?(x)-rChild:((x-parent-lChild)?x-lChild:x-rChild)))
//每一层的比较对应着查找p,v
单旋: 只执行zig/zag旋转,且执行一次 双旋: 旋转过程中即包含zig又包含zag
//zig简述
g(x)-lChildp-rChild;
p-Child-parentg(x);//将孩子节点旋转
p-parentg(x)-parent;
g(x)-parentp;//将父节点旋转
//zag原理同上插入过程中的重平衡 当节点x插入后, 可能导致二叉树结构一系列节点发生不平衡现象(也就是重心偏向一边), 但是经过局部旋转后将可能导致一系列的恢复平衡
删除过程中的重平衡 当节点x删除后, 只会导致局部的节点发生不平衡现象, 当对局部的不平衡进行zig/zag调整时, 局部子树的高度将有可能降低,又有可能导致上一层的祖先发生不平衡,因此需要不断向上遍历,发现一个失衡的祖先则将其旋转至平衡状态,直到更新到没有出现不平衡现象
统一重平衡算法 在删除与插入的过程中都涉及到zig,zag旋转,于是可将插入,删除操作统一,为避免通过zig,zag旋转出现的繁琐,于是提出了34重构的方式 34重构: 直接传入g,p,v三个节点以及这三个节点对应的左右子树,对其进行全部重新连接,由此可覆盖所有的旋转操作
templatetypename TBinNodePosi* BSTT::connect34(BinNodePosi* a,BinNodePosi* b,BinNodePosi* c, BinNodePosi* T0,BinNodePosi* T1,BinNodePosi* T2,BinNodePosi* T3){a-lChildT0; if(T0) T0-parenta;a-rChildT1; if(T1) T1-parenta;updateHeight(c);//更新数的高度c-lChildT2; if(T2) T2-parentc;c-rChildT3; if(T3) T3-parentc;updateHeight(c);//更新数的高度b-lChilda; if(T0) a-parentb;b-rChildc; if(T2) c-parentb;updateHeight(c);//更新数的高度return b;//对传入的节点进行重连操作
}
//针对zig,zag旋转模式,传入不同的参数调用connect34
templatetypename TBinNodePosi* BSTT::rotateAt(BinNodePosi* v){BinNodePosi* pv-parent,gp-parent;if(g-lChildp)//p为左孩子,zig旋转if(p-lChildv){//v为左孩子,执行zig,zigp-parentg-parent;//向上连接return connect34(v,p,g,v-lChild,v-rChild,p-rChild,g-rChild);}else{//zig,zag双旋v-parentg-parent;return connect34(p,v,g,p-lChild,v-lChild,v-rChild,g-rChild);}else //zag旋转if(p-rChildv){//zag,zagp-parentg-parent;//向上连接return connect34(g,p,v,g-lChild,p-lChild,v-lChild,v-rChild);}else{//zag,zig旋转v-parentg-parent;return connect34(g,v,p,g-lChild,v-lChild,v-rChild,p-rChild);}}
insert实现
//将关键码e插入合适的位置,然后调整平衡树状态,使其平衡
templatetypename TBinNodePosi* AVLT::insert(const T e){BinNodePosi* xsearch(e);if(x) return x;//节点e已存在树中xnew BinNodeT(e,_hot);_size;//_hot查找过程中指向e应该存在的位置,插入过程将导致某一祖先出现不平衡for(BinNodePosi* g_hot;g;gg-parent){//从x的位置向上查找检查每个祖先,直到出现不平衡的祖先if(!AVlBalanced(*g)){//发现失衡的祖先调用34重构使之平衡FromParentTo(*g)rotateAt(tallerChild(tallerChild))//tallerChild查找p,v的位置break; }elseupdateHeight(g);//向上查找顺便更新当前g的高度}return x;//返回更新后的结果
}
remove的实现 search查找出要删除的节点位置,调用remove(),查找失衡的局部子树, 调用34重构使其恢复平衡,remove的实现与insert差不多, 区别只是在于,remove相比insert多调用一次remove函数
注:经过上述操作后, insert,remove复杂度将降低到O(logn)的状态
