个人主页：仍有未知等待探索-CSDN博客

专题分栏：C++

目录

一、概念

二、平衡因子

三、操作

插入

旋转

左单旋

右单旋

左右双旋

右左双旋

---

一、概念

二叉平衡搜索树又称AVL树，是一种特殊的二叉搜索树。一般的二叉搜索树在遇到数据有序时，查找的效率比较的低。

而二叉平衡搜索树，为了防止有这种极端的情况出现，其保证了任一节点的左右子树的高度差不超过1，通过控制高度，使查找的次数降低。 

二、平衡因子

二叉平衡搜索树，在对节点的结构进行定义的时候多添加了一个平衡因子的变量（bf），用来判断树是否是平衡的。

平衡因子 = 右子树的高度 - 左子树的高度

平衡因子的取值为 ：0、+1、-1、+2、-2

当平衡因子为+2、-2的时候，代表了这棵树需要进行调整。

三、操作

插入

插入的步骤就是这些。

为什么调节完，平衡因子为1、-1的时候要向上进行调整？ 

如果调节完，平衡因子为1、-1，则在没有调整的时候，平衡因子为0。新增了一个结点之后，高度发生了变化。以当前节点为根节点的子树的高度发生了变化，则以当前节点为其中的一个节点的子树的高度也同样发生了变化，所以需要进行调整。

旋转

对于要通过旋转进行调节平衡因子的情况不细分的话，有4种：左单旋、右单旋、左右双旋、右左双旋。

注意：在进行旋转的时候，对于每个节点的指针变化，要特别的细心。

节点中有三个指针，一个指向左孩子、一个指向右孩子、另外一个指向双亲。

旋转点：进行旋转的一个基准点。就比如左单旋的话，parent就是旋转点。

左单旋

左单旋变换：subrl 变成 parent 的右子树，parent 成为 subr 的左子树。

直接看图变换是不难，但是写代码就会有很多的坑（指针的变换）。

// 左单旋
// 参数是图中的parent，也称为旋转点
void RotateL(node* parent)
{
	node* subr = parent->right;
	node* subrl = subr->left;
    
    // subrl 成为 parent 的右子树 
	parent->right = subrl;
	if (subrl)
		subrl->parent = parent;

	subr->left = parent;
	node* pparent = parent->parent;

	parent->parent = subr;

	if (_root != parent)
	{

		if (pparent->left == parent)
		{
			pparent->left = subr;
		}
		else 
		{
			pparent->right = subr;
		}
		subr->parent = pparent;
	}
	else
	{
		_root = subr;
		subr->parent = nullptr;
	}

	parent->bf = subr->bf = 0;
}

右单旋

如图是右单旋的情况。

右单旋的变换：sublr 变成 parent 的左子树，将parent 变成 subl 的右子树。

直接看图变换是不难，但是写代码就会有很多的坑（指针的变换）。

// 右单旋
// parent 为旋转点
void RotateR(node* parent)
{
	node* subl = parent->left;
	node* sublr = subl->right;
    
    // sublr成为parent的左子树
	parent->left = sublr;
    // 如果sublr是空的话，不需要更新它的双亲结点，因为空指针不能进行解引用
	if (sublr)
		sublr->parent = parent;
    
    // parent成为subl的右子树
	subl->right = parent;
    // 记录一下这个子树的根节点的双亲结点
	node* pparent = parent->parent;
    
    // 更新parent的双亲节点
	parent->parent = subl;
    
    // 判断该子树的根节点是不是整个子树的根节点
    // 不是的话，也需要更新该子树的根节点的双亲结点
	if (_root != parent)
	{
		
		if (pparent->left == parent)
		{
			pparent->left = subl;
		}
		else 
		{
			pparent->right = subl;
		}
		subl->parent = pparent;
	}
	else
	{
		_root = subl;
		subl->parent = nullptr;
	}
    
    // 更新平衡因子
	parent->bf = subl->bf = 0;
}

左右双旋

左右双旋的变换：先以 subl 为旋转点进行左单旋，然后再以 parent 为旋转点进行右单旋。

注意：1、指针的变换 2、注意新的节点插入在 b 子树的左子树和右子树的时候，平衡因子的变化。

 

// 左右双旋
// 传参传的节点还是parent
void RotateLR(node* parent)
{
	node* psubl = parent->left;
	node* psublr = psubl->right;
    
    // 记录之前的 sublr 节点的平衡因子
	int bf = psublr->bf;
    
    // 先以 subl 为旋转点进行左单旋
	RotateL(parent->left);
    // 然后再以 parent 为旋转点进行右单旋
	RotateR(parent);
    
    // 在完成旋转调整平衡后，在对该子树的平衡因子进行变换
    // 至于为什么平衡因子等于这些值，可以去看看我画的图然后进行对比
    // 还是比较清楚的
	if (-1 == bf)
	{
		psubl->bf = psublr->bf = 0;
		parent->bf = 1;
	}
	else if (1 == bf)
	{
		parent->bf = psublr->bf = 0;
		psubl->bf = -1;	
	}
	else if (0 == bf) // 如果在旋转之前的平衡因子就是为0，则调整完之后的平衡因子都是0
	{
		parent->bf = psubl->bf = psublr->bf = 0;
	}
	else // 这种情况一般是没有的，如果有，则是你写的AVL树是有错误的
	{
		assert(false);
	}
}

 

右左双旋

右左双旋的变换：先以 subr 为旋转点进行右单旋，然后再以 parent 为旋转点进行左单旋。

注意：1、指针的变换 2、注意新的节点插入在 c 子树的左子树和右子树的时候，平衡因子的变化。

 

// 右左双旋
void RotateRL(node* parent)
{
	node* psubr = parent->right;
	node* psubrl = parent->left;
	int bf = psubrl->bf;
    
    // 先以subr为旋转点进行右单旋
	RotateR(parent->right);
    // 再以parent为旋转点进行左单旋
	RotateL(parent);
    
    // 更新平衡因子
	if (1 == bf)
	{
		psubr->bf = psubrl->bf = 0;
		parent->bf = -1;
	}
	else if (-1 == bf)
	{
		parent->bf = psubrl->bf = 0;
		psubr->bf = 1;
	}
	else if (0 == bf)
	{
		parent->bf = psubr->bf = psubrl->bf = 0;
	}
	else 
	{
		assert(false);
	}
}