前言

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

一、AVL树的概念

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

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

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

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

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

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

二、AVL树节点的定义

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

//K:key  V:Valuetemplate<classK, classV>structAVLTreeNode{
//构造函数AVLTreeNode(constpair<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<classK, classV>classAVLTree{
typedefAVLTreeNode<K, V>Node;
public:
private:
Node*_root=nullptr;
};

三、AVL树的插入

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

按照二叉搜索树的方式插入新节点

调整节点的平衡因子

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

（1）进行插入节点

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

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

（2）更新平衡因子

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

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

新增结点在parent的右边，parent的平衡因子 ++
新增结点在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 的父结点的平衡因子，因此无需继续往上更新平衡因子

而不会影响parent 的父结点的平衡因子，因此无需继续往上更新平衡因子

-2或2 此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理

parent的平衡因子更新后为：
-1或1	只有0经过 -- 或 ++ 操作后会变成 -1/1，说明新结点的插入使得 parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子

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

当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋

当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋

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

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

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

什么是旋转，下面解释

以上分析的代码如下：

boolInsert(constpair<K, V>&kv)
{
//节点为空，新建根节点，默认为平衡二叉树if (_root==nullptr)
    {
_root=newNode(kv);
returntrue;
    }
//节点为不空Node*parent=nullptr;//用于记录上一个节点Node*cur=_root;
//寻找合适的位置进行插入while (cur)
    {
if (cur->_kv.first>kv.first)
        {
parent=cur;
cur=cur->_left;
        }
elseif (cur->_kv.first<kv.first)
        {
parent=cur;
cur=cur->_right;
        }
else//cur->kv.first = kv.first要插入值已经存在，插入失败        {
returnfalse;
        }
    }
cur=newNode(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;
        }
elseif (parent->_bf==1||parent->_bf==-1)//第二种情况        {
cur=parent;
parent=parent->_parent;
        }
elseif (parent->_bf==2||parent->_bf==-2)//第三种情况        {
// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转if (parent->_bf==2&&cur->_bf==1)
            {
RotateL(parent);//左单旋            }
elseif (parent->_bf==-2&&cur->_bf==-1)
            {
RotateR(parent);//右单旋            }
elseif (parent->_bf==-2&&cur->_bf==1)
            {
RotateLR(parent);//双旋转：左单旋后右单旋            }
elseif (parent->_bf==2&&cur->_bf==-1)
            {
RotateRL(parent);//双旋转：右单旋后左单旋            }
break;
        }
else//不是上面三种情况，插入有问题        {
assert(false);
        }
    }
returntrue;
}

四、AVL树的旋转

4.1 左单旋

左单旋的步骤如下：

让 subR 的左子树作为parent的右子树
让parent作为subR的左子树

让subR作为整个子树的根
更新平衡因子

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

旋转示意图如下：

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

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

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

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

左单旋代码如下：

//左单旋voidRotateL(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 右单旋

右单旋的步骤如下：

让 subL 的右子树作为 parent 的左子树
让 parent 作为 subL 的右子树

让 subL 作为整个子树的根
更新平衡因子

旋转示意图如下：

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

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

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

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

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

右单旋代码如下：

//右单旋voidRotateR(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 左右双旋

左右双旋的步骤如下：

以 subL 为旋转点进行左单旋

以 parent 为旋转点进行右单旋
更新平衡因子

旋转示意图如下：

（1）插入新节点

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

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

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

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

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

（4）更新平衡因子

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

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

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

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

如图：

（1） subLR == -1

（2） subLR == 1

（3） subLR == 0

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

左右双旋的代码如下：

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

4.4 右左双旋

右左双旋的步骤如下：

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

旋转示意图如下：

（1）插入新节点

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

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

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

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

（4）更新平衡因子

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

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

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

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

平衡因子更新如图：

（1） subLR == 1

（2） subLR == -1

（3） subLR == 0

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

右左双旋的代码如下：

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

五、AVL树的验证

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

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

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

voidInOrder()
{
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 平衡因子正常

//判断平衡因子是否异常boolIsBalance()
{
returnIsBalance(_root);
}
intHeight(Node*root)
{
if (root==nullptr)
return0;
intlh=Height(root->_left);
intrh=Height(root->_right);
returnlh>rh?lh+1 : rh+1;
}
boolIsBalance(Node*root)
{
if (root==nullptr)
    {
returntrue;
    }
intleftHeight=Height(root->_left);
intrightHeight=Height(root->_right);
if (rightHeight-leftHeight!=root->_bf)
    {
cout<<root->_kv.first<<"平衡因子异常"<<endl;
returnfalse;
    }
returnabs(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:Valuetemplate<classK, classV>structAVLTreeNode{
//构造函数AVLTreeNode(constpair<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<classK, classV>classAVLTree{
typedefAVLTreeNode<K, V>Node;
public:
boolInsert(constpair<K, V>&kv)
    {
//节点为空，新建根节点，默认为平衡二叉树if (_root==nullptr)
        {
_root=newNode(kv);
returntrue;
        }
//节点为不空Node*parent=nullptr;//用于记录上一个节点Node*cur=_root;
//寻找合适的位置进行插入while (cur)
        {
if (cur->_kv.first>kv.first)
            {
parent=cur;
cur=cur->_left;
            }
elseif (cur->_kv.first<kv.first)
            {
parent=cur;
cur=cur->_right;
            }
else//cur->kv.first = kv.first要插入值已经存在，插入失败            {
returnfalse;
            }
        }
cur=newNode(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;
            }
elseif (parent->_bf==1||parent->_bf==-1)//第二种情况            {
cur=parent;
parent=parent->_parent;
            }
elseif (parent->_bf==2||parent->_bf==-2)//第三种情况            {
// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转if (parent->_bf==2&&cur->_bf==1)
                {
RotateL(parent);//左单旋                }
elseif (parent->_bf==-2&&cur->_bf==-1)
                {
RotateR(parent);//右单旋                }
elseif (parent->_bf==-2&&cur->_bf==1)
                {
RotateLR(parent);//双旋转：左单旋后右单旋                }
elseif (parent->_bf==2&&cur->_bf==-1)
                {
RotateRL(parent);//双旋转：右单旋后左单旋                }
break;
            }
else//不是上面三种情况，插入有问题            {
assert(false);
            }
        }
returntrue;
    }
//左单旋voidRotateL(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;
    }
//右单旋voidRotateR(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;
    }
//双旋转：左单旋后右单旋voidRotateLR(Node*parent)
    {
Node*subL=parent->_left;
Node*subLR=subL->_right;
intbf=subLR->_bf;//用于判断平衡因子的更新RotateL(parent->_left);
RotateR(parent);
//需要更新平衡因子if (bf==-1)//subLR 的左子树新增        {
subL->_bf=0;
parent->_bf=1;
subLR->_bf=0;
        }
elseif(bf==1)//subLR 的右子树新增        {
subL->_bf=-1;
parent->_bf=0;
subLR->_bf=0;
        }
elseif (bf==0)//subLR 自己就是新增        {
subL->_bf=0;
parent->_bf=0;
subLR->_bf=0;
        }
else//不是上面三种情况，插入有问题        {
assert(false);
        }
    }
//双旋转：右单旋后左单旋voidRotateRL(Node*parent)
    {
Node*subR=parent->_right;
Node*subRL=subR->_left;
intbf=subRL->_bf;//用于判断平衡因子的更新RotateR(parent->_right);
RotateL(parent);
//需要更新平衡因子if (bf==-1)//subRL 的左子树新增        {
subR->_bf=1;
parent->_bf=0;
subRL->_bf=0;
        }
elseif (bf==1)//subRL 的右子树新增        {
subR->_bf=0;
parent->_bf=-1;
subRL->_bf=0;
        }
elseif (bf==0)//subLR 自己就是新增        {
subR->_bf=0;
parent->_bf=0;
subRL->_bf=0;
        }
else//不是上面三种情况，插入有问题        {
assert(false);
        }
    }
//voidInOrder()
    {
_InOrder(_root);
    }
//判断平衡因子是否异常boolIsBalance()
    {
returnIsBalance(_root);
    }
private:
void_InOrder(Node*root)
    {
if (root==nullptr)
return;
_InOrder(root->_left);
cout<<root->_kv.first<<":"<<root->_kv.second<<endl;
_InOrder(root->_right);
    }
intHeight(Node*root)
    {
if (root==nullptr)
return0;
intlh=Height(root->_left);
intrh=Height(root->_right);
returnlh>rh?lh+1 : rh+1;
    }
boolIsBalance(Node*root)
    {
if (root==nullptr)
        {
returntrue;
        }
intleftHeight=Height(root->_left);
intrightHeight=Height(root->_right);
if (rightHeight-leftHeight!=root->_bf)
        {
cout<<root->_kv.first<<"平衡因子异常"<<endl;
returnfalse;
        }
returnabs(rightHeight-leftHeight) <2&&IsBalance(root->_left)
&&IsBalance(root->_right);
    }
private:
Node*_root=nullptr;
};

Test.cpp

#include <iostream>usingnamespacestd;
#include <assert.h>#include "AVLTree.h"voidTestAVLTree1()
{
//int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };intarr[] = { 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 (autoe : arr)
    {
t.Insert(make_pair(e, e));
    }
t.InOrder();
}
voidTestAVLTree2()
{
srand(time(0));//随机数种子constsize_tN=100000;
AVLTree<int, int>t;
for (size_ti=0; i<N; ++i)
        {
size_tx=rand();
t.Insert(make_pair(x, x));
//cout << t.IsBalance() << endl;        }
//判断平衡因子是否异常cout<<t.IsBalance() <<endl;
}
intmain()
{
//TestAVLTree1();TestAVLTree2();
return0;
}

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

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

【C++进阶】五、AVL树

前言

一、AVL树的概念

二、AVL树节点的定义

三、AVL树的插入

四、AVL树的旋转

4.1 左单旋

4.2 右单旋

4.3 左右双旋

4.4 右左双旋

五、AVL树的验证

六、AVL树的性能

七、完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++进阶】五、AVL树

前言

一、AVL树的概念

二、AVL树节点的定义

三、AVL树的插入

四、AVL树的旋转

4.1 左单旋

4.2 右单旋

4.3 左右双旋

4.4 右左双旋

五、AVL树的验证

六、AVL树的性能

七、完整代码

热门文章

最新文章

相关课程

相关电子书