【搜索结构】AVL树的学习与实现

什么是AVL树

AVL树的定义

插入函数的实现

左单旋和右单旋

左右双旋与右左双旋

什么是AVL树

AVL树实际上就是二叉搜索树的一种变体，我们都知道二i叉搜索树可以将查找的时间复杂度提升到O(logn)，极大提升搜索效率。但是在极端情况下，当按顺序向树插入节点时，二叉树严重不平衡，相当于退化成了链表，此时查找的时间复杂度就变为了O(n)，这并不是我们希望看到的。

那么有没有什么方式可以让二叉搜索树保持一定的平衡性从而不至于导致查找效率严重降低呢？AVL树也就是高度平衡二叉树给出的解决方案是：

1. 二叉树的每个节点都有一个平衡因子，平衡因子等于左子树高度减右子树高度的值

2. 平衡因子的绝对值不能超过1

3. 当插入或删除节点导致平衡因子绝对值超过1时，进行旋转

AVL树的定义

让我们来思考一下，要实现前面描述的功能，AVL树的单个节点应该有哪些成员变量呢？

1. 首先肯定要有左右子树的节点

2. 然后为了旋转时能够找到父亲，我们还需要存父亲节点

3. 为了确保平衡，我们要将左右高度差作为平衡因子保存

4. 最后还有搜索要用到的键值对

AVL树节点类定义：

template<class K, class V>
struct AVLTreeNode
{// 由于插入节点时要向上更新，所以使用三叉链结构AVLTreeNode<K, V>* left;AVLTreeNode<K, V>* right;AVLTreeNode<K, V>* parent; pair<K, V> _kv; // 键值int _bf; // 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv), left(nullptr),right(nullptr),parent(nullptr),_bf(0){}
};

那么，AVL树的定义就应该是：

template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

插入函数的实现

让我们先明确一下AVL树插入一个节点要做的事：

1. 按照二叉搜索树的规则找到插入位置进行插入

2. 根据左右高度差得到平衡因子

3. 当平衡因子绝对值大于1时进行旋转处理

首先二叉树搜索规则就是：当插入节点的键小于当前节点的键时，和当前节点的左子树进行比较；当插入节点的键大于当前节点的键时，和当前节点的右子树进行比较；否则说明插入节点的键已经存在，这不符合二叉搜索树的规则，直接报错。我们按照这个规则找到可以插入的位置然后将新节点插入。

插入完成之后，我们开始更新平衡因子，当新节点位于父亲的左边时，bf减1；当位于父亲的右边时，bf加1。修改完父亲的平衡因子后，进行判断：

1. 如果当前父亲平衡因子值为0，说明高度差没有改变，不需要进行处理，直接break即可。

2. 如果当前父亲平衡因子值为1/-1，说明插入导致高度差改变了，这可能会导致祖先节点的平衡因子绝对值超过1，所以需要继续往上更新祖先的平衡因子

3. 如果更新后的祖先的平衡因子绝对值超过1，就需要进行旋转处理

为了更直观地理解这个过程，让我们来看一个简单的例子：

插入新节点导致祖先失去平衡：

通过旋转，使AVL树恢复平衡

我们可以看到，这棵树的根节点平衡因子在插入新节点后，由1变为2，而进行一次左旋之后，平衡因子更新为0，恢复了平衡。

由于旋转涉及到的情况比较多且有一些细节操作，而这只是其中最简单的一种情况，所以我们先写出AVL树插入的基本框架，之后再对各个需要旋转的情况分别进行处理。

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr; // 用于记录插入位置的父亲节点Node* cur = _root; // 用于比较查找到插入位置while (cur){parent = cur;if (kv.first < cur->_kv.first){cur = cur->left;}else if (kv.first > cur->_kv.first){cur = cur->right;}// 搜索二叉树不支持重复key值的情况else{return false;}}// 此时说明已经找到了插入位置,插入新节点cur = new Node(kv);if (kv.first < parent->_kv.first){parent->left = cur;}else{parent->right = cur;}cur->parent = parent; // 记得保持三叉链结构// 更新平衡因子while (parent){if (cur == parent->left){parent->_bf--;}else{parent->_bf++;}// 正好平衡了if (parent->_bf == 0){break;}// 说明需要向上调整else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->parent;}// 在此处进行旋转调整else if (parent->_bf == 2 || parent->_bf == -2){// 旋转处理……}// 说明旋转有问题,不能在|bf|==2时恢复平衡else{assert(false);}}return true;}

左单旋和右单旋

先来看左单旋，如下图所示，是左单旋最简单的情况：

但显然需要左单旋的情况通常会更复杂些，所以我们实现左单旋时，需要考虑具有通用性的情况：

可以发现，我们的左单旋操作似乎只需要让parent的右指向subRL，然后让subR的左指向parent。但大家可别忘了，我们定义AVL树节点时，为了方便向上更新，设计的是三叉链结构，所以还需要更新subRL和parent的父亲节点。除此之外，还需要考虑到parent可能是祖先节点的孩子，所以如果parent是AVL树的根节点：将根节点更新为subR，并将subR的父亲更新为nullptr；如果parent是祖先节点的孩子：则将祖先节点的孩子更新为subR，并将subR的父亲更新为父亲节点。

指针朝向修改完后，我们还需要修改发生高度变化的节点的平衡因子，如上图所示，parent的平衡因子由2变为0，subR的平衡因子由1变为0。

void RotateL(Node* parent)
{// 在修改之前先保存祖父节点Node* grandpa = parent->parent;// 事实上，对于左旋这一情况，我们要修改的只有parent,subR,subRL最多再加个grandpa的指针朝向Node* subR = parent->right;Node* subRL = subR->left;// 进行左旋操作parent->right = subRL;subR->left = parent;// 之后还得把父指针也一起修改了parent->parent = subR;if(subRL)subRL->parent = parent;// 这棵树不是子树if (parent == _root){_root = subR;_root->parent = nullptr;}// 这棵树是子树else{// 是祖父节点的左子树if (grandpa->left == parent){grandpa->left = subR;}// 是祖父节点的右子树else{grandpa->right = subR;}subR->parent = grandpa;}parent->_bf = subR->_bf = 0;}

接下来是右单旋，在局部子树左偏时，我们通过右旋来进行处理：

由于在左单旋部分我们已经详细讲解过了，右单旋其实就相当于反过来，所以就不再讲解一遍了。

	void RotateR(Node* parent){// 在修改之前先保存祖父节点Node* grandpa = parent->parent;// 事实上，对于右旋这一情况，我们要修改的只有parent,subL,subLR最多再加个grandpa的指针朝向Node* subL = parent->left;Node* subLR = subL->right;// 进行右旋操作parent->left = subLR;subL->right = parent;// 之后还得把父指针也一起修改了parent->parent = subL;if (subLR)subLR->parent = parent;// 需要考虑现在调整的这棵树是子树的情况if (parent == _root){_root = subL;_root->parent = nullptr;}else{// 是祖父节点的左子树if (grandpa->left == parent){grandpa->left = subL;}// 是祖父节点的右子树else{grandpa->right = subL;}subL->parent = grandpa;}parent->_bf = subL->_bf = 0;
}

左右双旋与右左双旋

我们还是先来看一个左右双旋的简单例子，可以看到，我们先通过一次左旋，把这棵子树修改为了单纯的左偏，而处理左偏，我们只需要进行一次右旋即可。

再来看更普遍的情况：

事实上，由于我们已经有了左旋和右旋的代码，所以进行双旋时，可以直接复用左旋和右旋函数，所以双旋主要考虑的是如何更新平衡因子。

一共有三种情况：

第一种：60就是新增节点，此时平衡因子全部更新为0

第二种：新增节点向b插入，此时parent的因子为1，其余因子为0

第三种：新增节点向c插入，此时subL的因子为-1，其余因子为0

大家可以自己分别画一下这三种情况，其实自己动手画一下就很好理解了，让我们看代码：

void RotateLR(Node* parent){Node* subL = parent->left;Node* subLR = subL->right;// 啊啊啊，原来是这里错了，调试了一个晚上。。// int bf = parent->_bf;int bf = subLR->_bf;RotateL(parent->left);RotateR(parent);if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}//else//{//	assert(false);//}}

右左双旋和左右双旋完全类似，也是三种情况，其实理解了左右双旋，右左双旋就很好写了！

	void RotateRL(Node* parent){Node* subR = parent->right;Node* subRL = subR->left;// 提前记录修改点的平衡因子int bf = subRL->_bf;// 先右旋RotateR(parent->right);// 再左旋RotateL(parent);if (bf == 0){// 自己就是新增节点parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){// 新增节点位于subRL的左子树parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){// 新增节点位于subRL的右子树parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}//else//{//	assert(false);//}}