wordpress手机端网站模板下载,黑马程序员项目库,微信h5页面模板,旅行社erp管理系统使用平衡因子
avltree是一棵每个节点的左右子树的高度差不超过1的二叉树搜索树#xff0c;对于avltree最重要的就是对平衡因子的控制。 对于旋转我们重点要注意的是三个节点#xff0c;以左旋举例#xff0c;需要注意的就是parent#xff0c;subr#xff0c;subrl。而旋转的方…平衡因子
avltree是一棵每个节点的左右子树的高度差不超过1的二叉树搜索树对于avltree最重要的就是对平衡因子的控制。 对于旋转我们重点要注意的是三个节点以左旋举例需要注意的就是parentsubrsubrl。而旋转的方式有四种我们只需要根据对应的平衡因子来去判断该怎样旋转就行。
左旋 对于左旋 我们可以用一张图来概括这里的h是指高度0的avl树这里只适用于parent平衡因子为2subr平衡因子为1的情况。 我们需要注意这三者关系的变化以及对应平衡因子的更新。 根据这几点我们就能写出对应的旋转代码 void rotateL(avltnode*parent){//获得对应节点avltnode* subr parent-_right;avltnode* subrl subr-_left;avltnode* parentParent parent-_parent;// 更新parent的右parent-_right subr-_left;//更新subr的右节点subr-_left parent;//更新parent的父节点parent-_parent subr;//判断subrl是否为空节点如果不为空就更新subrl的父节点if (subrl)subrl-_parent parent;//判断parentParent节点是否为空if (parentParent nullptr){//为空说明走到了最上面的节点subr-_parent nullptr;_node subr;}else{//如果没有则判断是要放在左边还是右边。if (parentParent-_left parent)parentParent-_left subr;else if (parentParent-_right parent)parentParent-_right subr;subr-_parent parentParent;}//更新平衡因子subr-_bf parent-_bf 0;}
右旋
右旋也是可以用一张图来概括这里的h是指高度0的avl树这里只适用于parent平衡因子为-2subl平衡因子为-1的情况。 逻辑跟左旋差不了多少代码注释也不过多赘述。 代码 //右旋void rotateR(avltnode* parent){avltnode* subl parent-_left;avltnode* sublr subl-_right;avltnode* parentParent parent-_parent;subl-_right parent;parent-_parent subl;parent-_left sublr;//判断sublr是否为空if (sublr) sublr-_parent parent;//判断parentParent是否为空if (parentParent nullptr){subl-_parent nullptr;_node subl;}else{if (parentParent-_left parent){parentParent-_left subl;}else{parentParent-_right subl;}subl-_parent parentParent;}subl-_bf parent-_bf 0;}
右左双旋
sublsublr写错了该市subrsubrl 这里只是一种情况先将 subr 右旋再将parent左旋这里只适用于parent平衡因子为2subr平衡因子为-1的情况。 这里的平衡因子更新其实是要根据subrl来定的 因为subr为-1时subrl肯定是不为空的这里也有一个总结当然可以当一个公式记住就行。 代码
void rotateRL(avltnode* parent)
{avltnode* subrparent-_right;avltnode* subrl subr-_left;int bf subrl-_bf;rotateR(subr);rotateL(parent);//判断平衡因子if (bf 0){subr-_bf subrl-_bf parent-_bf 0;}else if (bf 1){subr-_bf subrl-_bf 0;parent-_bf -1;}else if (bf -1){subr-_bf 1;subrl-_bf parent-_bf 0;}else//如果都不属于就报错{assert(false);}
}
左右双选
这里只适用于parent平衡因子为-2subl平衡因子为1的情况 也就类似于右左双旋 代码 void rotateLR(avltnode*parent){avltnode* subl parent-_left;avltnode* sublr subl-_right;int bf sublr-_bf;rotateL(subl);rotateR(parent);if (bf 0){subl-_bf parent-_bf sublr-_bf 0;}else if (bf -1){subl-_bf sublr-_bf 0;parent-_bf 1;}else if (bf 1){subl-_bf -1;sublr-_bf parent-_bf 0;}}
总结
其实说avl树很难但是当你根据公式来写这棵树其实他也并不是很复杂。但是最终我们还是要去理解avl树为什么要这样旋转。
