C++ AVLTree

1. AVLTree的定义

2. 平衡因子

3. AVLTree的基础接口

插入

旋转

左单旋：

右单旋：

双旋：

4. AVLTree的测试

5. 小结

1. AVLTree的定义

二叉搜索树（BST）虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下 。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii和E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 ) ，即可降低树的高度，从而减少平均搜索长度。

2. 平衡因子

平衡因子不是必须的，只是选择实现AVLTree的一种方式。

平衡因子的优势是可以直接观察，但是需要付出维护的代价。

在每一个节点中都加入其平衡因子的数值，一般习惯用右子树高度-左子树高度

template<typename k,typename v>
struct AVLTreeNode {typedef AVLTreeNode<k, v> Node;Node* _left;Node* _right;Node* _parent;int _bf;//balance factorpair<k, v> _kv;AVLTreeNode( const pair<k,v>& kv = make_pair(k(),v()) ):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

以下树为例进行分析。

将平衡因子当作一个风向标。

标出每一个节点现在的平衡因子：

新插入的节点会影响从根到该节点路径上所有节点的平衡因子，每插入一个平衡因子就需要调整其祖先的平衡因子（这也是为什么每个节点的成员需要设计一个parent）。

对于叶子结点，每插入一个节点，对于其双亲（原来的叶子）的变化：

插入在parent右边, 平衡因子++

插入在parent左边，平衡因子--

下面来讨论在普遍情况下插入节点后平衡因子的变化。

首先，任意树的平衡因子只会是-1 0 1

(否则不满足AVL树的条件)

1. 如果在插入节点之后，parent的平衡因子是0（就像上图的节点8），说明原本是-1或者1，然后新节点加入到了矮的那一边。

2. 如果插入后parentr的平衡因子是1或则-1，说明原本parent的平衡因子本来是0，在右或左插入一个。那此时parent的子树的高度就变化了，需要继续向上更新。

3. 如果插入后parent的平衡因子是2或者-2，说明原本parent的平衡因子本来是-1或者1，然后新节点加入到了长的那一边。此时parent的子树的高度也变化了，需要继续向上更新。

并且已经违反了AVL树的规则，需要进行旋转。

3. AVLTree的基础接口

基本结构都和二叉搜索树类似。

先实现结点：

template<typename k,typename v>
struct AVLTreeNode {typedef AVLTreeNode<k, v> Node;Node* _left;Node* _right;Node* _parent;int _bf;//balance factorpair<k, v> _kv;AVLTreeNode(const pair<k,v>& kv = make_pair(k(),v()):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

再写树：

构造我们现在只强调一下拷贝构造。

不能直接将根_root拷贝过来，这样是两颗重复的树，我们需要自己实现深拷贝。

而树的拷贝需要递归，构造函数里直接递归当然不合适，所以需要再封装一层。

插入

插入的大逻辑如下：

bool insert(const pair<k, v>& kv) {Node* parent = nullptr;Node* cur = _root;if (cur == nullptr) {_root = new Node(kv);return true;}while (cur) {if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;}else {return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first) parent->_left = cur;if (parent->_kv.first < kv.first) parent->_right = cur;cur->_parent = parent;//开始调整parent的balance factor,因为是三叉链，所以可以通过parent一路遍历向上while (parent) {//先计算平衡因子if (parent->_left == cur) {parent->_bf--;}else if (parent->_right == cur) {parent->_bf++;}//再决定是否向上调整if (parent->_bf == 0) {break;}else if (parent->_bf == 1 || parent->_bf == -1) {//adjust upcur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) {//旋转}else {//如果还有其他情况，说明原节点的bf有问题，不满足avl树的规范，直接断掉assert(0);}}return true;
}

在搜索二叉树的基础上，插入变的更加复杂。

首先比较的都是pair中的first，也就是key值

并且依然需要使用双指针，否则不好接入

最后就是需要插入完成之后调整_bf

旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。

直接通过上文中的例子来进入“旋转”的主题

左单旋：

新节点插入较高右子树的右侧，开始向上遍历调整平衡因子，调整到8的时候发现平衡因子是2，需要旋转，然后就将8这个节点传进我们的调节函数RotateL

旋转方法：9的左子树变成8的右子树，8变成9的左子树

这样旋转之后高度和加入节点之前没有变化。

抽象图：

所有的分析中都要注意，节点之间的高度差距不能超过1

假设30为传入函数的需要调整的节点（命名为parent）

60命名为subR a/b/c是三个等高的树

（如果a/b/c不等高就不能构成我们想调整的情况。）

总结一下就是：

左单旋需要将subRL连接到parent的右边，因为60的左子树一定是大于30的，然后将30连接到60的左边。

可以先通过列举h==0 h==1 h==2 h==3等情况观察：

h==0时最简单。也是上文引例中的情况。

h==1时的情况

h==2时，情况的种类就很多了。

a/b可能是xyz中的任意一种情况。c只能是x，否则直接在该子树中就可以调节了。

注意为什么是3*3*4

因为左单旋对应的模型是在60的右树（C）下进行增加节点，所以只有4个可以选择的位置。

h==3时，先分析高度为3的子树的情况，可能为x（全满）或者y（非全满）

其中y共有14种情况。所以不讨论加节点的C树，a/b树就已经有(14+1)*(14+1)种可能性

因此，解决这个问题还需要从抽象图入手，将a、b、c当作高度为h的抽象树。

代码实现：

旋转点：平衡因子出现问题的点。

左单旋其实只需要改变subR suRL parent三者的链接关系。

parent可以是整棵树的根，也可以是任意一个子树的根

依然有逻辑bug，subRL和parent的_parent都还要修改。

先只修改subRL的_parent（parent是需要调整的节点的变量名，_parent是节点内的成员变量）

subRL可能是空（h==0的时候就是空）。但是parent和subR是一定存在的（否则怎么会出现一个_bf是2一个_bf是1呢）

那如果这棵树本来自身只是一颗子树呢？

所以在改动parent->_parent的值之前，要记录一下原来的parent->_parent

对于parent->_parent的分析：

如果是空，表明30（原来的parent）本来就是整棵树的根，现在整棵树的根调整了，

我们需要调整下_root

如果不是空，就像之前的insert一样，得从parentParent再去找我们左旋的这棵树是在左边还是右边。但是不用调整_root

至此，单旋的大逻辑就已经完成。

节点链接好了，但是我们现在还没有处理平衡因子。

经过观察不难发现，parent和subR的平衡因子都变成0了

再加一句：parent->_bf = subR->_bf = 0;

void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) {subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent) {if (parentParent->_left == parent) {parentParent->_left = subR;}else {parentParent->_right = subR;}}else {subR->_parent = nullptr;this->_root = subR;}subR->_parent = parentParent;//调整平衡因子parent->_bf = subR->_bf = 0;
}

为了便于记忆：取名字的三个节点呈现一个“ > ”形状，要将凹陷的部分拉出来，所以出现这种形状叫左旋。

右单旋：

逻辑几乎和左旋是一样的，只是交换了right和left

读者可以自行尝试先写一写这个代码。

void RotateR(Node* parent) {assert(parent);Node* subL = parent->_left;Node* subLR = subL->right;parent->_left = subLR;if (subLR) {subLR->_parent = parent;}//解决subL和parent的父节点问题Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr) {_root = subL;}else {if (parentParent->_left == parent) {parentParent->_left = subL;}else {parentParent->_right = subL;}}subL->_parent = parentParent;//调整平衡因子parent->_bf = subL->_bf = 0;
}

实现好了左单旋和右单旋的代码

回到原来的插入代码，进行联系：

左旋的时候，parent的bf==2 cur的bf == 1

右旋的时候，parent的bf==-2 cur 的bf==-1

根据上述的两个条件，要讨论哪些旋转方案也逐渐明朗

cur->_bf==1&& parent->bf==2（左单旋）

cur->_bf==-1&& parent->bf==-2(右单旋)

cur->_bf==-1&& parent->bf==2

cur->_bf==1&& parent->bf==-2

来看后面两种情况：

双旋：

上面为单旋能解决的情况（parent和subR的bf符号相同），下面为符号相反

（h==0）

按照之前的旋转思路，此时进行左单旋，能保证搜索树的特征，但是没有完成旋转的初衷：使高度差消失。

这样旋只是让原来的右边高变成现在的左边高

(h==1)

如果此时再右旋，又会旋回去。

也就是说，左右旋面对这种情况只会原地打转。

解决方法：双旋

先看h==1或h==0

再看抽象图：

左双旋分为：右单旋+左单旋

右双旋分为：左单旋+右单旋

需要左双旋时，第一次右单旋就将本来需要左双旋的变成上文最基本的模型：

因为此时涉及到对subR进行一次单旋，需要使用到subRL的右子树，所以需要单独再拆开一层树来分析。单旋的时候subRL不一定存在，但这次都是在subRL的位置上加的数据，所以subRL一定不为空

还可以直接观察双旋结果：

直接看起始和终点状态，将subRL这个节点变成根，parent在左、subR在右

然后subRL的左右子树分别分配给parent的右和subR的左

总结：subRL或者subLR会成为新的根，他左边的子树分配给在两个节点中更左边的节点的右边，他右边的子树分配给在两个节点中更右边的节点（subR或subL / parent中的任意一个）的左边

双旋的代码实现的大逻辑：

当然是不正确的，

虽然每一次单旋都能保证父节点和子节点的转接，但是没有考虑平衡因子的维护。

问题整理：

双旋并不像单旋，单纯的全部更新为0

并且新节点加到b和c，最后的结果还不一样。

h为0的时候还是一种单独的情况，更新完之后是全0

以左双旋为例：

如果subRL的平衡因子是1 就是在C插入

如果subRL的平衡因子是-1 就是在B插入

如果是0，则subRL本身是新加入的节点，也就是上文所说的h是0的时候的特殊情况。

RotateRL的意思就是先右单旋再左单旋

左双旋和右双旋实现：

void RotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//采用直接观察法，记录最初的subRL的_bfRotateR(subR);RotateR(parent);if (bf == 0) {//说明subRL就是新加入的元素subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == -1) {parent->_bf = 0;subRL->_bf = 0;subR = 1;}else if (bf == 1) {parent->_bf = 1;subR->_bf = 0;subRL->_bf = 0;}else {assert(0);}
}void RotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);Rotate(parent);if (bf == 0) {parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1) {parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1) {parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else {assert(0);}
}

这个时候就能根据parent和cur的_bf值判断怎么旋了。

旋完之后可以直接break跳出平衡因子的调节。

4. AVLTree的测试

完成了以上代码后，使用{16, 3, 7, 11, 9, 26, 18, 14, 15} {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

两组测试用例来测试代码。

先实现中序走一遍。

但是中序只能保证是一个二叉搜索树。

还要判断其是不是平衡搜索树。

再实现一个找高度的函数

或者

均可，但是切忌写成：

递归里套了递归，时间复杂度会大很多。这一点在之前的博客中有过详细讲解。

利用_Height函数实现IsBalanceTree函数

bool _IsBalanceTree(Node* root) {if (root == nullptr) return true;//空树也算AVLTree//计算节点高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if (abs(diff) >= 2) {cout << "结构错误，有高度差大于1的节点" << endl;return false;}if (diff != root->_bf) {cout << "平衡因子调节错误" << endl;return false;}//并且保证所有的子树都满足这个条件。return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

调试技巧：

如果发现有错，用编译器cout来找报出错

打断点不一定要用编译器的条件断点，可以自己直接写。

第一组：

通过了。

第二组：

利用上述调试技巧打断点。

发现是6的平衡因子有问题

那么就在插入6时打下断点，开始观察是如何出错的。

（空语句不能打断点，所以我们定义一个变量语句来方便打断点）

然后顺利找到是RotateRL时调节平衡因子的问题。（bf==1时parent的值应该是-1）

AVLTree test2:

由于C语言库函数的设计，只能有32468个随机数。

所以希望产生N个随机数时最好加一个其他数字。

5. 小结

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

比如：插入时最多旋转两次（双旋），但是erase时可能需要旋转很多次。