C++实现AVL树（四种旋转详解）

深藏阁楼爱情的钟 2022-06-01 06:49 268阅读 0赞

## 一、概念 ##

AVL树又称为高度平衡的二叉搜索树，它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

## 二、性质 ##

*  树中每个左子树和右子树都是AVL树
 *  左子树和右子树高度之差的绝对值（简称平衡因子）不超过1（0，1，-1）  
    平衡因子就是用右子树的高度减去左子树的高度  
    ![这里写图片描述][SouthEast]  
    红色的就是每个节点的平衡因子

## 三、AVL树的插入 ##

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

### 插入算法： ###

*  如果是空树，插入后即为根节点，插入后直接返回true
 *  如果树不空，寻找插入位置，若在寻找的过程中找到key，则插入失败直接返回false
 *  插入结点
 *  更新平衡因子，对树进行调整

#### 新节点pcur平衡因子为0，但其双亲结点parent的平衡因子有三种情况： ####

*  如果parent的平衡因子为0  
    即在parent较矮的子树上插入新节点，parent平衡，其高度没有增加，此时从parent到 根路径 上各结点为根的子树的高度不变，即各结点的平衡因子不变，结束平衡化处理。
 *  如果parent的平衡因子的绝对值为1  
    插入前parent的平衡因子为0，插入后以parent为根的子树没有失去平衡，但该子树 的高度增 加，需从parent向根节点方向回溯，继续查看parent的双亲的平衡性。
 *  在上述更新后，如果parent平衡因子的绝对值为2，新节点在较高的子树插入，需要做平衡化处理：  
    **若parent->\_bf == 2，说明右子树高，设parent的右子subR**   
    当subR的平衡因子为1，执行左单旋转  
    当subR的平衡因子为-1，执行先右后左双旋转  
    **若parent->\_bf == -2，说明左子树高，设parent的左子树subL**   
    当subL的平衡因子为-1，执行右单旋转  
    当subL的平衡因子为1，执行先左后右双旋转  
    **旋转后parent为根的子树高度降低，无需继续向上层回溯**

### 1.左单旋 ###

插入节点位于较高右子树的右侧  
如下图所示：  
![这里写图片描述][SouthEast 1]

//左单旋
        void RotateL(pNode parent)
        {
            pNode subR = parent->_pRightChild;
            pNode subRL = subR->_pLeftChild;
    
            parent->_pRightChild = subRL;
            if (subRL)
                subRL->_pParent = parent;
    
            subR->_pLeftChild = parent;
            pNode pparent = parent->_pParent;
            subR->_pParent = pparent;
            parent->_pParent = subR;
    
            if (parent == _pRoot)
            {
                _pRoot = subR;
            }
            else//更新祖父节点的左右孩子
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = subR;
                else
                    pparent->_pRightChild = subR;
            }
            //更新平衡因子
            parent->_bf = subR->_bf = 0;
        }

### 2.右单旋 ###

插入节点位于较高左子树的左侧  
如下图所示：  
![这里写图片描述][SouthEast 2]

void RotateR(pNode parent)
        {
            pNode subL = parent->_pLeftChild;
            pNode subLR = subL->_pRightChild;
    
            parent->_pLeftChild = subLR;
            if (subLR)
                subLR->_pParent = parent;
    
            subL->_pRightChild = parent;
            pNode pparent = parent->_pParent;
            parent->_pParent = subL;
            subL->_pParent = pparent;
    
            if (parent == _pRoot)
            {
                _pRoot = subL;
            }
            else
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = subL;
                else
                    pparent->_pRightChild = subL;
            }
            //更新平衡因子
            parent->_bf = subL->_bf = 0;
        }

### 3.左右双旋 ###

插入节点在较高左子树的右侧  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

//左右双旋
        void RotateLR(pNode parent)
        {
            pNode pSubL = parent->_pLeftChild;
            pNode pSubLR = NULL;
            if (pSubL)
                pSubLR = pSubL->_pRightChild;
    
            RotateL(parent->_pLeftChild);//先对parent的左孩子进行左旋
            RotateR(parent);//对parent进行右旋
    
            if (pSubLR->_bf == 1)
                parent->_bf = 0;
            else if (pSubLR->_bf == -1)
                parent->_bf = 1;
        }

### 4.右左双旋 ###

插入节点位于较高右子树的左侧  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

//右左双旋
        void RotateRL(pNode parent)
        {
            pNode pSubR = parent->_pRightChild;
            pNode pSubRL = NULL;
            if (pSubR!=NULL)
                pSubRL = pSubR->_pLeftChild;
    
            RotateR(parent->_pRightChild);
            RotateL(parent);
    
            if (pSubRL->_bf == 1)
                parent->_bf = -1;
            else if (pSubRL->_bf == -1)
                parent->_bf = 0;
        }

## 4.AVL的删除 ##

（在这里简单介绍一下删除的算法，不做具体的代码实现）

从AVL树中删除一个节点，首先必须检测该结点是否存在，若存在删除该结点之后可能会破 坏AVL树的高度平衡，因此需要做平衡化旋转。  
被删除的结点pcur存在以下情况：

*  被删除结点只有左孩子
 *  被删除结点只有右孩子
 *  被删除结点左右孩子都存在–>变为删除中序遍历下的第一个结点q

更新parent的平衡因子，若q是parent的左孩子，则parent的平衡因子增加1，否则减少1，根据修改后的parent的平衡因子调整到根路径上的所有节点：

*  parent平衡因子的平衡因子为1或-1，parent高度不变，则从parent到根所有节点高度均 不变，不用调整。
 *  parent的平衡因子变成0，虽然以parent为根的子树平衡，其高度减1，但需要检查 parent的双亲结点的平衡性。
 *  结点parent的平衡因子为2或-2，则较矮子树被缩短，parent发生不平衡，需要进行平衡化旋转。

令parent较高子树的根为q，根据q的平衡因子，分一下三种情况

*  如果q的平衡因子为0，执行单旋转恢复parent
 *  如果q的平衡因子与parent平衡因子(正负)号相同，则执行一个单旋转恢复 parent
 *  如果q的平衡因子与parent平衡因子(正负)号相反，则执行一个双旋转恢复 parent

#### 完整代码 ####

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <stdlib.h>
    
    template <class K,class V>
    struct AVLTreeNode
    {
        AVLTreeNode(const K& key,const V& value)
        :_pLeftChild(NULL)
        , _pRightChild(NULL)
        , _pParent(NULL)
        , _key(key)
        , _value(value)
        , _bf(0)
        {}
        AVLTreeNode<K, V>* _pLeftChild;
        AVLTreeNode<K, V>* _pRightChild;
        AVLTreeNode<K, V>* _pParent;
        K _key;
        V _value;
        int _bf;
    };
    
    template <class K,class V>
    class AVLTree
    {
        typedef AVLTreeNode<K, V> Node;
        typedef AVLTreeNode<K, V>* pNode;
    public:
    
        AVLTree()
            :_pRoot(NULL)
        {}
    
        //插入
        bool Insert(const K& key, const V& value)
        {
            //空树的插入
            if (_pRoot == NULL)
            {
                _pRoot = new Node(key, value);
                return true;
            }
            pNode parent = NULL;
            pNode cur = _pRoot;
    
            //寻找待插入节点的位置
            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_pLeftChild;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_pRightChild;
                }
                else
                    return false;
            }
            //插入节点
            cur = new Node(key, value);
            if (parent->_key < key)
            {
                parent->_pRightChild = cur;
                cur->_pParent = parent;
            }
            else
            {
                parent->_pLeftChild = cur;
                cur->_pParent = parent;
            }
            //调整树
            while (parent)
            {
                if (parent->_pRightChild == cur)
                    parent->_bf++;
                else
                    parent->_bf--;
                if (parent->_bf == 0)
                    break;
                else if (parent->_bf == 1 || parent->_bf == -1)
                {
                    cur = parent;
                    parent = cur->_pParent;
                }
                else 
                {
                    if (parent->_bf == 2)
                    {
                        if (cur->_bf == 1)//插入节点位于右孩子处
                            RotateL(parent);
                        else
                            RotateRL(parent);
                    }
                    else
                    {
                        if (cur->_bf == -1)
                            RotateR(parent);
                        else
                            RotateLR(parent);
                    }
                    break;
                }
            }
            return true;
        }
    
        //中序遍历
        void InOrder()
        {
            _InOrder(_pRoot);
            cout << endl;
        }
    
        //判断是否为平衡二叉树
        bool IsBalance()
        {
            return _IsBalance(_pRoot);
        }
    
        //求树的高度
        int Height()
        {
            return _Height(_pRoot);
        }
    
    private:
    
        void _InOrder(pNode pRoot)
        {
            if (pRoot)
            {
                _InOrder(pRoot->_pLeftChild);
                cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
                _InOrder(pRoot->_pRightChild);
            }
        }
    
        int _Height(pNode pRoot)
        {
            if (pRoot == NULL)
                return 0;
    
            int leftHeight = _Height(pRoot->_pLeftChild);
            int rightHeight = _Height(pRoot->_pRightChild);
    
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
        bool _IsBalance(pNode pRoot)
        {
            if (pRoot == NULL)
                return true;
    
            int leftHeight = _Height(pRoot->_pLeftChild);
            int rightHeight = _Height(pRoot->_pRightChild);
    
            if (abs(leftHeight - rightHeight) >= 2)
                return false;
    
            return _IsBalance(pRoot->_pLeftChild) && _IsBalance(pRoot->_pRightChild);
        }
    
        //左单旋
        void RotateL(pNode parent)
        {
            pNode subR = parent->_pRightChild;
            pNode subRL = subR->_pLeftChild;
    
            parent->_pRightChild = subRL;
            if (subRL)
                subRL->_pParent = parent;
    
            subR->_pLeftChild = parent;
            pNode pparent = parent->_pParent;
            subR->_pParent = pparent;
            parent->_pParent = subR;
    
            if (parent == _pRoot)
            {
                _pRoot = subR;
            //  subR->_pParent = NULL;
            }
            else//更新祖父节点的左右孩子
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = subR;
                else
                    pparent->_pRightChild = subR;
            }
            parent->_bf = subR->_bf = 0;
        }
    
        //右单旋
        void RotateR(pNode parent)
        {
            pNode subL = parent->_pLeftChild;
            pNode subLR = subL->_pRightChild;
    
            parent->_pLeftChild = subLR;
            if (subLR)
                subLR->_pParent = parent;
    
            subL->_pRightChild = parent;
            pNode pparent = parent->_pParent;
            parent->_pParent = subL;
            subL->_pParent = pparent;
    
            if (parent == _pRoot)
            {
                _pRoot = subL;
            //  subL->_pParent = NULL;
            }
            else
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = subL;
                else
                    pparent->_pRightChild = subL;
            }
            parent->_bf = subL->_bf = 0;
        }
    
        //右左双旋
        void RotateRL(pNode parent)
        {
            pNode pSubR = parent->_pRightChild;
            pNode pSubRL = NULL;
            if (pSubR!=NULL)
                pSubRL = pSubR->_pLeftChild;
    
            RotateR(parent->_pRightChild);
            RotateL(parent);
    
            if (pSubRL->_bf == 1)
                parent->_bf = -1;
            else if (pSubRL->_bf == -1)
                parent->_bf = 0;
        }
    
        //左右双旋
        void RotateLR(pNode parent)
        {
            pNode pSubL = parent->_pLeftChild;
            pNode pSubLR = NULL;
            if (pSubL)
                pSubLR = pSubL->_pRightChild;
    
            RotateL(parent->_pLeftChild);
            RotateR(parent);
    
            if (pSubLR->_bf == 1)
                parent->_bf = 0;
            else if (pSubLR->_bf == -1)
                parent->_bf = 1;
        }
    
    private:
        pNode _pRoot;
    };

#### 测试代码： ####

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include "AVLTree.h"
    
    
    void Test()
    {
        int arr[10] = { 2, 5, 0, 6, 9, 1, 4, 3, 7, 8 };
        AVLTree<int, int> avl;
        for (int i = 0; i < 10; i++)
        {
            avl.Insert(arr[i], i);
        }
        avl.InOrder();
    
        cout << "avl is balance?" << avl.IsBalance() << endl;
        cout << "avl树高度为：" << avl.Height() << endl;
    
    }
    
    int main()
    {
        Test();
        system("pause");
        return 0;
    }

#### 运行结果： ####

![这里写图片描述][SouthEast 7]

[SouthEast]: /images/20220601/1f7d61d688904afabc66ffbfd5a97d9e.png
[SouthEast 1]: /images/20220601/3012f8cfb9164c35acfba6d430416f92.png
[SouthEast 2]: /images/20220601/f0c4126e7399458eb354446eb403f26c.png
[SouthEast 3]: /images/20220601/9e978cfec5ee4435b7034a3182d42b97.png
[SouthEast 4]: /images/20220601/f87e9f9f314147a085f467b9b6af0a0e.png
[SouthEast 5]: /images/20220601/30171e2e937c47e4baab9a73b700a6b3.png
[SouthEast 6]: /images/20220601/27d5239fac1c4da98368e6229971d19c.png
[SouthEast 7]: /images/20220601/c7103c571ca74578a842b8b7a745a070.png