• C++【AVL树】

    目录

    一、什么是AVL树

    插入

    更新平衡因子的规则

    旋转的规则

    第二种情况：左旋

    第一种情况：右旋

    第三种情况：左右旋

    第四种情况：右左旋

    测试一下​​​​​​​

    检查是不是平衡二叉树

    求高度

     随机插入一组数据测试

    二叉搜索树如果不平衡的话，就没办法发挥出二叉搜索树的优势

    AVLTree，红黑树

    一、什么是AVL树

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

    (需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
    一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
    它的左右子树都是AVL树
    左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1 )

    AVL树又可以称为高度平衡二叉搜索树 

    为什么这里控制高度之差不超过1，而不是相等？

    因为没有办法保证。

    比方说我们的树只有两个结点，那么必然是一个为根节点，一个为左子树结点或者右子树结点，所以左子树的高度和右子树的高度是不可能相等的。我们做不到 

    这样的树不是AVL树，因为我们没有满足每一个结点的左右子树的高度的差都是小于等于1

     通过控制树的高度去控制树的平衡

    这里的平衡因子就是高度差

    平衡因子=右子树的高度-左子树的高度

    （非必须）也可以不要，我们用的话是为了方便实现。

    也就是为了让我们有一个量化的值可以去查看

    插入

    如果我们是在8的左子树插入了一个7，那么8的左右子树的高度差变成0，依旧满足我们平衡二叉树的特性。

    但是如果在9的右子树加上了一个10呢？

    此时我们的9的左右子树的差是1，我们8的左右子树的差变成了2，我们需要对其进行调整和旋转。

    更新平衡因子的规则

    1、新增在右子树 

    如果新增的结点在父节点的右子树，我们需要将父节点的平衡因子+1，因为平衡因子的计算时右子树的高度减去左子树的高度，我们这里右子树的高度+1，但是左子树的高度并没有发生变化

    parent->bf++

    2、新增在左子树

    如果新增的结点在父节点的左子树，我们需要将父节点的平衡因子-1，因为平衡因子的计算时右子树的高度减去左子树的高度，我们这里左子树的高度+1，但是右子树的高度并没有发生变化

    parent->bf--

    3、更新后，parent->bf==1 或者 -1

    说明parent更新前的平衡因子是0，说明左右子树高度相等。

    插入后有一边高。

    parent高度变了，需要继续往上更新！（对上一层有影响）

    4、更新后，parent->bf==0

    说明parent更新前的平衡因子是1或者-1，说明左右子树高度相差1。

    插入后左右子树高度相等，插入填上了矮的那一边。

    parent所在的子树高度不变，不需要继续往上更新！（对上一层没有影响）

    5、更新后，parent->bf==2 或者 -2

    说明parent更新前的平衡因子是1或者-1，说明左右子树高度相差1。

    （原本就是平衡的临界值了）

    插入后原本就是高的一边更加高，打破了平衡。

    parent高度变了，需要旋转处理！

    6、更新后parent->bf >2or<-2的值？

    不可能，如果存在，则说明插入前就不是AVL树，需要去检查之前的操作的问题。

     

    下面的情况就需要旋转 

     

     如何用代码实现我们上述的方法

    1. //最坏的情况是更新到我们的根节点
    2.         //如果parent为空，也就是更新到了我们的根节点，没有上层节点了
    3.         while(parent)
    4.         {
    5.             if(cur==parent->_right)
    6.             {
    7.                 parent->_bf++;
    8.             }
    9.             else
    10.             {
    11.                 parent->_bf--;
    12.             }
    13.             
    14.             //父节点的bf为0的话，就停止迭代。
    15.             if((parent->_bf)==0)
    16.             {
    17.                 break;
    18.             }
    19.             //如果parent的_bf是1或者-1
    20.             //往上迭代
    21.             else if(abs(parent->_bf)==1)
    22.             {
    23.                 parent=parent->_parent;
    24.                 cur=cur->_parent;
    25.             }
    26.             else if(abs(parent->_bf)==2)
    27.             {
    28.                 //说明parent所在的子树已经不平衡了，需要旋转来调整
    29.             }
    30.             //说明parent的平衡因子>2，也就是在插入我们这个结点前面，我们的平衡二叉树已经不平衡了
    31.             else
    32.             {
    33.                 //直接抛出异常
    34.                 assert(false);
    35.             }
    36.         }

    我们观察到平衡因子是控制我们这一整棵树的关键。 

    旋转的规则

    出问题的时候一定是以parent为根节点所在的子树出问题了

    处理的原则

    1、旋转成平衡树 

    2、保持搜索树规则

    假设我们往树中依次插入

    1        3        5

     

    上面的树右边高，我们就需要往左边转，也就是左旋！

    更加复杂一点的情况

     

     

     

    我们往树中依次插入

    5        3        1         

     旋转的位置有可能是整棵树，也有可能是子树

    1.新节点插入较高左子树的左侧---左左：右单旋 

     

    2.新节点插入较高右子树的右侧---右右：左单旋

    3.新节点插入较高左子树的右侧---左右：先左单旋再右单旋

    4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋

     

    按照上面的图例演示，举几个简单的例子

    h==0

     

    h==1 

     

    所以这里的具象图有着无限多种情况，但是我们用上面的抽象图其实都是可以解释的。 

    第二种情况：左旋

      

    只有parent和subR的平衡因子发生了变化，且都变成0

    1. void RotateL(Node* parent)
    2.     {
    3.         Node* subR=parent->_right;
    4.         Node* subRL=subR->_left;
    5.  
    6.         parent->_right=subRL;
    7.         //修改三叉链里面的父亲结点
    8.         if(subRL)
    9.         {
    10.             subRL->_parent=parent;
    11.         }
    12.         Node* ppNode=parent->_parent;
    13.  
    14.         subR->_left=parent;
    15.         parent->_parent=subR;
    16.         //1、parent是整棵子树的根
    17.         if(parent==_root)
    18.         {
    19.             _root=subR;
    20.             subR->_parent= nullptr;
    21.         }
    22.         //2、parent是子树的根，也就是parent结点上面还有祖先结点
    23.         else
    24.         {
    25.             if(ppNode->_left==parent)
    26.             {
    27.                 ppNode->_left=subR;
    28.             }
    29.             else
    30.             {
    31.                 ppNode->_right=subR;
    32.             }
    33.             subR->_parent=ppNode;
    34.         }
    35.         //修改平衡因子
    36.         subR->_bf=parent->_bf=0;
    37.     }

    第一种情况：右旋

    1. //右旋
    2.     void RotateR(Node* parent)
    3.     {
    4.         Node*subL=parent->_left;
    5.         Node*subLR=subL->_right;
    6.  
    7.         parent->_left=subLR;
    8.         //修改三叉链表里面的父亲节点
    9.         if(subLR)
    10.         {
    11.             subLR->_parent=parent;
    12.         }
    13.         Node* ppNode=parent->_parent;
    14.  
    15.         subL->_right=parent;
    16.         parent->_parent=subL;
    17.         //1.parent是整个子树的根
    18.         if(parent==_root)
    19.         {
    20.             _root=subL;
    21.             subL->_parent= nullptr;
    22.         }
    23.         //2.parent是子树的根，也就是parent结点上面还有祖先结点
    24.         else
    25.         {
    26.             if(ppNode->_left==parent)
    27.             {
    28.                 ppNode->_left=subL;
    29.             }
    30.             else
    31.             {
    32.                 ppNode->_right=subL;
    33.             }
    34.             subL->_parent=ppNode;
    35.         }
    36.         //修改平衡因子
    37.         subL->_bf=parent->_bf=0;
    38.     }

    第三种情况：左右旋

    case1：在b插入

     无论是在b的位置插入还是在c的位置插入，b or c高度变为h，都会引发双旋。

    case2：在c插入 

     case3：h=0的情况（60自己就是新增）

     这里对应的90的结点就是我们的parent

    几个相关结点的标记如下

    case1：

     case2：

    case3：

    1. //左右旋
    2.     void RotateLR(Node* parent)
    3.     {
    4.         Node* subL=parent->_left;
    5.         Node* subLR=subL->_right;
    6.         int bf=subLR->_bf;
    7.  
    8.         RotateL(parent->_left);
    9.         RotateR(parent);
    10.  
    11.         //平衡因子的更新
    12.         //对上面的三种情况分别更改平衡因子
    13.         subLR->_bf=0;
    14.         //case1
    15.         if(bf==1)
    16.         {
    17.             parent->_bf=0;
    18.             subL->_bf=-1;
    19.         }
    20.         //case2
    21.         else if(bf==-1)
    22.         {
    23.             parent->_bf=1;
    24.             subL->_bf=0;
    25.         }
    26.         //case3
    27.         else if(bf==0)
    28.         {
    29.             parent->_bf=0;
    30.             subL->_bf=0;
    31.         }
    32.         else
    33.         {
    34.             assert(false);
    35.         }
    36.     }

    第四种情况：右左旋

    case1：在c位置插入新数据

     case2：在b位置插入新数据

    case3：h==0，（60自己就是新增） 

     几个相关结点标记如下

    case1：

    case2：

    case3：

    1. //左右旋
    2.     void RotateRL(Node* parent)
    3.     {
    4.         Node* subR=parent->_right;
    5.         Node* subRL=subR->_left;
    6.         int bf=subRL->_bf;
    7.  
    8.         RotateR(parent->_right);
    9.         RotateL(parent);
    10.  
    11.         //平衡因子的更新
    12.         //对上面的三种情况分别更改平衡因子
    13.         subRL->_bf=0;
    14.         //case1
    15.         if(bf==1)
    16.         {
    17.             parent->_bf=-1;
    18.             subR->_bf=0;
    19.         }
    20.             //case2
    21.         else if(bf==-1)
    22.         {
    23.             parent->_bf=0;
    24.             subR->_bf=1;
    25.         }
    26.             //case3
    27.         else if(bf==0)
    28.         {
    29.             parent->_bf=0;
    30.             subR->_bf=0;
    31.         }
    32.         else
    33.         {
    34.             assert(false);
    35.         }
    36.     }

    旋转的价值和意义

    1.让子树保持平衡

    2.降低树的高度（高度恢复到插入之前的样子）

    测试一下

    1.  
    2. #ifndef AVL_AVLTREE_H
    3. #define AVL_AVLTREE_H
    4. #pragma once
    5. using namespace std;
    6. template<class K,class V>
    7. struct AVLTreeNode
    8. {
    9.     AVLTreeNode* _left;
    10.     AVLTreeNode* _right;
    11.     //三叉链，更新结点可能会影响结点的祖先
    12.     AVLTreeNode* _parent;
    13.     
    14.     pair _kv;
    15.     int _bf;//平衡因子 balance factor
    16.  
    17.     AVLTreeNode(const pair&kv)
    18.         :_left(nullptr)
    19.         ,_right(nullptr)
    20.         ,_parent(nullptr)
    21.         ,_kv(kv)
    22.         ,_bf(0)
    23.     {
    24.  
    25.     }
    26. };
    27.  
    28. template<class K,class V>
    29. struct AVLTree
    30. {
    31.     typedef AVLTreeNodeNode;
    32. public:
    33.     bool Insert(const pair&kv)
    34.     {
    35.         if(_root== nullptr)
    36.         {
    37.             _root=new Node(kv);
    38.             return true;
    39.         }
    40.         Node * parent= nullptr;
    41.         Node* cur=_root;
    42.         while(cur)
    43.         {
    44.             if(cur->_kv.first
    45.             {
    46.                 parent=cur;
    47.                 cur=cur->_right;
    48.             }
    49.             else if(cur->_kv.first>kv.first)
    50.             {
    51.                 parent=cur;
    52.                 cur=cur->_left;
    53.             }
    54.             else
    55.             {
    56.                 //相等的话，不插入，去重
    57.                 return false;
    58.             }
    59.         }
    60.  
    61.         //插入我们的新节点
    62.         cur=new Node(kv);
    63.         if(parent->_kv.first
    64.         {
    65.             parent->_right=cur;
    66.         }
    67.         else
    68.         {
    69.             parent->_left=cur;
    70.         }
    71.  
    72.         //及时更新我们三叉链的parent的属性
    73.         cur->_parent=parent;
    74.  
    75.         //控制平衡
    76.         //1、沿着这个位置往上更新平衡因子
    77.         //这里的新插入的结点会影响祖先结点的平衡
    78.  
    79.         //最坏的情况是更新到我们的根节点
    80.         //如果parent为空，也就是更新到了我们的根节点，没有上层节点了
    81.         while(parent)
    82.         {
    83.             if(cur==parent->_right)
    84.             {
    85.                 parent->_bf++;
    86.             }
    87.             else
    88.             {
    89.                 parent->_bf--;
    90.             }
    91.  
    92.             //父节点的bf为0的话，就停止迭代。
    93.             if((parent->_bf)==0)
    94.             {
    95.                 break;
    96.             }
    97.             //如果parent的_bf是1或者-1
    98.             //往上迭代
    99.             else if(abs(parent->_bf)==1)
    100.             {
    101.                 parent=parent->_parent;
    102.                 cur=cur->_parent;
    103.             }
    104.             else if(abs(parent->_bf)==2)
    105.             {
    106.                 //说明parent所在的子树已经不平衡了，需要旋转来调整
    107.  
    108.                 //右右--左旋
    109.                 if((parent->_bf==2)&&(cur->_bf==1))
    110.                 {
    111.                     RotateL(parent);
    112.                 }
    113.                 else if((parent->_bf==-2)&&(cur->_bf==-1))
    114.                 {
    115.                     RotateR(parent);
    116.                 }
    117.                 else if(parent->_bf==-2&&cur->_bf==1)
    118.                 {
    119.                     RotateLR(parent);
    120.                 }else if(parent->_bf==2&&cur->_bf==-1)
    121.                 {
    122.                     RotateRL(parent);
    123.                 }else{
    124.                     assert(false);
    125.                 }
    126.                 break;
    127.             }
    128.             //说明parent的平衡因子>2，也就是在插入我们这个结点前面，我们的平衡二叉树已经不平衡了
    129.             else
    130.             {
    131.                 //直接抛出异常
    132.                 assert(false);
    133.             }
    134.         }
    135.         return true;
    136.     }
    137.  
    138.     void InOrder()
    139.     {
    140.         _InOrder(_root);
    141.         cout << endl;
    142.     }
    143.  
    144. private:
    145.     //左旋
    146.     void RotateL(Node* parent)
    147.     {
    148.         Node* subR=parent->_right;
    149.         Node* subRL=subR->_left;
    150.  
    151.         parent->_right=subRL;
    152.         //修改三叉链里面的父亲结点
    153.         if(subRL)
    154.         {
    155.             subRL->_parent=parent;
    156.         }
    157.         Node* ppNode=parent->_parent;
    158.  
    159.         subR->_left=parent;
    160.         parent->_parent=subR;
    161.         //1、parent是整棵子树的根
    162.         if(parent==_root)
    163.         {
    164.             _root=subR;
    165.             subR->_parent= nullptr;
    166.         }
    167.         //2、parent是子树的根，也就是parent结点上面还有祖先结点
    168.         else
    169.         {
    170.             if(ppNode->_left==parent)
    171.             {
    172.                 ppNode->_left=subR;
    173.             }
    174.             else
    175.             {
    176.                 ppNode->_right=subR;
    177.             }
    178.             subR->_parent=ppNode;
    179.         }
    180.         //修改平衡因子
    181.         subR->_bf=parent->_bf=0;
    182.     }
    183.  
    184.     //右旋
    185.     void RotateR(Node* parent)
    186.     {
    187.         Node*subL=parent->_left;
    188.         Node*subLR=subL->_right;
    189.  
    190.         parent->_left=subLR;
    191.         //修改三叉链表里面的父亲节点
    192.         if(subLR)
    193.         {
    194.             subLR->_parent=parent;
    195.         }
    196.         Node* ppNode=parent->_parent;
    197.  
    198.         subL->_right=parent;
    199.         parent->_parent=subL;
    200.         //1.parent是整个子树的根
    201.         if(parent==_root)
    202.         {
    203.             _root=subL;
    204.             subL->_parent= nullptr;
    205.         }
    206.         //2.parent是子树的根，也就是parent结点上面还有祖先结点
    207.         else
    208.         {
    209.             if(ppNode->_left==parent)
    210.             {
    211.                 ppNode->_left=subL;
    212.             }
    213.             else
    214.             {
    215.                 ppNode->_right=subL;
    216.             }
    217.             subL->_parent=ppNode;
    218.         }
    219.         //修改平衡因子
    220.         subL->_bf=parent->_bf=0;
    221.     }
    222.  
    223.     //左右旋
    224.     void RotateLR(Node* parent)
    225.     {
    226.         Node* subL=parent->_left;
    227.         Node* subLR=subL->_right;
    228.         int bf=subLR->_bf;
    229.  
    230.         RotateL(parent->_left);
    231.         RotateR(parent);
    232.  
    233.         //平衡因子的更新
    234.         //对上面的三种情况分别更改平衡因子
    235.         subLR->_bf=0;
    236.         //case1
    237.         if(bf==1)
    238.         {
    239.             parent->_bf=0;
    240.             subL->_bf=-1;
    241.         }
    242.         //case2
    243.         else if(bf==-1)
    244.         {
    245.             parent->_bf=1;
    246.             subL->_bf=0;
    247.         }
    248.         //case3
    249.         else if(bf==0)
    250.         {
    251.             parent->_bf=0;
    252.             subL->_bf=0;
    253.         }
    254.         else
    255.         {
    256.             assert(false);
    257.         }
    258.     }
    259.  
    260.     //左右旋
    261.     void RotateRL(Node* parent)
    262.     {
    263.         Node* subR=parent->_right;
    264.         Node* subRL=subR->_left;
    265.         int bf=subRL->_bf;
    266.  
    267.         RotateR(parent->_right);
    268.         RotateL(parent);
    269.  
    270.         //平衡因子的更新
    271.         //对上面的三种情况分别更改平衡因子
    272.         subRL->_bf=0;
    273.         //case1
    274.         if(bf==1)
    275.         {
    276.             parent->_bf=-1;
    277.             subR->_bf=0;
    278.         }
    279.             //case2
    280.         else if(bf==-1)
    281.         {
    282.             parent->_bf=0;
    283.             subR->_bf=1;
    284.         }
    285.             //case3
    286.         else if(bf==0)
    287.         {
    288.             parent->_bf=0;
    289.             subR->_bf=0;
    290.         }
    291.         else
    292.         {
    293.             assert(false);
    294.         }
    295.     }
    296.     void _InOrder(Node* root)
    297.     {
    298.         if (root == nullptr)
    299.         {
    300.             return;
    301.         }
    302.  
    303.         _InOrder(root->_left);
    304.         cout << root->_kv.first << ":" << root->_kv.second << endl;
    305.         _InOrder(root->_right);
    306.     }
    307.  
    308.    
    309. private:
    310.     Node* _root=nullptr;
    311.  
    312. };
    313.  
    314.  
    315. #endif //AVL_AVLTREE_H

     

    1. void TestAVLTree1()
    2. {
    3.     int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    4.     AVLTree<int, int> t1;
    5.     for (auto e : a)
    6.     {
    7.         t1.Insert(make_pair(e, e));
    8.     }
    9.  
    10.     t1.InOrder();
    11. }

     

    检查是不是平衡二叉树

     但是中序遍历有序，只能说明我们的avl树是一棵搜索树，并不能直接说明是平衡二叉树，我们也不能靠检查平衡因子的方式去检查，因为我们代码运行的条件就是检查的平衡因子。所以不能这么查。我们这里不妨查平衡二叉树的高度来检查是不是平衡二叉树

    求高度

    1. int Height(Node* root)
    2.     {
    3.         if (root == nullptr)
    4.             return 0;
    5.  
    6.         return max(Height(root->_left), Height(root->_right)) + 1;
    7.     }
    1. bool _IsBalance(Node* root)
    2.     {
    3.         if (root == nullptr)
    4.         {
    5.             return true;
    6.         }
    7.  
    8.         int leftHT = Height(root->_left);
    9.         int rightHT = Height(root->_right);
    10.         int diff = rightHT - leftHT;
    11.  
    12.         if (diff != root->_bf)
    13.         {
    14.             cout << root->_kv.first << "平衡因子异常" << endl;
    15.             return false;
    16.         }
    17.  
    18.         return abs(diff) < 2
    19.                && _IsBalance(root->_left)
    20.                && _IsBalance(root->_right);
    21.     }

     测试

    1. void TestAVLTree1()
    2. {
    3.     int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
    4. //    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    5.     AVLTree<int, int> t1;
    6.     for (auto e : a)
    7.     {
    8.         t1.Insert(make_pair(e, e));
    9.     }
    10.  
    11.     t1.InOrder();
    12.     cout <<"IsBalance:"<IsBalance() << endl;
    13. }

     

     

     随机插入一组数据测试

    1. void TestAVLTree2()
    2. {
    3.     size_t N = 10000;
    4.     srand(time(0));
    5.     AVLTree<int, int> t1;
    6.     for (size_t i = 0; i < N; ++i)
    7.     {
    8.         int x = rand();
    9.         t1.Insert(make_pair(x, i));
    10.         /*	bool ret = t1.IsBalance();
    11.             if (ret == false)
    12.             {
    13.                 int u = 1;
    14.             }
    15.             else
    16.             {
    17.                 cout << "Insert:" << x << " IsBalance:" <
    18.             }*/
    19.     }
    20.     cout << "IsBalance:" << t1.IsBalance() << endl;
    21. }

     

  • 相关阅读:
    Bert相关面试题整理
    Dubbo—— 一个服务既是消费者又是提供者
    【Spring面试】八、事务相关
    积分商城游戏能够给商家带来什么？怎么搭建积分商城?
    CentOS 环境 SIPp 安装及使用
    b2b2c o2o 多商家入驻商城 直播带货商城 电子商务
    攻防世界_MISC之碎纸机11
    Photoshop图层混合模式公式(Unity，CG实现)
    WinHex(三)
    javaweb没有web.xml设置方法
  • 原文地址：https://blog.csdn.net/weixin_62684026/article/details/127585338