【C++进阶】四、AVL树（二）

目录

前言 

一、AVL树的概念

二、AVL树节点的定义

三、AVL树的插入

四、AVL树的旋转

4.1 左单旋

4.2 右单旋

4.3 左右双旋

4.4 右左双旋

五、AVL树的验证

六、AVL树的性能

七、完整代码

---

前言 

        前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照红黑树（二叉搜索树）来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树（AVL树）来实现

一、AVL树的概念

        二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

        因此，两位俄罗斯的数学家G.M.Adelson-Velskii和 E.M.Landis 在1962年发明了一种解决上述问题的方法：

        当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度，这棵树叫 AVL树

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
3. 如果一棵二叉搜索树是高度平衡的，它就是AVL树，如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)

注意：树中每个结点左右子树高度之差的绝对值不超过1，AVL树接近于满二叉树，满二叉树的每个结点左右子树高度之差均为0 

二、AVL树节点的定义

        AVL树这里直接使用键值对，即 KV模型，使用键值对是为了方便后面实现 set 和 map。AVL树节点的定义增加了一个指向父节点的指针，变成了三叉链结构，并且每个节点都增加了一个平衡因子（一般是右子树高度 - 左子树高度），平衡因子的初始化设置为0即可

//K:key  V:Value
template<class K, class V>
struct AVLTreeNode
{//构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr), _parent(nullptr),_bf(0){}//成员变量pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factor 平衡因子
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

三、AVL树的插入

        AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

接下来按两个步骤进行解释： 

（1）进行插入节点 

因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：

1. 待插入结点的key值比当前结点小就插入到该结点的左子树
2. 待插入结点的key值比当前结点大就插入到该结点的右子树
3. 待插入结点的key值与当前结点的 key 值相等就插入失败

 （2）更新平衡因子

        插入完成后需要更新平衡因子 ，需要更新平衡因子的判断条件是：是取决于该结点的左右子树的高度是否发生了变化

所以我们插入结点后需要倒着往上更新平衡因子，更新规则如下：

1. 新增结点在parent的右边，parent的平衡因子 ++
2. 新增结点在parent的左边，parent的平衡因子 --

比如：下图进行插入一个新节点，祖先节点的平衡因子都可能发生变化

所以，每更新完一个结点的平衡因子后，都需要进行以下判断：

• 如果 parent 的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子
• 如果 parent 的平衡因子等于0，表明无需继续往上更新平衡因子了
• 如果parent的平衡因子等于 -2 或者 2，表明此时以 parent 结点为根结点的子树已经不平衡了，需要进行旋转处理

注： parent 不是这三种情况，插入有问题 

平衡因子分析如下：

parent的平衡因子更新后为：
-1或1	只有0经过 -- 或 ++ 操作后会变成 -1/1，说明新结点的插入使得 parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子
0	只有-1/1经过 ++ 或 -- 操作后会变成0，说明新结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得 parent 左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent 的父结点的平衡因子，因此无需继续往上更新平衡因子
-2或2	此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理

 

当parent的平衡因子为 -2或2，需要旋转处理，旋转处理又分四种情况：

1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋
2. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋
3. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋
4. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋

 比如第二种情况，这种情况就需要进行左单旋

 什么是旋转，下面解释

以上分析的代码如下：

bool Insert(const pair<K, V>& kv)
{//节点为空，新建根节点，默认为平衡二叉树if (_root == nullptr){_root = new Node(kv);return true;}//节点为不空Node* parent = nullptr;//用于记录上一个节点Node* cur = _root;//寻找合适的位置进行插入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//cur->kv.first = kv.first要插入值已经存在，插入失败{return false;}}cur = new Node(kv);//插入if (parent->_kv.first < kv.first)//插入到parent左边{parent->_right = cur;cur->_parent = parent;}else//插入到parent右边{parent->_left = cur;cur->_parent = parent;}//进行更新平衡因子while (parent)//parent 为空，说明已经更新到根节点{if (parent->_left == cur)//新节点插入在parent左边{parent->_bf--;}else//新节点插入在parent右边{parent->_bf++;}//继续更新平衡因子的依据：根据子树的高度是否变化// （1）parent->_bf == 0 说明之前parent->_bf是 1 或者 -1，说明之前parent一边高一边低，// 这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新// （2）parent->_bf == 1 或 -1 说明之前是 parent->_bf == 0，两边一样高，现在插入一边更高了，//  parent所在子树高度变了，继续往上更新// （3）parent->_bf == 2 或 -2，说明之前 parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则// 需要就地处理 -- 旋转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)//第三种情况{// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);//左单旋}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);//右单旋}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);//双旋转：左单旋后右单旋}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);//双旋转：右单旋后左单旋}break;}else//不是上面三种情况，插入有问题{assert(false);}}return true;
}

四、AVL树的旋转

4.1 左单旋

左单旋的步骤如下：

1. 让 subR 的左子树作为parent的右子树
2. 让parent作为subR的左子树
3. 让subR作为整个子树的根
4. 更新平衡因子

以下图片为了方便演示，用的都是抽象图，即代表无数种情况

旋转示意图如下：

旋后满足二叉搜索树的性质：

1. subR的左子树当中结点的值本身就比 parent 的值大，因此可以作为 parent 的右子树
2. parent 及其左子树当中结点的值本身就比 subR 的值小，因此可以作为 subR 的左子树

然后进行更新平衡因子，平衡因子全部置为0

经过左单旋后，树的高度变已经降下来了

左单旋代码如下：

//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;//进行链接parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;//记录parent节点的前一个节点subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr)//即subR已经是根节点{_root = subR;_root->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subR;}else//parent原本在 ppNode 的右边{ppNode->_right = subR;}subR->_parent = ppNode;}//旋转完成，更新平衡因子parent->_bf = subR->_bf = 0;
}

注意： 结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向 

4.2 右单旋

右单旋的步骤如下：

1. 让 subL 的右子树作为 parent 的左子树
2. 让 parent 作为 subL 的右子树
3. 让 subL 作为整个子树的根
4. 更新平衡因子

旋转示意图如下：

注：图片也是抽象图，涵盖无数种情况

右单旋后满足二叉搜索树的性质：

1. subL 的右子树当中结点的值本身就比 parent 的值小，因此可以作为 parent 的左子树
2. parent 及其右子树当中结点的值本身就比 subL 的值大，因此可以作为 subL 的右子树

 然后进行更新平衡因子，平衡因子全部置为0 

 经过右单旋后，树的高度变已经降下来了

右单旋代码如下：

//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//进行链接parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;//记录parent节点的前一个节点subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr)//即subL已经是根节点{_root = subL;subL->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subL;}else//parent原本在 ppNode 的右边{ppNode->_right = subL;}subL->_parent = ppNode;}//旋转完成，更新平衡因子parent->_bf = subL->_bf = 0;
}

注意： 结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向

4.3 左右双旋

左右双旋的步骤如下：

1. 以 subL 为旋转点进行左单旋
2. 以 parent 为旋转点进行右单旋
3. 更新平衡因子

旋转示意图如下：

（1）插入新节点

（2） 以 subL 为旋转点进行左单旋

 注：双旋转后平衡因子是不对的，需要后序更新平衡因子

（3）以 parent 为旋转点进行右单旋

  注：双旋转后平衡因子是不对的，需要后序更新平衡因子

        左右双旋后满足二叉搜索树的性质，左右双旋后，实际上就是让 subLR 的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让 subLR 作为整个子树的根（结合图理解）

（4）更新平衡因子 

        左右双旋之后，需要进行更新平衡因子，正确更新平衡因子的关键是：记录没有旋转之前 subLR 节点的平衡因子，该平衡因子用于判断以下三种情况：

1. subLR 的平衡因子为1时，说明 subLR 的右子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、-1、0
2. subLR 的平衡因子为-1时，说明 subLR 的左子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为1、0、0
3. subLR 的平衡因子为0时，说明 subLR 自己就是新增节点，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0

如图：

（1） subLR == -1

 （2） subLR == 1

  （3） subLR == 0

注意： subLR 自己就是新增节点时，其他情况都不会存在， subLR 不是这三种情况，插入有问题

左右双旋的代码如下：

//双旋转：左单旋后右单旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//用于判断平衡因子的更新RotateL(parent->_left);RotateR(parent);//需要更新平衡因子if (bf == -1)//subLR 的左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//subLR 的右子树新增{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0)//subLR 自己就是新增{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else//不是上面三种情况，插入有问题{assert(false);}
}

4.4 右左双旋

右左双旋的步骤如下：

1. 以 subR 为旋转点进行右单旋
2. 以 parent 为旋转点进行左单旋
3. 更新平衡因子

旋转示意图如下：

（1）插入新节点

（2）以 subR 为旋转点进行右单旋

（3）以 parent 为旋转点进行左单旋

注：双旋转后平衡因子是不对的，需要后序更新平衡因子

        右左双旋后满足二叉搜索树的性质，右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根（结合图理解）

（4）更新平衡因子  

        右左双旋之后，需要进行更新平衡因子，正确更新平衡因子的关键是：记录没有旋转之前 subLR 节点的平衡因子，该平衡因子用于判断以下三种情况：（与左右双旋一致，右左双旋就是在另一边）

1. subLR 的平衡因子为1时，说明 subLR 的右子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 -1、0、0
2. subLR 的平衡因子为-1时，说明 subLR 的左子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、1、0
3. subLR 的平衡因子为0时，说明 subLR 自己就是新增节点，左右双旋后parent、subL、subLR的平衡因子分别更新为 0、0、0

平衡因子更新如图：

（1） subLR == 1

 （2） subLR == -1

  （3） subLR == 0

 注意： subLR 自己就是新增节点时，其他情况都不会存在， subLR 不是这三种情况，插入有问题

右左双旋的代码如下：

//双旋转：右单旋后左单旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//用于判断平衡因子的更新RotateR(parent->_right);RotateL(parent);//需要更新平衡因子if (bf == -1)//subRL 的左子树新增{subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1)//subRL 的右子树新增{subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == 0)//subLR 自己就是新增{subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else//不是上面三种情况，插入有问题{assert(false);}
}

五、AVL树的验证

        AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

（1）验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

void InOrder()
{InOrder(_root);
}void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);
}

（2）验证其为平衡树

每个节点子树高度差的绝对值不超过1，进行验证节点的平衡因子是否计算正确，结果为 true 平衡因子正常

//判断平衡因子是否异常
bool IsBalance()
{return IsBalance(_root);
}int Height(Node* root)
{if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;
}bool IsBalance(Node* root)
{if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}

注：AVL树其他接口就不实现了，掌握插入即可，面试也比较关注AVL树的插入，即AVL树如何进行调平衡

六、AVL树的性能

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 logN（以2为底）。

        但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

        因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

七、完整代码

AVLTree.h

#pragma once//K:key  V:Value
template<class K, class V>
struct AVLTreeNode
{//构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr), _parent(nullptr),_bf(0){}//成员变量pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factor 平衡因子
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){//节点为空，新建根节点，默认为平衡二叉树if (_root == nullptr){_root = new Node(kv);return true;}//节点为不空Node* parent = nullptr;//用于记录上一个节点Node* cur = _root;//寻找合适的位置进行插入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//cur->kv.first = kv.first要插入值已经存在，插入失败{return false;}}cur = new Node(kv);//插入if (parent->_kv.first < kv.first)//插入到parent左边{parent->_right = cur;cur->_parent = parent;}else//插入到parent右边{parent->_left = cur;cur->_parent = parent;}//进行更新平衡因子while (parent)//parent 为空，说明已经更新到根节点{if (parent->_left == cur)//新节点插入在parent左边{parent->_bf--;}else//新节点插入在parent右边{parent->_bf++;}//继续更新平衡因子的依据：根据子树的高度是否变化// （1）parent->_bf == 0 说明之前parent->_bf是 1 或者 -1，说明之前parent一边高一边低，// 这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新// （2）parent->_bf == 1 或 -1 说明之前是 parent->_bf == 0，两边一样高，现在插入一边更高了，//  parent所在子树高度变了，继续往上更新// （3）parent->_bf == 2 或 -2，说明之前 parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则// 需要就地处理 -- 旋转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)//第三种情况{// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);//左单旋}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);//右单旋}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);//双旋转：左单旋后右单旋}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);//双旋转：右单旋后左单旋}break;}else//不是上面三种情况，插入有问题{assert(false);}}return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//进行链接parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;//记录parent节点的前一个节点subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr)//即subR已经是根节点{_root = subR;_root->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subR;}else//parent原本在 ppNode 的右边{ppNode->_right = subR;}subR->_parent = ppNode;}//旋转完成，更新平衡因子parent->_bf = subR->_bf = 0;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//进行链接parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;//记录parent节点的前一个节点subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr)//即subL已经是根节点{_root = subL;subL->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subL;}else//parent原本在 ppNode 的右边{ppNode->_right = subL;}subL->_parent = ppNode;}//旋转完成，更新平衡因子parent->_bf = subL->_bf = 0;}//双旋转：左单旋后右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//用于判断平衡因子的更新RotateL(parent->_left);RotateR(parent);//需要更新平衡因子if (bf == -1)//subLR 的左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if(bf == 1)//subLR 的右子树新增{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0)//subLR 自己就是新增{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}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 == -1)//subRL 的左子树新增{subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1)//subRL 的右子树新增{subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == 0)//subLR 自己就是新增{subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else//不是上面三种情况，插入有问题{assert(false);}}//void InOrder(){_InOrder(_root);}//判断平衡因子是否异常bool IsBalance(){return IsBalance(_root);}
private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}
private:Node* _root = nullptr;
};

Test.cpp

#include <iostream>
using namespace std;
#include <assert.h>
#include "AVLTree.h"void TestAVLTree1()
{//int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : arr){t.Insert(make_pair(e, e));}t.InOrder();
}void TestAVLTree2()
{srand(time(0));//随机数种子const size_t N = 100000;AVLTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand();t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}//判断平衡因子是否异常cout << t.IsBalance() << endl;
}int main()
{//TestAVLTree1();TestAVLTree2();return 0;
}

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新