数据结构——AVL树

什么是AVL树

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

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

1.它的左右子树都是AVL树。

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。

例如下图：如果一颗二叉搜索树是高度平衡的，它就是AVL树。如果它有N个结点，其高度可保持在O(logN)，搜索时间复杂度为O(lonN)。

AVL树结点的定义

在结点的定义中，我们直接定义成KV模型的结点，并新增一个平衡因子，还有一个_parent指针，也就是说，该结点拥有三个指针+一对键值对+一个平衡因子，在初始化时指针都初始化为空，平衡因子设定成0。

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)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};

AVL树的插入和平衡因子

首先为什么结点已经有了_parent，为什么还要新定义一个parent呢？这两个的含义不同，_parent的是每个结点都含有对父结点的链接，而parent则是定义成cur指针的父结点指针，也就是随时会发生变动，容易处理。也是为了和二叉搜索树的cur parent配合。

AVL树的插入：在AVL树的插入中，和二叉搜索树的插入相同，这里就不多赘述了。

AVL树的平衡因子：在前面可以知道，新插入的结点的平衡因子都初始化成0，那么该结点的父结点就需要进行更改了。

步骤一：更改平衡因子

1.如果cur插入在parent的左边，那么parent的平衡因子-1

2.如果cur插入在parent的右边，那么parent的平衡因子+1

步骤二：检查平衡因子

1.如果parent的平衡因子为0，那么说明插入前为±1，那么说明此时插入后不会增加高度。

2.如果parent的平衡因子为±1，那么说明插入前为0，那么说明此时插入后会增加高度。那么此时需要对祖先结点进行更新，让cur和parent各自返回上一层，然后重复步骤一和步骤二进行循环。

3.如果parent的平衡因子为±2，那么说明插入后违反了AVL树的性质，需要旋转处理。

    //插入函数
    bool insert(const pair<K,T>& kv)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(kv);
            return true;
        }
 
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
 
        while (cur)//当不为空，说明存在值，那么继续搜索可插入的地方
        {
            if (cur->_kv.first < kv.first)//key大于结点值，往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)//key小于结点值，往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等，那么不插入，插入失败
            {
                return false;
            }
        }
            //找到地方插入，new一个新结点
            cur = new Node(kv);
 
            if (parent->_kv.first < kv.first)//key大于父结点值，插右边
            {
                parent->_right = cur;
                cur->_parent = parent;
            }
            else//小于那么插左边
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
 
            return true;//插入成功
 
        //开始更新平衡因子
        while (cur != _root)//最差的情况就是一直更新回根结点
        {
            //处理因子
            if (cur == parent->_left)//如果插入的结点在父节点的左边
            {
                parent->_bf--;//因子-1
            }
            else//如果插入的结点在父节点的右边
            {
                parent->_bf++;//因子+1
            }
 
            //处理完成，开始检查因子
            if (parent->_bf == 0)//等于0，说明平衡，不需要处理
            {
                break;
            }
            //等于1或-1，说明高度变化了，那么要处理祖先结点因子
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
 
            else if (parent->_bf == 2 || parent->_bf == -2)// 如果等于2或-2，需要旋转解决
            {
                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)//左子树的右子树高
                {
                    RotateRL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)//右子树的左子树高
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                assert(false);//当平衡因子不为预期值，直接断言出错
            }
           
        }
    }

AVL树的旋转

在上述检查平衡因子时，当遇到parent = 2 的情况时，需要进行旋转处理。

AVL树的旋转有四种：左单旋，右单旋，左右双旋，右左双旋。

但是我们怎么判断什么情况下用什么旋转呢？

左单旋

如下图所示：此时parent = 2 ，cur = 1

此时为：右子树的右子树新增结点导致二叉树失衡。需要进行左旋转处理。就是，右高了，左旋使两边平衡

左单旋的步骤如下：由上图可以看到，c中新增了一个结点使二叉树失衡，只看开头和结果的话，就是b当成了30结点的右子树，然后60结点当成了根结点，然后30结点当成了60结点的左子树。

那么我们将30结点定义成parent，60结点定义成subR，b结点定义成subRL。

第一步：让subRL链接parent结点

第二步：让parent结点链接subR结点

第三步：让subR结点成为_root根结点。

注意：因为每两个结点都是相互链接的，所以更新链接的时候，需要双向各自取消链接再重新链接

    //左单旋
    void RotateL(Node* parent)
    {
        //定义新指针，方便操作
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* pp = parent->_parent;//方便更改_root的操作
 
        parent->_right = subRL;//让parent结点链接subRL
        subR->_left = parent;//让subR的左子树链接parent
        parent->_parent = subR;//由于parent的_parent由nullptr变成了subR，所以也需要重新链接
        if (subRL)
        //判断subRL是否为空，如果为空的话就不需要对subRL进行操作了，不然会出现对空指针进行解引用的问题
        {
            subRL->_parent = parent;//不为空，那么让subRL链接parent
        }
        if (_root = parent)//如果parent是整棵树的根结点
        {
            _root = subR;//subR变为根结点
            subR->_parent = nullptr;//subR的_parent为空
        }
        else//如果parent不是整棵树的根结点，那么将新的parent重新链接上一个结点
        {
            if (pp->_left = parent)//如果parent是上一个结点的左子树，那么新的parent也是
            {
                pp->_left = subR;
            }
            else//如果parent是上一个结点的右子树，那么新的parent也是
            {
                pp->_right = subR;
            }
            subR->_parent = pp;//更新subR的父结点
        }
        parent->_bf = subR->_bf = 0;//由于旋转后，整棵树的高度变回插入前的，那么此时parent和subR(cur)的因子都变回0
    }

右单旋

右单旋的逻辑与左单旋相同，这里就不多赘述了。

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;
        Node* pp = parent->_parent;
 
        //建立subL和parent之间的关系
        parent->_left = subRR;
        subL->_right = parent;
 
        //建立parent和subRR之间的关系
        parent->_parent = subL;
        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }
 
        //建立PP和subL之间的关系
        if (_root == parent)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        //更新平衡因子
        subL->_bf = parent->_bf = 0;
    }

左右双旋

如下图，原本->插入结点->左旋->右旋

这里需要用到左右双旋是因为插入的结点不在左子树的左子树，也就是说，使二叉树失衡的是左子树的右子树新增的结点。

那么此时就需要先将新增结点的树放到最左边，变成左子树的左子树，这样就可以进行右旋了，那么怎么变呢，我们只需要将30结点和60结点当成我们上面所学的左单旋例子即可

也就是说，用30结点子树传入进行左单旋(图的右下角)，然后在让90结点的子树进行右旋(图的左下角)

 我们看原本和结果：b成了30结点右子树，c成了90结点左子树，30和90分别成了60结点的左右子树，60结点成为了根结点。

那么我们左旋传入的结点就是30结点，旋转完成后，再将 90 结点传入进行右旋。

平衡因子的更新：

在双旋之后，我们可以发现，原本60结点的左子树，变成了30结点的右子树，60结点的右子树，变成了90结点的左子树，那么我们只需要根据60结点的平衡因子，就能知道到底是30结点的平衡因子改变了还是90结点的平衡因子改变了。当然，subR/subL结点的平衡因子由图所示都更新成0

    void RotateLR(Node* parent)//左右双旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        int bf = subLR->_bf;
 
        RotateL(parent->_left);
        RotateR(parent);
 
        if (bf == 0)
        {
            //subLR自己就是新增
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == -1)
        {
            //subLR的左子树新增
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if(bf == 1)
        {
            //subLR的右子树新增
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_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 == 0)
        {
            //subRL自己就是新增
            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);
        }
    }

AVL树的验证

验证为二叉搜索树

想要验证为二叉搜索树，即采用中序遍历，如果为升序，那么就是二叉搜索树

还是一样，需要在内部类调用私有成员。

//中序遍历副函数
void Inorder()
{
	_Inorder(_root);
}
//中序遍历主函数
void _Inorder(Node* root)
{
	if (root == nullptr)
		return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}

验证为AVL树

1.每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

2.节点的平衡因子是否计算正确。

那么，步骤也就变成了：采用后序遍历

1.从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）

2.先判断左子树是否是平衡二叉树。

3.再判断右子树是否是平衡二叉树。

4.若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）

//判断是否为AVL树
bool IsAVLTree()
{
	int hight = 0; //输出型参数
	return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
	if (root == nullptr) //空树是平衡二叉树
	{
		hight = 0; //空树的高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_IsBalanced(root->_left, leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_IsBalanced(root->_right, rightHight) == false)
		return false;
	//检查该结点的平衡因子
	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子设置异常：" << root->_kv.first << endl;
	}
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	hight = max(leftHight, rightHight) + 1;
	return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}

AVL树的性能

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