搜索二叉树进阶之AVL树

本文主要是介绍搜索二叉树进阶之AVL树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

二叉搜索树（BST）是一种基础的数据结构，能够高效地进行搜索、插入和删除操作。然而，在最坏的情况下，普通的BST可能会退化成一条链表，导致操作效率降低。为了避免这种情况，出现了自平衡二叉搜索树，AVL树就是其中的一种。

一、什么是AVL树？

AVL树是Adelson-Velsky和Landis在1962年发明的一种自平衡二叉搜索树。它的特点是通过对树进行旋转操作来保持平衡，以确保在最坏情况下，树的高度仍然是O(log n)，从而保证插入、删除和查找操作的时间复杂度都是O(log n)。

1.1 AVL树的平衡因子

AVL树的核心概念是平衡因子（Balance Factor）。对于树中的任意节点，平衡因子定义为其右子树高度减去左子树高度的值（其实左右都可以，只要保证左右子树的高度差的绝对值小于等于1就行）。即：

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

为了保证AVL树的平衡，平衡因子的取值必须是-1、0或1。一旦某个节点的平衡因子超出这个范围，就需要进行旋转操作来恢复平衡。（旋转操作后续讲解）

2.2 AVL树平衡因子的更新

我们规定，当一个节点的右子树高度增加时，此时平衡因子就++，当他的左子树节点增加，该节点的平衡因子就--。

于是我们就会遇见以下三种情况：

1、平衡因子更新为0：

这说明之前的平衡因子为-1或者1，都有过高度差值，但此次插入导致差值为0，两边子树高度相同。所以不需要再继续向父节点检查。

2、平衡因子更新为-1或者1：

这说明之前的平衡因子为0（不可能为-2或者2，因为说明插入前就不是AVL树了），此次插入将之前平衡的高度差再次拉上差距，我们需要继续向上检查当前节点的父节点，是否会出现平衡因子异常。并且，若该节点为父节点的左子节点，就让父节点平衡因子--，否则让其++。

3、平衡因子为-2或者2：

这后面插入之后已经不是一个AVL树了，我们需要对该异常节点进行旋转操作。

二、AVL树的旋转

1、左单旋：

以这个抽象图为例，Parent的左子树高度为h，我们命名为a，subR为Parent的右子树，subR左右子树的高度一开始都是h，我们分别命名为b,c。

如果要对Parent进行左旋，那么此时a，b，c的高度都必须为h，并且c子树必须为满二叉树（如果不是，那么插入到空缺的叶子结点，高度不变，高度差仍然为1），否则Parent节点不能满足两边子树高度差绝对值大于1的条件。

此时只要在c子树上插入任意一个结点，都会使c的高度变为h+1，导致subR的高度差为1，根据上文，这会导致继续向上检查父节点，（父节点原本平衡因子为1），更新后为2，由于两个节点的平衡因子分别为2,1，同号单旋，异号双旋，所以需要对Parent节点进行左单旋。

具体方法就是将subR的左子树赋给Parent的右子树，让Parent的父节点指向subR节点。

我们以一个比较理解的例子为例：

在这个例子中，h为0，我们插入一个C节点到B节点的右子树，就会导致A节点的平衡因子出现问题，需要进行左旋操作。

随后我们将b的左子树给A的右子树（因为这里B的左子树为空，所以就没体现出来），随后让A的父节点变为B的父节点（在这里要判断A为他父节点的什么子树，左还是右，随后给B相应的身份）。

最后不要忘记更新平衡因子为0.

代码实现：

（我们以这样的定义为背景（后面的代码一样））

：

template<class T, class K>
struct AVLTreeNode
{AVLTreeNode(const pair<T, K>& kv):_kv(kv), parent(nullptr), left(nullptr), right(nullptr), _bf(0){}AVLTreeNode<T, K>* right;AVLTreeNode<T, K>* left;AVLTreeNode<T, K>* parent;pair<T, K> _kv;int _bf;
};template<class T, class K>
class  AVLTree
{typedef  AVLTreeNode<T, K> Node;
private:Node* _root;
};

parent指向父节点，_bf为平衡因子，_kv为存储的数据

本文为旋转的介绍，所以AVL树的删除插入一律跳过，想看的朋友可以在评论区留言，我也许会单独发一篇AVL树的模拟实现讲解。

void RotateL(Node* Parent)
{Node* pParnet = Parent->parent;//指向Parent的父节点Node* subR = Parent->right;//subR节点Node* subRL = subR->left;//subRL节点，指向等会交给Parent的右子树的节点//先把subRL给Parent的右子树Parent->right = subRL;if (subRL)//判断subRL是否为空{//不为空时要更新subRL的父节点subRL->parent = Parent;}//随后判断Parent的父节点是否为空，为空就说明Parent为当前树的根节点。if (pParnet == nullptr){_root = subR;subR->parent = nullptr;//进行更新，根节点替换为subR}else{//不为空if (pParnet->left = Parent){//Parent为pParent的左子树节点pParnet->left = subR;}else{ppParent->right = subR;}subR->parent = pParnet;//更新subR的父节点}//旋转结束后，更新平衡因子Parent->_bf = subR->_bf = 0;//进行左旋的条件是，Parent的平衡因子一开始为2，subR平衡因子为1，二者同号且为正，进行左单旋
}

按照一开始讲解的逻辑按部就班的书写代码就行，注意的是一开始传递的参数只有一个Parent节点,我们需要提前创建指针指向subR,subRL,pParent。

2、右单旋

与左单旋相对应的就是右单旋，他就像是左单旋的轴对称一样。

此时只要对a进行插入（a必须为满二叉树），就会触发连续向上的平衡因子更新检查，一直更新到subL为-1，随后向上导致Parent平衡因子为-2 。

同号单旋，异号双旋，由于都是负数，就对Parent进行右单旋。

一样的逻辑，先让Parent的左子树指向subL的右子树节点，随后让Parent的父节点成为subL的父节点。

代码演示：

	void RotateR(Node* Parent){Node* pParent = Parent->parent;Node* subL = Parent->left;Node* subLR = subL->right;Parent->left = subLR;if (subLR)//subLR是否为空{subLR->parent = Parent;}if (pParent == nullptr)//pParent是否为空{_root = subL;subL->parent = nullptr;}else{if (pParent->left = Parent){pParent->left = subL;}else{pParent->right = subL;}subL->parent = pParent;}subL->_bf = Parent->_bf = 0;}

3、右左双旋

我们之前只分析了二者平衡因子同号的情况，倘若Parent平衡因子为2，子树平衡因子为-1，或者Parent平衡因子为-2，子树平衡因子为1的时候，又该怎么办呢？

我们发现倘若在进行单项旋转的话，avl树仍然不会保持平衡。这时候就就需要进行双旋了。

由于Parent为2，子树为-1，异号进行左右双旋，先对子树进行左旋，再对Parent进行右旋。

注意，此时要更新旋转后的平衡因子，结果与subRL的平衡因子有关系，倘若subRL为-1，说明Parent的最后平衡因子为0，两个子树高度都为h，而subR的平衡因子为1，因为右子树高度为h，左子树高度为h-1。

代码演示如下：

void RotateRL(Node* Parent)
{Node* subR = Parent->right;Node* subRL = subR->left;int bf = subRL->_bf;//此时的subRL不可能为空，因为a的高度为h，bc高度为h-1，d高度为h，要想旋转，subRL必须存在。//或者说，subRL至少也是那个新插入的节点即：h为0，h-1代表subRL就是新插入的节点//我们这里可以复用之前写的单旋代码：RotateR(subR);RotateL(Parent);if (bf == 0){//说明subRL就是新插入的节点subR->_bf = subRL->_bf = Parent->_bf = 0;}else if (bf == -1){//插入在subRL的左树上Parent->_bf = subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){Parent->_bf = -1;subR->_bf = subRL->_bf = 0;}else{assert(false);//说明出现了其他情况，报错就行了}
}

注意，在复用之前单旋代码前，我们必须先保存当前subR，subRL的节点指针，并且知道subRL的平衡因子大小，这对我们更新最后的平衡因子有帮助。

4、左右双旋

如图，左右双旋也是右左双旋的翻版，思路只能说是差不了多少。

	void RotateLR(Node* Parent){Node* subL = Parent->left;Node* subLR = subL->right;int bf = subLR->_bf;RotateL(subL);RotateR(Parent);if (bf == 0){subL->_bf = subLR->_bf = Parent->_bf = 0;}else if (bf == 1){Parent->_bf = -1;subL->_bf = subLR->_bf = 0;}else if (bf == -1){subL->_bf = 1;subLR->_bf = Parent->_bf = 0;}else{assert(false);}}