当前位置：首页 > news >正文

AVLTree 旋转笔记(根据平衡因子插入的公式，贼好理解)

news 2025/8/15 9:06:26

平衡因子

avltree是一棵每个节点的左右子树的高度差不超过1的二叉树搜索树，对于avltree最重要的就是对平衡因子的控制。

对于旋转我们重点要注意的是三个节点，以左旋举例，需要注意的就是parent，subr，subrl。而旋转的方式有四种，我们只需要根据对应的平衡因子来去判断该怎样旋转就行。

左旋

对于左旋，我们可以用一张图来概括

这里的h是指高度>=0的avl树，这里只适用于parent平衡因子为2，subr平衡因子为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平衡因子为-2，subl平衡因子为-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;}

右左双旋

subl，sublr写错了，该市subr，subrl
这里只是一种情况

先将 subr 右旋，再将parent左旋，这里只适用于parent平衡因子为2，subr平衡因子为-1的情况。
这里的平衡因子更新其实是要根据subrl来定的：
因为subr为-1时subrl肯定是不为空的，这里也有一个总结，当然可以当一个公式记住就行。
代码：

void rotateRL(avltnode* parent)
{avltnode* subr=parent->_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平衡因子为-2，subl平衡因子为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;}}