目录AVL 树AVL树节点的定义AVL树的插入AVL树的旋转1. 新节点插入较高左子树的左侧---左左右单旋2. 新节点插入较高右子树的右侧---右右左单旋3. 新节点插入较高左子树的右侧---左右先左单旋再右单旋4. 新节点插入较高右子树的左侧---右左先右单旋再左单旋AVL树的验证关于AVL树的性能AVL树总代码AVL 树AVL树是一种自平衡的二叉搜索树。它的核心特点是在插入或删除节点后会通过旋转操作自动调整树的结构确保任何节点的左右子树高度差不超过1从而维持树的平衡保证查找、插入、删除等操作的时间复杂度稳定在O(log n)。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。定义• 左右子树都是 AVL• 左右子树高度差绝对值不超过 1• 这个高度差叫平衡因子通常是 -1/0/1• 若有 n 个结点高度可保持在 O(log₂ n)搜索复杂度也为 O(log₂ n)AVL树节点的定义templateclass T struct AVLTreeNode { AVLTreeNode(const T data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} T _data; // 节点存储的数据 AVLTreeNodeT* _left; // 左孩子 AVLTreeNodeT* _right; // 右孩子 AVLTreeNodeT* _parent; // 父节点 int _bf; // 平衡因子右子树高度 - 左子树高度 };AVL树的插入AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步1. 按照二叉搜索树的方式插入新节点2. 调整节点的平衡因子Insert是 AVL 树中最核心的接口之一它的任务不是单纯把数据插进去而是要在插入完成后继续维护整棵树的平衡性这个函数整体可以分成两大阶段按照二叉搜索树的规则找到插入位置并把新节点挂上去从新节点的父节点开始沿着父节点链一路向上更新平衡因子如果发现某个祖先节点失衡就立即旋转修复第一阶段AVL 树本质上还是一棵二叉搜索树所以插入时仍然遵循二叉搜索树的规则比当前节点小往左走比当前节点大往右走如果相等通常直接返回false表示不插入重复值找到空位置以后创建新节点并把它挂到父节点的左边或者右边。这一部分和普通二叉搜索树插入没有区别第二阶段新节点插入以后不是所有祖先节点都会失衡但新节点到根节点这一条路径上的节点平衡因子都可能受到影响所以要从新节点的父节点开始向上调整这里要先统一平衡因子的定义本实现中平衡因子定义为右子树高度 - 左子树高度所以更新规则是新节点插入到父节点左边父节点左子树变高父节点_bf--新节点插入到父节点右边父节点右子树变高父节点_bf父节点更新完以后平衡因子只可能出现三类结果parent-_bf 0说明插入前父节点的平衡因子一定是1或-1插入以后刚好抵消成0。这表示虽然当前节点左右子树高度关系发生了变化但以当前父节点为根的整棵子树高度并没有继续增加。既然这棵子树高度没变那它上面的祖先节点也就不会再受到影响所以可以直接停止更新parent-_bf 1或parent-_bf -1说明插入前父节点的平衡因子一定是0插入以后变成了1或-1。这表示父节点原来左右一样高现在其中一边多了一层因此以父节点为根的这棵子树高度增加了。既然子树高度增加了那么它的父节点也可能继续受影响所以必须继续向上更新parent-_bf 2或parent-_bf -2说明当前父节点已经失衡不再满足 AVL 树的要求。这时不能继续单纯向上更新而必须对这棵失衡子树做旋转处理parent-_bf 2说明右边高parent-_bf -2说明左边高接下来还要根据孩子节点的平衡因子进一步区分是单旋还是双旋右边高时可能是RR或RL左边高时可能是LL或LRbool Insert(const T data) { // 1. 如果当前树为空直接创建根节点即可 if (_root nullptr) { _root new Node(data); return true; } // 2. 先按二叉搜索树规则查找插入位置 Node* parent nullptr; Node* cur _root; while (cur ! nullptr) { parent cur; // 如果待插入值比当前节点小继续去左子树找位置 if (data cur-_data) { cur cur-_left; } // 如果待插入值比当前节点大继续去右子树找位置 else if (data cur-_data) { cur cur-_right; } // 如果值已经存在这里不允许重复插入直接返回 false else { return false; } } // 3. 找到空位置后创建新节点并挂到 parent 下面 Node* newNode new Node(data); newNode-_parent parent; if (data parent-_data) { parent-_left newNode; } else { parent-_right newNode; } // 4. 从新节点开始沿着父链向上更新平衡因子 cur newNode; parent newNode-_parent; while (parent ! nullptr) { // 4.1 新节点在父节点左边父节点左子树变高所以平衡因子减 1 if (cur parent-_left) { parent-_bf--; } // 4.2 新节点在父节点右边父节点右子树变高所以平衡因子加 1 else { parent-_bf; } // 4.3 如果父节点平衡因子变成 0说明这棵子树高度没有继续增长更新结束 if (parent-_bf 0) { break; } // 4.4 如果父节点平衡因子变成 1 或 -1说明这棵子树高度增加了要继续向上更新 else if (parent-_bf 1 || parent-_bf -1) { cur parent; parent parent-_parent; } // 4.5 如果父节点平衡因子变成 2 或 -2说明失衡需要旋转修复 else if (parent-_bf 2) { // 右边高了 2 层 // 如果右孩子的平衡因子是 1属于 RR做左单旋 if (parent-_right-_bf 1) { Node* subR parent-_right; _RotateL(parent); // RR 单旋完成后两个关键节点平衡因子都恢复为 0 parent-_bf 0; subR-_bf 0; } // 如果右孩子的平衡因子是 -1属于 RL做右左双旋 else { _RotateRL(parent); } // 插入场景下第一次失衡修复完成后即可结束 break; } else if (parent-_bf -2) { // 左边高了 2 层 // 如果左孩子的平衡因子是 -1属于 LL做右单旋 if (parent-_left-_bf -1) { Node* subL parent-_left; _RotateR(parent); // LL 单旋完成后两个关键节点平衡因子都恢复为 0 parent-_bf 0; subL-_bf 0; } // 如果左孩子的平衡因子是 1属于 LR做左右双旋 else { _RotateLR(parent); } // 插入场景下第一次失衡修复完成后即可结束 break; } } return true; }AVL树的旋转如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构 使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种左旋冲突的左孩变右孩。右旋则反之1. 新节点插入较高左子树的左侧---左左右单旋上图在插入前AVL树是平衡的新节点插入到30的左子树(注意此处不是左孩子)中30左 子树增加 了一层导致以60为根的二叉树不平衡要让60平衡只能将60左子树的高度减少一层右子 树增加一层 即将左子树往上提这样60转下来因为60比30大只能将其放在30的右子树而如果30有 右子树右子树根的值一定大于30小于60只能将其放在60的左子树旋转完成后更新节点 的平衡因子即可。在旋转过程中有以下几种情况需要考虑a. 30节点的右孩子可能存在也可能不存在b. 60可能是根节点也可能是子树如果是根节点旋转完成后要更新根节点如果是子树可能是某个节点的左子树也可能是右子树旋转的目标是把30提上去作为这棵子树新的根把60放到30的右边如果30原来有右子树b由于b的值一定大于30、小于60所以它只能挂到60的左边如果60原来就是整棵树的根要更新_root如果60原来只是某棵子树的根还要把它的新根30接回到祖父节点下面void _RotateR(Node* parent) { //右单旋 // parent 对应图中的 60 // subL 对应图中的 30 // subLR 对应图中 30 的右子树 b //先保存 parent 的左孩子也就是图中的 30 Node* subL parent-_left; //再保存 subL 的右孩子也就是图中的 b //旋转后b 要挂到 60 的左边所以这里必须提前保存 Node* subLR subL-_right; //右旋后60 会下沉成为 30 的右孩子 //那么原来 30 的右子树 b就要接到 60 的左边 parent-_left subLR; //如果 b 存在它换了父节点所以要把 b 的父节点改成 60 if (subLR ! nullptr) { subLR-_parent parent; } //先保存 60 原来的父节点 //因为 60 可能是整棵树的根也可能只是某棵子树的根 Node* ppNode parent-_parent; //把 60 放到 30 的右边 //这一步就对应图里“30 上升60 下沉到 30 的右侧” subL-_right parent; //更新 30 的父节点让它先接管 60 原来的位置 subL-_parent ppNode; //更新 60 的父节点因为现在 60 已经变成 30 的右孩子 parent-_parent subL; //如果 60 原来就是根节点 //那么右旋之后整棵树的新根就变成了 30 if (ppNode nullptr) { _root subL; } else { //如果 60 原来不是根节点 //那么要判断 60 原来挂在祖父节点的左边还是右边 //再把旋转后的新子树根 30 接回去 if (ppNode-_left parent) { ppNode-_left subL; } else { ppNode-_right subL; } } }2. 新节点插入较高右子树的右侧---右右左单旋这里是“新节点插入较高右子树的右侧”导致30的右边继续增高出现 RR 型失衡解决方法是做一次左单旋重点是要把60提上去把30压到60的左边如果60原来有左子树b因为b一定大于30小于60所以它只能挂到30的右边30可能是根也可能只是某棵子树的根所以还要处理祖父节点连接问题void _RotateL(Node* parent) { //左单旋 // parent 对应图中的 30 // subR 对应图中的 60 // subRL 对应图中 60 的左子树 b //先保存 parent 的右孩子也就是图中的 60 Node* subR parent-_right; //再保存 subR 的左孩子也就是图中的 b //旋转后b 要挂到 30 的右边所以这里必须提前保存 Node* subRL subR-_left; //左旋后30 会下沉成为 60 的左孩子 //那么原来 60 的左子树 b就要接到 30 的右边 parent-_right subRL; //如果 b 存在它换了父节点所以要把 b 的父节点改成 30 if (subRL ! nullptr) { subRL-_parent parent; } //先保存 30 原来的父节点 //因为 30 可能是整棵树的根也可能只是某棵子树的根 Node* ppNode parent-_parent; //把 30 放到 60 的左边 //这一步就对应图里“60 上升30 下沉到 60 的左侧” subR-_left parent; //更新 60 的父节点让它先接管 30 原来的位置 subR-_parent ppNode; //更新 30 的父节点因为现在 30 已经变成 60 的左孩子 parent-_parent subR; //如果 30 原来就是根节点 //那么左旋之后整棵树的新根就变成了 60 if (ppNode nullptr) { _root subR; } else { //如果 30 原来不是根节点 //那么要判断 30 原来挂在祖父节点的左边还是右边 //再把旋转后的新子树根 60 接回去 if (ppNode-_left parent) { ppNode-_left subR; } else { ppNode-_right subR; } } //在插入引发的 RR 场景中左单旋完成后 //parent 和 subR 的平衡因子都会恢复为 0 parent-_bf 0; subR-_bf 0; }3. 新节点插入较高左子树的右侧---左右先左单旋再右单旋这里是“新节点插入较高左子树的右侧”导致90左边高但30的右边又更高所以不能直接右旋.必须先把30左旋再把90右旋重点先把“双旋”拆成两个单旋去理解60会在双旋后变成新的子树根平衡因子不能简单统一清零必须看subLR旋转前的_bf将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再 考虑平衡因子的更新。void _RotateLR(Node* parent) { //左右双旋 // parent 对应图中的 90 // subL 对应图中的 30 // subLR 对应图中的 60 //先记录 parent 的左孩子 30 Node* subL parent-_left; //再记录 subL 的右孩子 60 //双旋完成后60 会成为这棵子树新的根 Node* subLR subL-_right; //在旋转前先保存 60 的平衡因子 //因为旋转完成后30 和 90 的平衡因子要根据它来决定 int bf subLR-_bf; //第一步先对 30 做左单旋 //这一步做完后60 会先上升到 30 的位置 _RotateL(subL); //第二步再对 90 做右单旋 //这一步做完后60 会最终成为整棵失衡子树的新根 _RotateR(parent); //双旋完成后中间节点 60 一定恢复平衡 subLR-_bf 0; //根据旋转前 60 的平衡因子修正 30 和 90 的平衡因子 if (bf -1) { // 说明新节点插入在 60 的左侧 // 旋转后90 会表现为右边稍高 parent-_bf 1; subL-_bf 0; } else if (bf 1) { // 说明新节点插入在 60 的右侧 // 旋转后30 会表现为左边稍高 parent-_bf 0; subL-_bf -1; } else { // bf 0 时说明 60 原本左右高度相同 // 旋转后 30、60、90 都恢复平衡 parent-_bf 0; subL-_bf 0; } }4. 新节点插入较高右子树的左侧---右左先右单旋再左单旋这里是“新节点插入较高右子树的左侧”导致30右边高但90的左边又更高所以不能直接左旋,必须先对90右旋再对30左旋.它和 LR 型完全对称void _RotateRL(Node* parent) { //右左双旋 // parent 对应图中的 30 // subR 对应图中的 90 // subRL 对应图中的 60 //先记录 parent 的右孩子 90 Node* subR parent-_right; //再记录 subR 的左孩子 60 //双旋完成后60 会成为这棵子树新的根 Node* subRL subR-_left; //在旋转前先保存 60 的平衡因子 //因为旋转完成后30 和 90 的平衡因子要根据它来决定 int bf subRL-_bf; //第一步先对 90 做右单旋 //这一步做完后60 会先上升到 90 的位置 _RotateR(subR); //第二步再对 30 做左单旋 //这一步做完后60 会最终成为整棵失衡子树的新根 _RotateL(parent); //双旋完成后中间节点 60 一定恢复平衡 subRL-_bf 0; //根据旋转前 60 的平衡因子修正 30 和 90 的平衡因子 if (bf -1) { // 说明新节点插入在 60 的左侧 // 旋转后90 会表现为右边稍高 parent-_bf 0; subR-_bf 1; } else if (bf 1) { // 说明新节点插入在 60 的右侧 // 旋转后30 会表现为左边稍高 parent-_bf -1; subR-_bf 0; } else { // bf 0 时说明 60 原本左右高度相同 // 旋转后 30、60、90 都恢复平衡 parent-_bf 0; subR-_bf 0; } }总结 假如以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑1. pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR 当pSubR的平衡因子为1时执行左单旋 当pSubR的平衡因子为-1时执行右左双旋2. pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是执行右单旋 当pSubL的平衡因子为1时执行左右双旋 旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。pParent-_bf 2看右孩子pSubRpSubR-_bf 1说明是RR执行左单旋pSubR-_bf -1说明是RL执行右左双旋pParent-_bf -2看左孩子pSubLpSubL-_bf -1说明是LL执行右单旋pSubL-_bf 1说明是LR执行左右双旋旋转完成后以原pParent为根的子树已经平衡不需要再向上更新AVL树的验证1. 验证其为二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确我们的平衡因子定义是右高 - 左高所以差值必须写成 rightHeight - leftHeightbool _IsBalanceTree(Node* root) const { // 空树也是 AVL 树 if (root nullptr) { return true; } // 计算左右子树高度 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); // 按照本实现的定义平衡因子 右高 - 左高 int diff rightHeight - leftHeight; // 如果现算出来的平衡因子和记录值不一致或者绝对值超过 1都不是 AVL 树 if (diff ! root-_bf || diff -1 || diff 1) { return false; } // 当前节点满足后还要继续检查左右子树是否也都满足 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);关于AVL树的性能AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即O(log n)。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。AVL树总代码#include iostream templateclass T struct AVLTreeNode { AVLTreeNode(const T data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} T _data; // 节点存储的数据 AVLTreeNodeT* _left; // 左孩子 AVLTreeNodeT* _right; // 右孩子 AVLTreeNodeT* _parent; // 父节点 int _bf; // 平衡因子右子树高度 - 左子树高度 }; templateclass T class AVLTree { using Node AVLTreeNodeT; public: AVLTree() : _root(nullptr) {} ~AVLTree() { _Destroy(_root); _root nullptr; } AVLTree(const AVLTree) delete; AVLTree operator(const AVLTree) delete; public: bool Insert(const T data) { // 1. 如果当前树为空直接创建根节点即可 if (_root nullptr) { _root new Node(data); return true; } // 2. 按照二叉搜索树规则查找插入位置 Node* parent nullptr; Node* cur _root; while (cur ! nullptr) { parent cur; // 如果待插入值更小继续去左子树查找 if (data cur-_data) { cur cur-_left; } // 如果待插入值更大继续去右子树查找 else if (data cur-_data) { cur cur-_right; } // 如果值相等这里不允许重复插入 else { return false; } } // 3. 创建新节点并挂到父节点下面 Node* newNode new Node(data); newNode-_parent parent; if (data parent-_data) { parent-_left newNode; } else { parent-_right newNode; } // 4. 从新节点开始向上更新平衡因子 cur newNode; parent newNode-_parent; while (parent ! nullptr) { // 如果当前节点是父节点的左孩子说明父节点左子树变高 if (cur parent-_left) { parent-_bf--; } // 如果当前节点是父节点的右孩子说明父节点右子树变高 else { parent-_bf; } // 5. 平衡因子变成 0说明这棵子树高度没有继续增长可以停止 if (parent-_bf 0) { break; } // 6. 平衡因子变成 1 或 -1说明这棵子树高度增加了要继续向上更新 else if (parent-_bf 1 || parent-_bf -1) { cur parent; parent parent-_parent; } // 7. 平衡因子变成 2说明右边过高需要做 RR 或 RL 调整 else if (parent-_bf 2) { // 右孩子平衡因子为 1属于 RR做左单旋 if (parent-_right-_bf 1) { Node* subR parent-_right; _RotateL(parent); // RR 单旋后这两个关键节点恢复平衡 parent-_bf 0; subR-_bf 0; } // 右孩子平衡因子为 -1属于 RL做右左双旋 else { _RotateRL(parent); } // 插入场景下第一次失衡修复完成后即可结束 break; } // 8. 平衡因子变成 -2说明左边过高需要做 LL 或 LR 调整 else if (parent-_bf -2) { // 左孩子平衡因子为 -1属于 LL做右单旋 if (parent-_left-_bf -1) { Node* subL parent-_left; _RotateR(parent); // LL 单旋后这两个关键节点恢复平衡 parent-_bf 0; subL-_bf 0; } // 左孩子平衡因子为 1属于 LR做左右双旋 else { _RotateLR(parent); } // 插入场景下第一次失衡修复完成后即可结束 break; } } return true; } void InOrder() const { //这是对外提供的中序遍历接口 //外部用户不需要传根节点直接调用这个公开函数即可 _InOrder(_root); std::cout std::endl; } int Height() const { return _Height(_root); } bool IsBalanceTree() const { return _IsBalanceTree(_root); } private: void _RotateL(Node* parent) { // 1. 保存右孩子和右孩子的左子树 Node* subR parent-_right; Node* subRL subR-_left; // 2. 让 parent 接住 subRL parent-_right subRL; // 3. 如果 subRL 存在要更新它的父节点 if (subRL ! nullptr) { subRL-_parent parent; } // 4. 保存 parent 原来的父节点 Node* ppNode parent-_parent; // 5. 让 subR 上升到 parent 原来的位置 subR-_left parent; subR-_parent ppNode; // 6. parent 下沉成为 subR 的左孩子 parent-_parent subR; // 7. 根据 parent 原来是否是根节点重新连接整棵树 if (ppNode nullptr) { _root subR; } else { if (ppNode-_left parent) { ppNode-_left subR; } else { ppNode-_right subR; } } } void _RotateR(Node* parent) { // 1. 保存左孩子和左孩子的右子树 Node* subL parent-_left; Node* subLR subL-_right; // 2. 让 parent 接住 subLR parent-_left subLR; // 3. 如果 subLR 存在要更新它的父节点 if (subLR ! nullptr) { subLR-_parent parent; } // 4. 保存 parent 原来的父节点 Node* ppNode parent-_parent; // 5. 让 subL 上升到 parent 原来的位置 subL-_right parent; subL-_parent ppNode; // 6. parent 下沉成为 subL 的右孩子 parent-_parent subL; // 7. 根据 parent 原来是否是根节点重新连接整棵树 if (ppNode nullptr) { _root subL; } else { if (ppNode-_left parent) { ppNode-_left subL; } else { ppNode-_right subL; } } } void _RotateLR(Node* parent) { // 1. 记录左孩子和左孩子的右孩子 Node* subL parent-_left; Node* subLR subL-_right; // 2. 保存中间节点旋转前的平衡因子 int bf subLR-_bf; // 3. 先对左孩子做左单旋 _RotateL(subL); // 4. 再对当前节点做右单旋 _RotateR(parent); // 5. 双旋后中间节点成为新的子树根它的平衡因子一定恢复为 0 subLR-_bf 0; // 6. 根据中间节点旋转前的平衡因子修正另外两个节点 if (bf -1) { parent-_bf 1; subL-_bf 0; } else if (bf 1) { parent-_bf 0; subL-_bf -1; } else { parent-_bf 0; subL-_bf 0; } } void _RotateRL(Node* parent) { // 1. 记录右孩子和右孩子的左孩子 Node* subR parent-_right; Node* subRL subR-_left; // 2. 保存中间节点旋转前的平衡因子 int bf subRL-_bf; // 3. 先对右孩子做右单旋 _RotateR(subR); // 4. 再对当前节点做左单旋 _RotateL(parent); // 5. 双旋后中间节点成为新的子树根它的平衡因子一定恢复为 0 subRL-_bf 0; // 6. 根据中间节点旋转前的平衡因子修正另外两个节点 if (bf -1) { parent-_bf 0; subR-_bf 1; } else if (bf 1) { parent-_bf -1; subR-_bf 0; } else { parent-_bf 0; subR-_bf 0; } } void _Destroy(Node* root) { //这个函数用后序遍历释放整棵树 //为什么要后序释放 //因为必须先释放左子树和右子树最后再释放当前节点否则当前节点一删就找不到下面的孩子了 // 如果当前节点为空直接返回 if (root nullptr) { return; } // 先释放左子树 _Destroy(root-_left); // 再释放右子树 _Destroy(root-_right); // 最后释放当前节点 delete root; } void _InOrder(Node* root) const { //验证这棵树是否仍然保持二叉搜索树的有序性 // 当前节点为空说明递归到底直接返回 if (root nullptr) { return; } // 先遍历左子树 _InOrder(root-_left); // 再访问当前节点 std::cout root-_data ; // 最后遍历右子树 _InOrder(root-_right); } int _Height(Node* root) const { /* 这个函数用于计算以某个节点为根的子树高度 它主要用于调试和校验不参与插入时的平衡维护 插入维护靠的是 _bf不是每次都现算高度 */ // 空树高度为 0 if (root nullptr) { return 0; } // 分别递归计算左右子树高度 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); // 返回较大者加 1 return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; } bool _IsBalanceTree(Node* root) const { // 空树也是 AVL 树 if (root nullptr) { return true; } // 计算左右子树高度 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); // 本实现中的平衡因子定义为右高 - 左高 int diff rightHeight - leftHeight; // 如果现算的平衡因子和记录值不一致或者绝对值超过 1则不是 AVL 树 if (diff ! root-_bf || diff -1 || diff 1) { return false; } // 继续递归检查左右子树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } private: Node* _root; }; int main() { AVLTreeint t1; t1.Insert(30); t1.Insert(20); t1.Insert(10); std::cout LL: std::endl; t1.InOrder(); std::cout t1.IsBalanceTree() std::endl; // 1 AVLTreeint t2; t2.Insert(10); t2.Insert(20); t2.Insert(30); std::cout RR: std::endl; t2.InOrder(); std::cout t2.IsBalanceTree() std::endl; // 1 AVLTreeint t3; t3.Insert(30); t3.Insert(10); t3.Insert(20); std::cout LR: std::endl; t3.InOrder(); std::cout t3.IsBalanceTree() std::endl; // 1 AVLTreeint t4; t4.Insert(10); t4.Insert(30); t4.Insert(20); std::cout RL: std::endl; t4.InOrder(); std::cout t4.IsBalanceTree() std::endl; // 1 AVLTreeint t5; int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (int x : arr) { t5.Insert(x); } std::cout 综合测试: std::endl; t5.InOrder(); std::cout t5.Height() std::endl; // 4 std::cout t5.IsBalanceTree() std::endl; // 1 std::cout t5.Insert(15) std::endl; // 0 return 0; }