当前位置： 首页 > news >正文

AVL树详解

news 2026/6/15 20:26:07

目录

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树节点的定义：

template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} T _data; // 节点存储的数据 AVLTreeNode<T>* _left; // 左孩子 AVLTreeNode<T>* _right; // 右孩子 AVLTreeNode<T>* _parent; // 父节点 int _bf; // 平衡因子：右子树高度 - 左子树高度 };

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

Insert是 AVL 树中最核心的接口之一，它的任务不是单纯把数据插进去，而是要在插入完成后继续维护整棵树的平衡性

这个函数整体可以分成两大阶段

  1. 按照二叉搜索树的规则找到插入位置，并把新节点挂上去

  2. 从新节点的父节点开始，沿着父节点链一路向上更新平衡因子，如果发现某个祖先节点失衡，就立即旋转修复

第一阶段：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或LR

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; } // 如果值已经存在，这里不允许重复插入，直接返回 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，看右孩子pSubR

  • pSubR->_bf == 1，说明是RR，执行左单旋

  • pSubR->_bf == -1，说明是RL，执行右左双旋

  • pParent->_bf == -2，看左孩子pSubL

  • pSubL->_bf == -1，说明是LL，执行右单旋

  • pSubL->_bf == 1，说明是LR，执行左右双旋

  • 旋转完成后，以原pParent为根的子树已经平衡，不需要再向上更新

AVL树的验证

1. 验证其为二叉搜索树如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确

我们的平衡因子定义是右高 - 左高，所以差值必须写成 rightHeight - leftHeight

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);

关于AVL树的性能：

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即O(log n)。

但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。

AVL树总代码：

#include <iostream> template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} T _data; // 节点存储的数据 AVLTreeNode<T>* _left; // 左孩子 AVLTreeNode<T>* _right; // 右孩子 AVLTreeNode<T>* _parent; // 父节点 int _bf; // 平衡因子：右子树高度 - 左子树高度 }; template<class T> class AVLTree { using Node = AVLTreeNode<T>; 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() { AVLTree<int> t1; t1.Insert(30); t1.Insert(20); t1.Insert(10); std::cout << "LL:" << std::endl; t1.InOrder(); std::cout << t1.IsBalanceTree() << std::endl; // 1 AVLTree<int> t2; t2.Insert(10); t2.Insert(20); t2.Insert(30); std::cout << "RR:" << std::endl; t2.InOrder(); std::cout << t2.IsBalanceTree() << std::endl; // 1 AVLTree<int> t3; t3.Insert(30); t3.Insert(10); t3.Insert(20); std::cout << "LR:" << std::endl; t3.InOrder(); std::cout << t3.IsBalanceTree() << std::endl; // 1 AVLTree<int> t4; t4.Insert(10); t4.Insert(30); t4.Insert(20); std::cout << "RL:" << std::endl; t4.InOrder(); std::cout << t4.IsBalanceTree() << std::endl; // 1 AVLTree<int> 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; }
http://www.jsqmd.com/news/1018917/

相关文章：

  • Bert理论讲解
  • 题解：洛谷 P2709 【模板】莫队 / 小 B 的询问
  • 2026精选：福州代理记账十大排行榜本土企业 ——高性价之选 - 资讯速览
  • MPC866外部总线接口：突发传输、总线仲裁与内存保留机制详解
  • 敏感肌、学生党舒缓面膜怎么选？2026年修护面膜选购指南：温和维稳 晒后泛红全适配 - 17329971652
  • 4步终极指南：使用OpenCore Legacy Patcher让老旧Mac焕发新生
  • 2026年商标购买平台排名+选购指南：从合规备案到流程过户，哪个最靠谱？ - 信息热点
  • CRT-Royale-Reshade：在现代游戏中复活经典CRT显示器的视觉魔法
  • Mythos推理空间编织：下一代AI的动态知识建模与不确定性管理
  • 北海高口碑黄金铂金回收白银回收实体老店排行 5 家靠谱门店电话地址全收录
  • 口碑爆棚！长沙这些全屋定制风格，究竟藏着怎样的魅力？ - 资讯速览
  • B站视频数据分析神器：Bilivideoinfo完整使用指南
  • MySQL面经整理
  • Windows 10也能运行Android应用：WSA移植版完全指南
  • EASY-HWID-SPOOFER：Windows硬件信息伪装工具全面指南
  • 浏览器端EPUB电子书制作工具：零安装的专业创作体验
  • 哈尔滨各区名表回收测评，道里道外哪家出价更高 - 奢侈品回收测评
  • 中国电子学会图形化2021.6月Scratch四级考级题
  • 专业滤袋服务商哪家强？7维度实测 - 资讯速览
  • 抖音批量下载工具终极指南：从单视频到主页全量快速下载
  • 长沙专业全屋定制公司，为你打造理想家居空间！ - 资讯速览
  • VisualCppRedist AIO：Windows系统运行库一体化部署架构深度解析
  • Dell T440服务器硬盘灯狂闪黄灯？别慌，手把手教你排查RAID故障（附官方文档解读）
  • 苹果降价终极低价确认官宣！6月16日晚8点苹果全机型全系大降价！iPhone17跳水至4000+，国补+618优惠券，买手机时机不要错过 - 资讯报道
  • PXD10微控制器Flash模块低功耗模式与寄存器配置实战指南
  • 如何用浏览器快速制作专业电子书：EPubBuilder完整指南
  • 2026年别墅自建房商家推荐榜：正规品牌实力排名 - 资讯速览
  • 2026杭州添旺犬舍成犬行为矫正口碑排行榜：爆冲护食分离焦虑纠正.doc - 资讯报道
  • 台钓/海钓鱼竿怎么选？行情解析与优质厂家推荐 - 品牌推荐大师
  • STM32 I2C LCD 1602完整使用指南：从入门到实战应用