• 【C++】map&set的底层结构 -- AVL树（高度平衡二叉搜索树）

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

    一、AVL树（高度平衡二叉搜索树）

    1、概念

    二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
    • 最优情况下，有 n 个结点的二叉搜索树为完全二叉树，查找效率为：O(log₂N)。
    • 最差情况下，有 n 个结点的二叉搜索树退化为单支树，查找效率为：O(N)。
    因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中 插入新结点 后，如果能 保证每个结点的左右子树高度之差的绝对值不超过 1 （需要对树中的结点进行调整），即可降低树的高度，从而减少平均 搜索长度。
    一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
    • 它的左右子树都是 AVL 树。
    • 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1/0/1）。

    如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log₂n)，搜索时间复杂度 O(log₂n)。

    为什么左右子树高度差不规定成0呢？

    因为在 2、4 等节点数的情况下，不可能做到左右高度相等的情况。

    2、AVL 树节点的定义

    AVL 树节点的定义：
    AVL 树节点是一个 三叉链结构，除了 指向左右孩子的指针，还有一个 指向其父亲的指针，数据域是键值对，即 pair 对象，还引入了平衡因子，用来判断是否需要进行平衡操作。 
    1. // AVL树节点的定义（KV模型）
    2. template<class K, class V>
    3. struct AVLTreeNode
    4. {
    5.     AVLTreeNode* _left;   // 该节点的左孩子
    6.     AVLTreeNode* _right;  // 该节点的右孩子
    7.     AVLTreeNode* _parent; // 该节点的双亲指针
    8.  
    9.     pair _kv;          // 键值对
    10.     int _bf;                 // 该节点的平衡因子(balance factor) = 右子树高度-左子树高度
    11.  
    12.     // 构造函数
    13.     AVLTreeNode(const pari& kv)
    14.         : _left(nullptr)
    15.         , _right(nullptr)
    16.         , _parent(nullptr)
    17.         , _kv(kv)
    18.         , _bf(0)
    19.     {}
    20. };
    21.  
    22. // AVL树的定义（KV模型）
    23. template<class K, class V>
    24. class AVLTree
    25. {
    26. 	typedef AVLTreeNode Node;
    27. public:
    28. 	// 成员函数
    29.  
    30. private:
    31. 	Node* _root;
    32. }

    3、AVL树的插入

    AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：
    1. 按照二叉搜索树的方式插入新节点到 AVL 树中。
    2. 新节点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡（控制树的平衡（旋转操作））。
    1. // 插入节点
    2. bool Insert(const pair& kv)
    3. {
    4.     // 如果树为空，则直接插入节点
    5.     if (_root == nullptr)
    6.     {
    7. 		_root = new Node(kv);
    8. 		return true;
    9. 	}
    10.  
    11. 	// 如果树不为空，找到适合插入节点的空位置
    12.     Node* parent = nullptr; // 记录当前节点的父亲
    13.     Node* cur = _root;      // 记录当前节点
    14.  
    15.     while (cur) // while循环结束，说明找到适合插入节点的空位置了
    16.     {
    17.         if(kv.first > cur->_kv.first) // 插入节点键值k大于当前节点
    18.         {
    19.             parent = cur;
    20.             cur = cur->_right;
    21.         }
    22.         else if(kv.first < cur->_kv.first) // 插入节点键值k小于当前节点
    23.         { 
    24.             parent = cur;
    25.             cur = cur->_left;
    26.         }
    27.         else // 插入节点键值k等于当前节点
    28.         {
    29.             return false;
    30.         }
    31.     }
    32.     
    33.     // 插入新节点
    34.     cur = new Node(kv); // 申请新节点
    35.     // 判断当前节点是父亲的左孩子还是右孩子
    36.     if (cur->_kv.first > parent->_kv.first)
    37.     {
    38.         parent->_right = cur;     
    39.  
    40.     }
    41.     else
    42.     {
    43.         parent->_left = cur;
    44.     }
    45.     cur->_parent = parent;
    46.  
    47.     // 控制平衡
    48. 	// 1、更新平衡因子
    49.     
    50.     // ...
    51.  
    52.     return true;
    53. }

    ⚪更新平衡因子

    （1）插入新节点cur 插入后，parent 的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1，0，1，分以下两种情况：
    • 如果 cur 插入到 新节点父亲（parent） 的左侧，只需给 父亲（parent） 的平衡因子--（_bf--）即可。
    • 如果 cur 插入到 新节点父亲（parent） 的右侧，只需给 父亲（parent） 的平衡因子++（_bf++）即可。
     （2）新节点父亲的平衡因子更新以后，又会分为 3 种情况：

    此时：parent的平衡因子可能有三种情况：0，正负 1， 正负 2。

    1. 如果更新以后，parent 的平衡因子是 0（则说明插入之前 parent 的平衡因子之前一定为 1/-1），说明父亲所在子树高度没变（因为把矮的那边给填补上了），此时满足 AVL 树的性质，插入成功，不需要继续往上更新。
    2. 如果更新以后，parent 的平衡因子是 1/-1（则说明插入之前 parent 的平衡因子 一定为 0），说明父亲所在子树高度增加，需要继续往上更新。（最坏情况：往上一直更新到根节点）。
    3. 如果更新以后，parent 的平衡因子是 2/-2，说明父亲所在子树出现了不平衡，需要对其进行旋转处理。
    1. // 插入节点
    2. bool Insert(const pair& kv)
    3. {
    4.     // 控制平衡
    5. 	// 1、更新平衡因子
    6.     
    7.     while (parent) // 最坏情况：更新到根节点
    8.     {
    9.         // 更新双亲的平衡因子
    10.         if (cur == parent->_left) // 新节点插入在父亲的左边
    11.             parent->_bf--;
    12.         else // 新节点插入在父亲的右边
    13.             parent->_bf++;
    14.  
    15.         // 更新后检测双亲的平衡因子
    16.         if (0 == pParent->_bf)
    17.         {    
    18.             break;
    19.         }
    20.  
    21.         //else if (1 == parent->_bf || -1 == parent->_bf)
    22.         else if (abs(parent->_bf) == 1) // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
    23.         {
    24.             cur = parent;
    25.             parent = cur->_parent;
    26.         }
    27.  
    28.         else if (abs(parent->_bf) == 2) // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以parent为根的树进行旋转处理
    29.         {
    30.             // 1、父节点的右边高，左边低，需要往左旋
    31.             if (parent->_bf == 2 && cur->_bf == 1) 
    32. 		    {
    33. 				RotateL(parent); // 左单旋
    34. 			}
    35.  
    36.             // 2、父节点的左边高，右边低，需要往右旋
    37. 			else if ((parent->_bf == -2 && cur->_bf == -1))
    38. 			{
    39. 				RotateR(parent); // 右单旋
    40. 			}
    41.             
    42.             // 3、父节点的左边高，且父节点左孩子的右边高
    43. 			else if (parent->_bf == -2 && cur->_bf == 1) 
    44. 			{
    45. 				RotateLR(parent); // 左右双旋
    46. 			}
    47.  
    48.             // 4、父节点的右边高，且父节点右孩子的左边高
    49.             else if (parent->_bf == 2 && cur->_bf == -1)
    50. 			{
    51. 				RotateRL(parent); // 右左双旋
    52. 			}
    53.  
    54. 			break; // 旋转完成，树已平衡，退出循环
    55.         }
    56.  
    57.         // 除了上述3种情况，平衡因子不可能有其它的值，报错处理
    58.         else
    59.         {
    60.             assert(false);
    61.         }
    62.     }
    63.     return true;
    64. }

    4、AVL树的旋转

    如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。
    根据节点插入位置的不同，AVL 树的旋转分为四种：

    旋转的本质：在遵循二叉搜索树的规则下，让左右均衡，降低整棵树的高度。

    该进行哪种旋转操作？

    引发旋转的路径是直线就是单旋，如果是折线就是双旋。

    注意：此处看到的树，可能是一颗完整的树，也可能是一颗子树。

    （1）新节点插入较高左子树的左侧 —— 左左：右单旋

    将新的节点插入到了 parent 左孩子的左子树上，导致的不平衡的情况。

    上图在插入前，AVL 树是平衡的，新节点插入到 30 的左子树（注意：此处不是左孩子）中，30 左子树增加了一层，导致以 60 为根的二叉树不平衡，要让 60 平衡，只能将 60 左子树的高度减少一层，右子树增加一层，即将左子树往上提，这样 60 转下来，因为 60 比 30 大，只能将其放在 30 的右子树，而如果 30 有右子树，右子树根的值一定大于 30，小于 60，只能将其放在 60 的左子树，旋转完成后，更新节点的平衡因子即可。

    【引发右单旋的条件】

    • 父亲左边高，右边低，所以要让父亲往右旋。
    • parent 的平衡因子为 -2，parent 左孩子平衡因子为 -1，观察发现，平衡因子都是负数，说明是左边高，也说明了引发旋转的路径是一条直线，所以我们要右旋操作。

    【右单旋操作】

    1、让 subL 的右子树 subLR 成为 parent 的左子树（因为 subLR 的右子树根节点值 > 30，< 60）。
    2、让 parent 成为 subL 的右子树（因为 60 > 30）。
    3、让 subL 变成这个子树的根。

    这一步操作前需要先判断下：parent 是根节点，还是一个普通子树

    • 如果是根节点，旋转完成后，则更新 subL 为新的根节点。
    • 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subL 为这个子树的根节点。

    4、根据树的结构，更新 parent 和 subL 的平衡因子为 0。

    在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：

    • 30 节点的右孩子可能存在，也可能不存在。（subL 的右子树 subLR 可能存在，也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向）。
    • 60 可能是根节点，也可能是子树。（旋转完成后，subL 的双亲节点，可能是空，也可能是 parent 原先的父节点。所以在更新 subL 的双亲指针前需要判断下）。

    依次调整 subLR、parent、subL 的位置和双亲指针的指向。 

    1. // 右单旋
    2. void _RotateR(Node* parent)
    3. {  
    4.     Node* subL = parent->_left; // subL : parent的左孩子
    5. 	Node* subLR = subL->_right; // subLR : parent左孩子的右孩子
    6.  
    7.     // 旋转完成之后，让subL的右子树subLR成为parent的左子树
    8.     parent->_left = subLR;
    9.     // 如果subLR存在，更新subLR的双亲指针，指向parent
    10.     if (subLR)
    11. 	{
    12. 		subLR->_parent = parent;
    13. 	}
    14.     
    15.     // 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点
    16.     Node* ppNode = parent->_parent;
    17.     
    18.     // 让parent成为subL的右子树
    19.     subL->_right = parent;
    20.     // 更新parent的双亲指针，指向subL
    21.     parent->_parent = subL;
    22.  
    23.     // 如果parent是根节点，根新指向根节点的指针
    24.     if (_root == parent)
    25. 	{
    26. 		_root = subL;            // 更新subL为新的根
    27. 		subL->_parent = nullptr; // 更新subL的双亲指针，指向空
    28. 	}
    29.     // parent不是根节点，就是一个普通子树
    30.     else
    31.     {
    32.         // 判断parent原先是左孩子还是右孩子
    33.         if (ppNode->_left == parent)
    34. 		{
    35. 			ppNode->_left = subL; // parent原先的双亲节点接管subL，subL为这个子树的根
    36. 		}
    37. 		else
    38. 		{
    39. 			ppNode->_right = subL;
    40. 		}
    41.         subL->_parent = ppNode; // 更新subL的双亲指针
    42.     }
    43.  
    44.     // 根据调整后的结构更新部分节点的平衡因子
    45.     parent->_bf = pSubL->_bf = 0;
    46. }
    （2）新节点插入较高右子树的右侧 —— 右右：左单旋

    【引发左单旋的条件】

    • 父亲右边高，左边低，所以要让父亲往左旋。
    • parent 的平衡因子为 2，parent 左孩子平衡因子为 1，观察发现，平衡因子都是正数，说明是右边高，也说明了引发旋转的路径是一条直线，所以我们要右旋操作。

    【右单旋操作】

    1、让 subR 的左子树 subRL 成为 parent 的右子树（因为 subRL 的左子树根节点值 > 30，< 60）。
    2、让 parent 成为 subR 的左子树（因为 30 < 60）。
    3、让 subR 变成这个子树的根。

    这一步操作前需要先判断下：parent 是根节点，还是一个普通子树

    • 如果是根节点，旋转完成后，则更新 subR 为新的根节点。
    • 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subR 为这个子树的根节点。

    4、根据树的结构，更新 parent 和 subR 的平衡因子为 0。

    在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：

    • subR 的左子树 subRL 可能存在，也可能为空。（当不为空时才更新 subR 左子树 subRL 的双亲指针指向）。
    • 旋转完成后，subR 的双亲节点，可能是空，也可能是 parent 原先的父节点。（所以更新 subR 的双亲指针前需要判断下）。

    依次调整 subRL、parent、subR 的位置和双亲指针的指向。

    1. // 左单旋
    2. void treeRotateLeft(Node* parent)
    3. {
    4.     Node* subR = parent->_right; // subR：父亲的右孩子
    5.     Node* subRL = subR->_left; // subRL：父亲的右孩子的左孩子（大于父亲，小于subR）
    6.  
    7.     // 让subRL成为父亲的右子树
    8.     parent->_right = subRL;
    9.     // 如果subRL不为空
    10.     if (subRL)
    11.     {
    12.         subRL->_parent = parent; // 更新subRL双亲指针，指向parent
    13.     }
    14.  
    15.     // 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点
    16.     Node* ppNode = parent->_parent;
    17.     
    18.     // 让parent成为subR的左子树
    19.     subR->_left = parent; 
    20.     // 更新parent双亲指针的指向
    21.     parent->_parent = subR;
    22.  
    23.     // 判断parent是不是根节点
    24.     if (parent == _root)
    25.     {
    26.         _root = subR;            // subR为新的根
    27.         subR->_parent = nullptr; // subR双亲指针指向空
    28.     }
    29.  
    30.     // 不是根节点，就是一个普通子树
    31.     else
    32.     {
    33.         // 判断parent原先是左孩子还是右孩子
    34.         if (ppNode->_left == parent)
    35.         {
    36.             ppNode->_left = subR; // parent原先的双亲节点接管subR，subR为这个子树的根
    37.         }
    38.         else
    39.         {
    40.             ppNode->_right = subR;
    41.         }
    42.         subR->_parent = ppNode; // 更新subR的双亲指针
    43.     }
    44.  
    45.     // 根据树的结构，更新parent和subR的平衡因子
    46.     parent->_bf = subR->_bf = 0;
    47. }
    （3）新节点插入较高左子树的右侧 —— 左右：先左单旋再右单旋（左右双旋）

    将新的节点插入到了 parent 左孩子的右子树上，导致的不平衡的情况。

    这时我们需要的是先对 parent 的右孩子进行一次左旋，再对 parent 进行一次右旋。

    将双旋变成单旋后再旋转，即：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。

    旋转之前，60 的平衡因子可能是 -1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整。

    【h == 0】 

    【引发双旋的条件】

    引发旋转的路径是直线就是单旋，如果是折线就是双旋。


    parent 的平衡因子为 -2，parent 左孩子的平衡因子为 1，观察发现，平衡因子是一负一正，说明左孩子右边高，父亲左边高，也说明了引发旋转的路径是一条折线，所以我们要先对左孩子进行左旋操作，再对父亲进行右旋操作。

    左右双旋操作后，根据树的结构，更新平衡因子时，需要注意：

    插入新节点的位置不同，经过左右双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有以下三种情况：

    1. 新节点插入到了 parent 左孩子的右子树的左边。
    2. 新节点插入到了 parent 左孩子的右子树的右边。
    3. 新节点就是 parent 左孩子的右孩子。

    这里可以观察到一个现象，根据这个现象就很好推出旋转后的平衡因子：

    节点 60 的左右子树被分走了，左子树最终成为了节点 30 的右子树，右子树最终成了节点 90 的左子树。

    1. void _RotateLR(PNode pParent)
    2. {
    3.     Node* subL = parent->_left; // 记录parent的左孩子
    4.     Node* subLR = subL->_right; // 记录parent的左孩子的右孩子
    5.     
    6.     // 旋转之前，因为插入新节点的位置不同，subLR的平衡因子可能是-1/0/1
    7.     int bf = subLR->_bf; // 记录subLR的平衡因子
    8.     
    9.     // 先对parent的左孩子进行左单旋
    10.     RotateL(parent->_left);
    11.     // 再对parent进行右单旋
    12.     RotateR(parent);
    13.  
    14.     // 旋转完成之后，根据情况对其他节点的平衡因子进行调整
    15.     subLR->_bf = 0;
    16.     if (bf == -1)
    17. 	{
    18. 		parent->_bf = 1;
    19. 		subL->_bf = 0;
    20. 	}
    21. 	else if (bf == 1)
    22. 	{
    23. 		parent->_bf = 0;
    24. 		subL->_bf = -1;
    25. 	}	
    26. 	else if (bf == 0)
    27. 	{
    28. 		parent->_bf = 0;
    29. 		subL->_bf = 0;
    30. 	}
    31. 	else
    32. 	{
    33. 		assert(false);
    34. 	}
    35. }
    （4）新节点插入较高右子树的左侧 —— 右左：先右单旋再左单旋（右左双旋）​​​​​​​

    将新的节点插入到了 parent 右孩子的左子树上，导致的不平衡的情况。

    这时我们需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋。

    【h == 1】

    【引发双旋的条件】

    引发旋转的路径是直线就是单旋，如果是折线就是双旋。
    parent 的平衡因子为 2， parent 右孩子平衡因子为 -1，观察发现，平衡因子是一正一负，说明右孩子左边高，父亲右边高，也说明了引发旋转的路径是一条折线，所以我们要先对右孩子进行右旋操作，再对父亲进行左旋操作。

    左右双旋操作后，根据树的结构，更新平衡因子时，需要注意：

    插入新节点的位置不同，经过右左双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有以下三种情况：

    • 新节点插入到了 parent 右孩子的左子树的左边。
    • 新节点插入到了 parent 右孩子的左子树的右边。
    • 新节点就是 parent 右孩子的左孩子。

    这里可以观察到一个现象，根据这个现象就很好推出旋转后的平衡因子：

    节点 60 的左右子树被分走了，左子树 b 最终成了节点 30 的右子树，右子树 c 最终成了节点 90 的左子树。

    1. // 右左双旋
    2. void treeRotateRL(Node* parent)
    3. {
    4.     Node* subR = parent->_right; // 记录parent的右孩子
    5.     Node* subRL = subR->_left;   // 记录parent的右孩子的左孩子
    6.  
    7.     // 旋转之前，因为插入新节点的位置不同，subRL的平衡因子可能为-1/0/1
    8.     int bf = subRL->_bf; // 记录subRL的平衡因子
    9.  
    10.     RotateR(parent->_right); // 先对parent的右孩子进行右单旋
    11.     RotateL(parent);         // 再对parent进行左单选
    12.  
    13.     // 旋转完成之后，根据树的结构对其他节点的平衡因子进行调整
    14.     subRL->_bf = 0;
    15.     if (bf == -1)
    16.     {
    17.         parent->_bf = 0;
    18.         subR->_bf = 1;
    19.     }
    20.     else if (bf == 1)
    21.     {
    22.         parent->_bf = -1;
    23.         subR->_bf = 0;
    24.     }
    25.     else if(bf == 0)
    26.     {
    27.         parent->_bf = 0;
    28.         subR->_bf = 0;
    29.     }
    30.     else
    31.     {
    32.         assert(false);
    33.     }
    34. }
    【总结】
    假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2/-2，分以下情况考虑：
    1、parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR。
    • 当 subR 的平衡因子为 1 时，执行左单旋。
    • 当 subR 的平衡因子为 -1 时，执行右左双旋。
    2、parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL。
    • 当 subL 的平衡因子为 -1 时，执行右单旋。
    • 当 subL 的平衡因子为 1 时，执行左右双旋。

    旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。

    5、AVL树的验证

    AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：
    1、验证其为二叉搜索树
    • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
    2、验证其为平衡树
    • 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）。
    • 节点的平衡因子是否计算正确。
    （1）首先写一个计算当前树高度的函数
    1. // 计算当前树的高度
    2. int Height(Node* root)
    3. {
    4.     // 当前树为空，则高度为0
    5.     if (root == nullptr)
    6.         return 0;
    7.  
    8.     // 当前树的高度 = 左右子树中高度最大的那个加1
    9.     return max(Height(root->_left), Height(root->_right)) + 1;
    10. }
    （2）检查AVL树是否平衡：【思路一】自顶向下的暴力解法
    1. bool IsBalance1()
    2. {
    3. 	return _IsBalance(_root);
    4. }
    5.  
    6. bool _IsBalance1(Node* root)
    7. {
    8.     // 当前树为空，说明是平衡的
    9. 	if (root == nullptr)
    10. 		return true;
    11.  
    12.     // 当前树不为空，计算左右子树的高度
    13. 	int leftHT = Height(root->_left);
    14. 	int rightHT = Height(root->_right);
    15. 	int diff = rightHT - leftHT;
    16.  
    17. 	if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
    18. 	{
    19. 		cout << root->_kv.first << "平衡因子异常" << endl;
    20. 		return false;
    21. 	}
    22.  
    23.     // 左右子树高度相减的绝对值小于2，说明当前树是平衡的，则继续往下判断其它子树
    24. 	return abs(diff) < 2
    25. 		&& _IsBalance(root->_left)
    26. 		&& _IsBalance(root->_right);
    27. }
    （3）检查AVL树是否平衡【思路二】自底向上的高效解法（动态规划，前一个子问题的解，能够用于后一个问题求解）
    1. bool IsBalance2()
    2. {
    3.     return _IsBalance2(_root) != -1;
    4. }
    5.  
    6. int _IsBalance2(Node* root)
    7. {
    8.     // 先判断当前树的左、右子树是否平衡，再判断当前树是否平衡
    9.     // 不平衡返回-1，平衡则返回当前树的高度
    10.  
    11.     // 当前树为空，返回高度0
    12.     if (root == nullptr)
    13.         return 0;
    14.  
    15.     // 当前树不为空，分别计算左右子树的高度
    16.     int leftHeight = _IsBalance2(root->_left);
    17.     int rightHeight = _IsBalance2(root->_right);
    18.     int diff = rightHT - leftHT;
    19.     
    20.     if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
    21.     {
    22.         cout << "平衡因子异常:" << root->_kv.first << endl;
    23.     }
    24.     
    25.     // 左子树高度等于-1、右子树高度等于-1、左右子树高度差的绝对值大于1，说明当前树不平衡
    26.     if (leftHeight == -1 || rightHeight == -1 || abs(diff) > 1)
    27.         return -1;
    28.  
    29.     // 运行到这里来了，说明当前树是平衡的，返回当前树的高度
    30.     return max(leftHeight, rightHeight) + 1;
    31. }
    （4）【思路三】
    1. bool _IsBalanceTree3(Node* root)
    2. {
    3.     // 空树也是AVL树
    4.     if (nullptr == root)
    5.         return true;
    6.     
    7.     // 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    8.     int leftHeight = _Height(root->_left);
    9.     int rightHeight = _Height(root->_right);
    10.     int diff = rightHeight - leftHeight;
    11.  
    12.     // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者pRoot平衡因子的绝对值超过1，则一定不是AVL树
    13.     if (diff != root->_bf || (diff > 1 || diff < -1))
    14.         return false;
    15.  
    16.     // pRoot的左和右如果都是AVL树，则该树一定是AVL树
    17.     return _IsBalanceTree3(root->_left) && _IsBalanceTree3(root->_right);
    18.  }
    3、验证用例
    • 常规场景 1：{16, 3, 7, 11, 9, 26, 18, 14, 15}
    • 特殊场景 2：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

    6、AVL树的删除（了解） 

    因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
    具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

    7、AVL 树的性能

    AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即 O(logN)。
    但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
    因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。
  • 相关阅读:
    三个步骤搞定 MySQL，offer到手。
    Haskell中的数据交换：通过http-conduit发送JSON请求
    在 ubuntu20.04 上安装 Pytorch
    SLAM相关手撕代码题
    P30 JComboBox下拉列表框
    微信小程序项目实例停车场车辆登记+后台
    .NET周刊【2月第2期 2024-02-11】
    绘制一条透明背景的trace，并保存；
    308. 二维区域和检索 - 可变 线段树/哈希
    conda 安装tensorflow一些命令
  • 原文地址：https://blog.csdn.net/weixin_74531333/article/details/133913852