【c++】【数据结构】AVL树

AVL树的定义

AVL树本质是一种搜索二叉树，传统的二叉搜索树我们都有所了解，其在理想情况下也就是接近满二叉树时拥有极高的插入与搜索效率，但是极其的不稳定。AVL树就是针对这种问题而产生的，其名字来源于发明创造他的科学家。AVL树是一种自平衡的二叉搜索树，拥有特定的算法动态维持平衡，避免因插入不平衡而产生的插入搜索效率低下的问题。

AVL树的部分模拟实现

#pragma once#include<iostream>#include<algorithm>using namespace std;template<class Key, class Value>
struct AVL_Node
{typedef AVL_Node<Key, Value> Node;AVL_Node(Key k, Value v):_key(k),_value(v){}Node* _parent = nullptr;Node* _left = nullptr;Node* _right = nullptr;Key _key = 0;Value _value = 0;int BFactor = 0;//平衡因子
};template<class Key, class Value>
class AVL
{
public:typedef AVL_Node<Key, Value> Node;bool find(Key a){return _find(root, a);}bool insert(Key a, Value b){if (!root)//树判空{root = new Node(a, b);return true;}Node* cur = root;Node* parent = nullptr;while (cur)//找位置{if (cur->_key == a) return false;parent = cur;if (cur->_key > a) cur = cur->_left;else cur = cur->_right;}if (parent->_key > a)//插入{parent->_left = new Node(a, b);cur = parent->_left;cur->_parent = parent;//parent->BFactor++;}else{parent->_right = new Node(a, b);cur = parent->_right;cur->_parent = parent;//parent->BFactor--;}Node* son = nullptr;while (parent){if (parent->_key > cur->_key){parent->BFactor++;}else{parent->BFactor--;}if (parent->BFactor == 0) break;if (parent->BFactor == 2 || parent->BFactor == -2){if (parent->_key > cur->_key){if (son && (cur->_key > son->_key)) Rrotation(cur);else LRrotation(cur);}else{if (son && (cur->_key < son->_key)) Lrotation(cur);else RLrotation(cur);}break;}son = cur;cur = parent;parent = parent->_parent;}return true;}void inorder()//中序打印{_inorder(root);}int high()//树的高度{return high(root);}void check()//检查结点平衡{_check(root);}private:void _check(Node* cur){if (!cur) return;if (high(cur->_left) - high(cur->_right) != cur->BFactor){cout << cur->_key << " : " << cur->BFactor << ", " << high(cur->_left) - high(cur->_right) << endl;}check(cur->_left);check(cur->_right);}int _high(Node* cur){if (!cur) return 0;int releft = high(cur->_left);int reright = high(cur->_right);return releft > reright ? releft + 1 : reright + 1;}void _inorder(Node* cur){if (!cur) return;_inorder(cur->_left);cout << cur->_key << endl;_inorder(cur->_right);}void LRrotation(Node* cur){if (cur->_right->BFactor == 1){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = -1;}else if (cur->_right->BFactor == -1){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 1;cur->_right->BFactor = 0;}else //cur的子结点是刚插入的情况{Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = 0;}}void RLrotation(Node* cur){if (cur->_left->BFactor == 1){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = -1;}else if (cur->_left->BFactor == -1){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 1;cur->_right->BFactor = 0;}else //cur的子结点是刚插入的情况{Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = 0;}}void Lrotation(Node* cur){Node* parent = cur->_parent;Node* pparent = parent->_parent;Node* cur_left = cur->_left;parent->_right = cur_left; //左右节点更新cur->_left = parent;if(cur_left) cur_left->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{root = cur;cur->_parent = nullptr; //解耦}cur->BFactor = 0; //平衡因子的更新parent->BFactor = 0;}void Rrotation(Node* cur){Node* parent = cur->_parent;Node* pparent = parent->_parent;//Node* son = cur->_left;Node* cur_right = cur->_right;parent->_left = cur_right; //左右节点更新cur->_right = parent;if (cur_right) cur_right->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{root = cur;cur->_parent = nullptr; //解耦}cur->BFactor = 0; //平衡因子的更新parent->BFactor = 0;}bool _find(Node* root, Key a){if (!root) return false;if (root->_key == a) return true;if (root->_key > a) return _find(root->_left, a);return _find(root->_right, a);}Node* root = nullptr;
};

AVL树是相对复杂的数据结构，它的核心算法是插入和删除函数，删除函数比起插入函数还要再难上一点，笔者能力有限，只对插入函数进行了实现。

平衡因子的引入

对于AVL树，首先我们还是要明确，其本质还是一颗二叉搜索树，所以先是要对其结点类进行定义。这里笔者采用的还是经典的Key-Value模型，抛开普通二叉搜索树所有的成员变量之外，笔者还定义了一个平衡因子，这是AVL树的关键。前面我们也说过，AVL树是一个自平衡的二叉搜索树，在弄清楚平衡是如何保持的之前，我们先应该明白AVL如何定义平衡与不平衡的。对于平衡二叉树来说，其最理想的状态无疑是满二叉树的状态，但是满二叉树不是想有就有的，只有特定的结点数量才能有满二叉树，很多情况下我们只能追求类似完全二叉树的状态也就是确保倒数第二层全满，而最后一层没满的情况。所以对于平衡状态的定义我们不应该过于严格，AVL树将每一个结点的左右子树的高度差不超过1的情况定义为平衡状态，反之就是不平衡状态。因此，我们可以在每个结点中都引入一个平衡因子，当然也有一些AVL树的实现是没有定义平衡因子的，那样的话就需要通过其他的方式得出左右子树的高度差，不过平衡因子这样的方式很方便，有很多人用。在每一个AVL树的结点中的平衡因子只有三种可能值：0，1，-1。用来表示左右子树相等，左子树的高度比右子树的高度大1，右子树的高度比左子树的高度大1这三种情况。如果出现2，-2这两种情况就要使用算法及时维护，保持平衡因子在正常范围内。

平衡因子的向上调整

AVL树的结点插入部分与普通二叉搜索树一样，但是在插入之后需要对平衡因子进行更新，如何更新呢？先来看一下这两种情况，

对于结点的插入，大致可以分为以上这两种，即对一个叶子结点插入的情况和对于一个有子结点的结点插入的情况。对于第一种情况，其在插入之后对于其父结点的平衡因子毫无疑问是要进行更新的，但我们要考虑的不仅仅是这个父结点，还有父结点的一系列祖宗结点，即从父结点出发向上直到根节点的路径上的所有节点，因为结点的插入会影响树的高度，进而会影响所有的祖宗结点，其他节点则不会受影响。说白了，平衡因子是左右子树之差，所以能影响它的只有子树高度的改变，子树没有插入结点，子树高度就不会变，平衡因子也就不会改变。那么这里究竟会不会呢？答案是不会的，虽然插入了结点，但是这颗子树的高度没有改变，还是2，高度没有变化也就不会影响它的祖宗节点。对于第二种情况呢？答案是会的，因为这种插入方式改变了树的高度，即将树的高度由1变成了2，这时高度的改变势必会影响它的祖宗结点。所以我们应该继续向上调整父节点的父节点，为了方便向上调整，结点中也引入了父结点的指针。那么究竟如何调整呢？我们再看向下面三张图，

在不考虑左右结点搭配的情况下，结点更新时就会遇到这三种情况，第一种情况树的高度没有发生变化，所以就不用再向上调整了；第二种树的高度发生了改变，还需要再次调整；第三种情况不仅树的高度发生了变化，两树高度之差还超过了1，需要算法来调整。看完了这么多种情况，我们会发现情况真的很多很复杂，如何总结并转换成代码呢？首先我们明白，当树的高度不再发生变化时，平衡因子的向上调整就该结束了，如何判断这种情况呢？我们发现，由于二叉树只有两棵子树，且AVL树的结点左右子树高度差不超过1，所以树的高度不发生变化的情况只有结点的左右子树高度差正好由1或-1变成0时，树的高度不会发生变化，平衡因子的向上调整在此终止。当AVL树的结点的左右子树高度差由0变成1或者-1时，树的高度会发生变化，平衡因子需要继续向向上调整。当AVL树的结点的左右子树高度差由1或者-1变成2或者-2时，树的平衡已经被破坏了，需要动用算法来维护了，算法我们之后说。总结一下就是父节点的平衡因子改变后是0就结束，是1或-1就继续向上调整，是2或-2就动用算法。至此，我们就完成了AVL树插入函数的大框架，

bool insert(Key a, Value b)
{if (!root)//树判空{root = new Node(a, b);return true;}Node* cur = root;Node* parent = nullptr;while (cur)//找位置{if (cur->_key == a) return false;parent = cur;if (cur->_key > a) cur = cur->_left;else cur = cur->_right;}if (parent->_key > a)//插入{parent->_left = new Node(a, b);cur = parent->_left;cur->_parent = parent;//parent->BFactor++;}else{parent->_right = new Node(a, b);cur = parent->_right;cur->_parent = parent;//parent->BFactor--;}Node* son = nullptr;while (parent){if (parent->_key > cur->_key){parent->BFactor++;}else{parent->BFactor--;}if (parent->BFactor == 0) break;if (parent->BFactor == 2 || parent->BFactor == -2){// 平衡因子维护算法}son = cur;cur = parent;parent = parent->_parent;}return true;
}

首先我们先对树进行判空，如果树为空，那最简单了，直接将要插入的结点设为根结点返回就行了。树不为空的话，我们就要先找到要插入的位置插入。之后进入循环，对父结点的平衡因子进行更新，插入的是左结点的就对父结点++，插入的是右结点的话就对父结点–。之后根据更新后的父结点的平衡因子的值进行相应操作，如果是1或-1，就将cur指针指向父结点，进入下一个循环对父结点的父结点再次重复相应的操作，是0就结束循环，是2或-2就用算法。这样，剩下的就只有算法了，这也是最难的一部分。

旋转算法

单旋算法

首先我们应该明确，在AVL树中，平衡因子最多也就是2或-2，是不会有3或-3，4或-4这种情况的，因为在插入时遇到平衡因子变成2或-2时就会及时调用算法调整，如果出现了大于2或小于-2的情况，就是自己写错了，在平衡因子为2或-2时没有调整。所以，我们在思考不平衡的情况时只要考虑左右子树之差为2或-2的情况就行。

右单旋

我们看向下面这一张图，

这就是一张典型的不平衡的AVL树，因为其根结点的左子树高度为2，右子树的高度为0，左右子树高度之差为2。那么其实这张图就可以变成，

这张图的h为0时就等于上面这张图，它代表的不只是一张图，是一种情况，比起第一张图，它更具有普适性，对于这种树不平衡的情况，就要使用旋转函数的单旋函数中的右单旋了。

说是旋转函数，到底应该怎么做呢？笔者做了下面这张图，

这种因为左子树过高将父结点向下压达到左右平衡的效果，就像整个树向右旋转了一样，这种做法叫做右单旋。右单旋的实现函数如下，

void Rrotation(Node* cur)
{Node* parent = cur->_parent;Node* pparent = parent->_parent;//Node* son = cur->_left;Node* cur_right = cur->_right;parent->_left = cur_right; //左右节点更新cur->_right = parent;if (cur_right) cur_right->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{root = cur;cur->_parent = nullptr; //解耦}cur->BFactor = 0; //平衡因子的更新parent->BFactor = 0;
}

根据传过来的cur指针算出cur的父结点的指针，爷爷结点的指针以及cur的右子节点的指针，这样我们就把右单旋指针对接所涉及的结点地址都记录下来了，对接时就不用担心指针覆盖的问题了。之后我们将cur的父结点的左指向cur的右子节点，cur的右指向cur的父结点。左右结点指针更新之后，别忘了还有为了方便向上调整而引入到结点中的父结点指针。首先我们先对cur的右子结点指针判空，cur的右子结点是有可能为空的，但是为空时将cur的父结点的左指向它不会有问题，因为本来就应该指向空，而父结点的指针更新就不行了，我们应该先判空，不为空的话就将他的父结点指针指向cur的父结点。然后再将cur的父结点的父结点指针指向cur，cur的父结点指针指向爷爷结点。最后我们还应注意cur的父结点是根结点的情况，因为根结点是没有父结点的，换到这里就是没有爷爷结点。如果有爷爷结点，就将爷爷结点的左或右子结点的指针指向cur。如果没有，先将cur的父结点指针置空，再将AVL树的根结点更新为cur。之后是对平衡因子的更新，其实将平衡因子的更新与旋转函数解耦更好，笔者这里怕麻烦没改了。通过这两个平衡因子的更新我们会发现，旋转后的cur与parent结点的平衡因子都变成了0，当然原本parent的位置上现在是cur了，但平衡因子为0意味着不用向上更新了，可以直接结束循环。

左单旋

听名字就知道，左单旋就是右单旋的完全镜像版，旋转过程与算法书写原理也是一模一样，笔者直接放出代码，不做过多赘述。

void Lrotation(Node* cur)
{Node* parent = cur->_parent;Node* pparent = parent->_parent;Node* cur_left = cur->_left;parent->_right = cur_left; //左右节点更新cur->_left = parent;if(cur_left) cur_left->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{root = cur;cur->_parent = nullptr; //解耦}cur->BFactor = 0; //平衡因子的更新parent->BFactor = 0;
}

双旋算法

在AVL树中，单单使用单旋算法是不能够应对所有情况的，对于一下两种情况，


使用单旋算法无法完成平衡，我们看一下，如果对其使用单旋会发生什么，

我们会发现当我们对左子树高的情况使用右旋时，最后变成了右子树高的情况，AVL树还是不平衡。怎么办呢？这时就要用到双旋了。

左右双旋

对于左子树高且呈折现形的情况，

旋转一次无法解决问题，我们应该先来一个左单旋，再来一个右单旋，

通过这样的方式可以实现树的平衡，在实际书写时我们也可以复用我们之前写好的左右单旋函数，但是，有一点不一样的是，平衡因子的更新，我们可以看到，实际双旋完这三个结点的平衡因子并不都是0，这里是存在俩各种情况的，我们需要分情况处理。

实际旋转完平衡因子的更新与son结点的哪棵子树更高有关系，


当然，我们还应该考虑son就是新插入的结点的情况，

我们在插入之前就对son结点的三种情况进行判断，在双旋结束之后更新对应的平衡因子就行。

void LRrotation(Node* cur)
{if (cur->_right->BFactor == 1){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = -1;}else if (cur->_right->BFactor == -1){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 1;cur->_right->BFactor = 0;}else //cur的子结点是刚插入的情况{Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = 0;}
}

这里需要注意，在第一次旋转之后，cur与son的位置已经乱了，需要将旋转完的son视为新的cur进行第二次旋转。son是刚插入的情况三个节点的平衡因子都是0，son的左子树高的情况需要将最后son（重置完是cur）的右结点的平衡因子更新为-1，son的右子树高的情况需要将最后son的左结点的平衡因子更新为1。

右左双旋

与左右单旋同理，右左双旋也是左右双旋的完全镜像版，算法书写原理一模一样，这里不过多赘述，直接放代码。

void RLrotation(Node* cur)
{if (cur->_left->BFactor == 1){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = -1;}else if (cur->_left->BFactor == -1){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 1;cur->_right->BFactor = 0;}else //cur的子结点是刚插入的情况{Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);cur->BFactor = 0;cur->_left->BFactor = 0;cur->_right->BFactor = 0;}
}

至此，插入函数的旋转算法全部讲完了，我们将对应的情况与对应的算法写入插入函数，

bool insert(Key a, Value b)
{if (!root)//树判空{root = new Node(a, b);return true;}Node* cur = root;Node* parent = nullptr;while (cur)//找位置{if (cur->_key == a) return false;parent = cur;if (cur->_key > a) cur = cur->_left;else cur = cur->_right;}if (parent->_key > a)//插入{parent->_left = new Node(a, b);cur = parent->_left;cur->_parent = parent;//parent->BFactor++;}else{parent->_right = new Node(a, b);cur = parent->_right;cur->_parent = parent;//parent->BFactor--;}Node* son = nullptr;while (parent){if (parent->_key > cur->_key){parent->BFactor++;}else{parent->BFactor--;}if (parent->BFactor == 0) break;if (parent->BFactor == 2 || parent->BFactor == -2){if (parent->_key > cur->_key){if (son && (cur->_key > son->_key)) Rrotation(cur);else LRrotation(cur);}else{if (son && (cur->_key < son->_key)) Lrotation(cur);else RLrotation(cur);}break;}son = cur;cur = parent;parent = parent->_parent;}return true;
}

就这样，AVL的核心之一——插入函数就完成了。除了插入函数之外，我还写了查找函数等的一些函数来检测插入函数正确与否，大家可以用作参考，实现思路都很简单，不过多赘述。