阅读量:0
目录
1.概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
高度之差=右子树高度 - 左子树高度
AVL == 高度平衡二叉树搜索树
由于AVL树的自平衡特性，它适用于需要频繁插入和删除操作的场景，尤其是对于需要快速搜索和有序遍历的数据集合。
平衡为什么不是高度差相等，而是高度差不超过 1？
为了涵盖更多的情况，例如为节点个数为 4 如下，高度差 1 也相对平衡了
为什么 满二叉树和 AVL 树是同一个 level？
增删查改：高度次->O（logN）
最后一 h 层有 2^(h-1)个节点
满二叉树 2^h-1=N
AVL 树 2^h-X=N //最后一行还存在缺失
X 范围：[1, 2^(h-1)-1]
满二叉树和 AVL 树 在量级上都是约等于 log N 的
2.实现
2.1 初始化
AVL树的节点定义包括以下几个属性：
- 值：每个节点存储的值，可以是任意类型，通常是一个关键字或数据。
- 左子节点指针：指向当前节点的左子节点的指针。左子节点的值应该小于或等于当前节点的值。
- 右子节点指针：指向当前节点的右子节点的指针。右子节点的值应该大于当前节点的值。
- 父节点指针：指向当前节点的父节点的指针。根节点的父节点指针为空。（为了便于后面更好的更新设计的）
- 平衡因子：表示当前节点的左子树高度和右子树高度之差。平衡因子可以为-1、0或1。
下面是一个示例代码来定义一个AVL树的节点结构：
template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; AVLTreeNode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) //balance factor {} };2.2 插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) {// if (_root == nullptr) { _root = new Node(kv); return true; } //搜索找到位置 Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right;//小于就右移 } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } }//找到一个为空的位置了生成支点，判断插入
cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent;//再指回去插入这部分代码倒是没问题，难的是新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树，破坏了AVL树就需要旋转调整再次变成AVL树。
如何根据这三种情况来实现插入和对高度的管理？
新增支点：右子树高度++，左子树高度--
插入会对祖先产生影响，平衡因子为 0 了，就再不会对上面的祖先产生影响了，变 0 就平衡了
对以上插入情况，分析可知
是否继续向上更新依旧：子树的高度是否变化
- parent->_bf == 0，说明之前parent->_bf是1或者-1，说明之前parent一边高一边低，而这次的插入是把矮的那边填上了，parent所在子树高度不变，不需要往上继续更新。
- parent->_bf == 1 或者 -1，说明之前parent->_bf为0，两边一样高，现在插入使一边变得更高了，parent所在子树高度变了，继续往上更新。
- parent->_bf == 2 或者 -2，说明之前parent->_bf是1或者-1，现在插入导致严重不平衡，违反规则，就地处理—>旋转。
什么时候结束呢？
_bf==0 或者更新到了根节点的时候
实现平衡因子的更新
// ... 控制平衡 // 更新平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; } else // if (cur == parent->_right) { parent->_bf++; } //判断处理 if (parent->_bf == 0) { // 更新结束 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 继续往上更新 cur = parent; parent = parent->_parent; //回指父指针作用的体现，实现上移了 } else if (parent->_bf == 2 || parent->_bf == -2) { // 子树不平衡了，需要旋转 if (parent->_bf == 2 || cur->bf == 1) { RotateL(parent); } break; } else { assert(false); } } return true; }接下来我们来看看旋转的实现
2.2.1 旋转（重点）
左单旋
[C++] 详解AVL树左旋的实现~
旋转的时候需要注意的问题：
- 保持他是搜索树
- 变成平衡树且降低这个子树的高度
核心操作：
parent->right=cur->left; cur->left=parent;如下情况都会用到左旋：
代码：
void RotateL(Node* parent) { // 保存父节点的右子节点 Node* cur = parent->_right; // 保存右子节点的左子节点 Node* curleft = cur->_left; // 利用区间性，将子左给父右 parent->_right = curleft; if (curleft) { // 将右子节点的左子节点作为父节点的右子节点 curleft->_parent = parent; } // 将父节点作为右子节点的左子节点 cur->_left = parent; // 保存父节点的父节点 Node* ppnode = parent->_parent; // 将父节点的父节点指向右子节点 parent->_parent = cur; // 判断原父节点是否为根节点 if (parent == _root) { // 更新根节点为右子节点 _root = cur; // 将新根节点的父指针置为空 cur->_parent = nullptr; } else { // 判断原父节点是其父节点的左子节点还是右子节点 if (ppnode->_left == parent) { // 更新父节点的左子节点为右子节点 ppnode->_left = cur; } else { // 更新父节点的右子节点为右子节点 ppnode->_right = cur; } // 更新右子节点的父指针为父节点的父节点 cur->_parent = ppnode; } // 将父节点和右子节点的平衡因子都设置为0，表示树已经平衡 parent->_bf = cur->_bf = 0; }右单旋
代码：
void RotateR(Node* parent) { // 获取父节点的左子节点 Node* cur = parent->_left; // 获取左子节点的右子节点 Node* curright = cur->_right; // 将左子节点的右子节点作为父节点的左子节点 parent->_left = curright; if (curright) { // 更新左子节点的右子节点的父指针 curright->_parent = parent; } // 引入父父节点 Node* ppnode = parent->_parent; // 将父节点作为左子节点的右子节点 cur->_right = parent; // 更新父节点的父指针 parent->_parent = cur; // 判断原父节点是否为根节点 if (ppnode == nullptr) { // 更新根节点为左子节点 _root = cur; // 将新根节点的父指针置为空 cur->_parent = nullptr; } else { // 判断原父节点是其父节点的左子节点还是右子节点 if (ppnode->_left == parent) { // 更新父节点的左子节点为左子节点 ppnode->_left = cur; } else { // 更新父节点的右子节点为左子节点 ppnode->_right = cur; } // 更新左子节点的父指针 cur->_parent = ppnode; } // 将父节点和左子节点的平衡因子都设置为0，表示树已经平衡 parent->_bf = cur->_bf = 0; }双旋
左右旋转：插入的两种情况，看的是折线情况
直线：单旋 2 1 同号
折线：双旋 2 -1
旋转判断
根据 parent 和 cur 的平衡因子，实现对使用哪种旋转的判断
else if (parent->_bf == 2 || parent->_bf == -2) { // 子树不平衡了，需要旋转 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //异号 else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } break; } else { assert(false); } }1.
双旋的结果本质：比 60 小 ，比 30 大的小插入 到 30 下面，找到一个区间中的点
2.❗ 双旋后，对平衡因子的处理
3.h==0 60 本身就是插入的
三种情况，关心 60 的值是-1 0 1
不存在其他奇怪的情况，分别做了 60 的左右
以 RL 为例实现代码：
void RotateRL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; int bf = curleft->_bf; RotateR(parent->_right); RotateL(parent); //举例思考填写 if (bf == 0) { cur->_bf = 0; curleft->_bf = 0; parent->_bf = 0; } else if (bf == 1) { cur->_bf = 0; curleft->_bf = 0; parent->_bf = -1; } else if (bf == -1) { cur->_bf = 1; curleft->_bf = 0; parent->_bf = 0; } else { assert(false); } }LR 旋转：
平衡因子是根据 curright 初始情况，经过旋转后的图分析分类后得带的
⭕具体而言，先左单旋再右单旋的操作步骤如下：
- 首先获取节点C的左子节点A（subL）和节点A的右子节点D（subLR）；
- 然后对节点A进行左单旋（RotateL），此时节点C的左子节点应为节点D，节点D的右子节点应为节点A；
- 最后对节点C进行右单旋（RotateR），此时节点D成为新的子树头节点，节点C成为节点D的右子节点。
最后一部分使用了if语句判断旋转后各个节点的平衡因子，并进行相应的调整，以便使AVL树保持平衡。
- 如果节点D的平衡因子为1，说明节点D的左子树比右子树高，需要进行右旋操作，这一次旋转中节点C和节点A都向右移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为-1；
- 如果节点D的平衡因子为-1，说明节点D的右子树比左子树高，需要进行左旋操作，这一次旋转中节点C和节点A都向左移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为1；
- 如果节点D的平衡因子为0，说明节点D的左右子树高度相等，不需要进行旋转操作，各个节点的平衡因子均设置为0；
- 如果节点D的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。
- 经过这两次旋转后，AVL树重新保持了平衡性和有序性。
void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; int bf = curright->_bf; RotateL(parent->_left); RotateR(parent); //解耦合，旋转bf 重新定义 if (bf == 0) { parent->_bf = 0; cur->_bf = 0; curright->_bf = 0; } else if (bf == -1) { parent->_bf = 1; cur->_bf = 0; curright->_bf = 0; } else if (bf == 1) { parent->_bf = 0; cur->_bf = -1; curright->_bf = 0; } }2.3 判断测试
test 发现不是根，父亲又是空，是为什么呢？
树的结构出问题了，某次旋转出事了
发现错误就是我们的晋级关键时刻
我们可以根据AVL树的性质来测试
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 即左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
求高度这有个对重载函数的巧妙使用:
当传入的节点
root是nullptr（空指针）时，说明到达了树的叶子节点的下一层，此时返回高度为0，因为空树的高度定义为0。
int Height() { return Height(_root); } int Height(Node* root) { if (root == nullptr) return 0; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }对于平衡的测试：
IsBalance(Node* root) 是一个递归函数，其工作流程如下：
- 基本情况：如果
root是nullptr，意味着到达了一个空节点，那么认为该子树是平衡的，返回true。- 计算子树高度：计算当前节点的左子树和右子树的高度，分别存储在
leftHight和rightHight变量中。- 检查平衡因子：
root->_bf表示当前节点的平衡因子，即右子树的高度减去左子树的高度。如果计算出的实际高度差与存储的平衡因子不匹配，那么输出错误信息并返回false。这一步是为了验证树的内部数据一致性。- 检查子树平衡性：检查当前节点的左右子树高度差的绝对值是否小于2（即是否平衡）。如果是，则继续递归检查左右子树是否平衡。如果所有的子树都平衡，那么整个树也是平衡的。
bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) return true; int leftHight = Height(root->_left); int rightHight = Height(root->_right); if (rightHight - leftHight != root->_bf) { cout << "平衡因子异常:" <<root->_kv.first<<"->"<< root->_bf << endl; return false; } return abs(rightHight - leftHight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); } private: Node* _root = nullptr; public: int _rotateCount = 0; };手动制作条件断点，一定要注意父亲回指的设定
// 更新父节点的父指针 parent->_parent = cur;对于这个纰漏的处理，来检验和调试这个问题
测试：
int main() { AVLTree<int, int> tree; // 插入一些节点 tree.Insert({10, 10}); tree.Insert({20, 20}); tree.Insert({30, 30}); tree.Insert({40, 40}); tree.Insert({50, 50}); cout << "树高度: " << tree.Height() << endl; cout << "树是否平衡: " << (tree.IsBalance() ? "是" : "否") << endl; // 插入更多节点来触发旋转 tree.Insert({25, 25}); tree.Insert({5, 5}); tree.Insert({15, 15}); cout << "树高度: " << tree.Height() << endl; cout << "树是否平衡: " << (tree.IsBalance() ? "是" : "否") << endl; return 0; }
发现错误：
拼写错误修正：例如 rotateCount 应为 _rotateCount。parent 不要拼写掉 e。
目前还不知道是为什么，重写了一遍，就跑起来了
完整代码：
#pragma once #include<iostream> #include<assert.h> using namespace std; template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // Update balance factor while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) break; else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { if (parent->_bf == 2 && cur->_bf == 1) RotateL(parent); else if (parent->_bf == -2 && cur->_bf == -1) RotateR(parent); else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent); break; } else { assert(false); } } return true; } void RotateL(Node* parent) { ++_rotateCount; Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft; if (curleft) { curleft->_parent = parent; } cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } parent->_bf = cur->_bf = 0; } void RotateR(Node* parent) { ++_rotateCount; Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright; if (curright) curright->_parent = parent; cur->_right = parent; Node* ppnode = parent->_parent; parent->_parent = cur; if (ppnode == nullptr) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } parent->_bf = cur->_bf = 0; } void RotateRL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; int bf = curleft->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { cur->_bf = 0; curleft->_bf = 0; parent->_bf = 0; } else if (bf == 1) { cur->_bf = 0; curleft->_bf = 0; parent->_bf = -1; } else if (bf == -1) { cur->_bf = 1; curleft->_bf = 0; parent->_bf = 0; } else { assert(false); } } void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; int bf = curright->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) { parent->_bf = 0; cur->_bf = 0; curright->_bf = 0; } else if (bf == -1) { parent->_bf = 1; cur->_bf = 0; curright->_bf = 0; } else if (bf == 1) { parent->_bf = 0; cur->_bf = -1; curright->_bf = 0; } else { assert(false); } } int Height() { return Height(_root); } int Height(Node* root) { if (root == nullptr) return 0; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); return max(leftHeight, rightHeight) + 1; } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl; return false; } return abs(rightHeight - leftHeight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); } private: Node* _root = nullptr; public: int _rotateCount = 0; };拓展：删除
插入到 0，不用更改
删除到 0，还要更改
删除会更加的复杂，平衡因子的更新，旋转等等，将上面的思路总结和拓展一下，大家有兴趣可以看看如下的实现代码：
bool Erase(const pair<T, V>& kv) { if (_root == nullptr) return false;首先，检查树是否为空。如果树为空，直接返回 false，表示删除失败。
Node* parent = nullptr; Node* cur = _root; // 找到要删除的节点 while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { break; } } if (cur == nullptr) return false;这部分代码用于在树中查找要删除的节点。通过比较当前节点 cur 的键值 cur->_kv.first 与要删除的键值 kv.first，决定向左子树还是右子树继续搜索。最终，cur 将指向要删除的节点，parent 是 cur 的父节点。如果找不到该键值，返回 false。
// 处理删除节点的三种情况 if (cur->_left == nullptr) { if (parent == nullptr) { _root = cur->_right; if (_root) _root->_parent = nullptr; } else { if (cur == parent->_left) { parent->_left = cur->_right; parent->_bf++; } else { parent->_right = cur->_right; parent->_bf--; } if (cur->_right) cur->_right->_parent = parent; } } else if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; if (_root) _root->_parent = nullptr; } else { if (cur == parent->_left) { parent->_left = cur->_left; parent->_bf++; } else { parent->_right = cur->_left; parent->_bf--; } if (cur->_left) cur->_left->_parent = parent; } } else // 左右子树都不为空 { Node* successorParent = cur; Node* successor = cur->_right; while (successor->_left) { successorParent = successor; successor = successor->_left; } cur->_kv = successor->_kv; if (successorParent->_left == successor) { successorParent->_left = successor->_right; successorParent->_bf++; } else { successorParent->_right = successor->_right; successorParent->_bf--; } if (successor->_right) successor->_right->_parent = successorParent; cur = successor; parent = successorParent; } delete cur;这一部分处理删除节点的三种情况：
- 左子树为空：直接用右子树替代删除节点。如果删除节点是根节点，直接更新根节点
_root。否则，更新父节点的左或右子树指针，并调整平衡因子。 - 右子树为空：直接用左子树替代删除节点。如果删除节点是根节点，直接更新根节点
_root。否则，更新父节点的左或右子树指针，并调整平衡因子。 - 左右子树都不为空：找到右子树中的最小节点（即中序后继节点），用这个节点替代当前节点。然后删除中序后继节点，并调整其父节点的指针和平衡因子。
// 更新平衡因子并处理旋转 bool isLRUpdated = true; while (parent) { if (!isLRUpdated) { if (cur == parent->_left) parent->_bf++; else parent->_bf--; } isLRUpdated = false; if (parent->_bf == 1 || parent->_bf == -1) return true; else if (parent->_bf == 0) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { Node* higherChild; int sign; if (parent->_bf > 0) { sign = 1; higherChild = parent->_right; } else { sign = -1; higherChild = parent->_left; } if (higherChild->_bf == 0) { if (sign > 0) { RotateL(parent); parent->_bf = 1; higherChild->_bf = -1; } else { RotateR(parent); parent->_bf = -1; higherChild->_bf = 1; } return true; } else if (higherChild->_bf == sign) { if (sign == 1) RotateL(parent); else RotateR(parent); } else { if (sign == 1) RotateRL(parent); else RotateLR(parent); } cur = parent; parent = cur->_parent; } else { assert(false); } } return true; }这一部分用于在删除节点后更新平衡因子并处理旋转，以保持树的平衡：
- 平衡因子为 ±1：子树高度没有变化，直接返回。
- 平衡因子为 0：子树高度减少，继续向上更新平衡因子。
- 平衡因子为 ±2：子树严重不平衡，需要旋转。根据较高子树的平衡因子选择合适的旋转方式：
- 如果较高子树的平衡因子为 0，进行单旋转。
- 如果较高子树的平衡因子与父节点相同，进行单旋转。
- 如果较高子树的平衡因子与父节点不同，进行双旋转。
通过这些操作，就可以确保树在删除节点后仍然保持平衡啦
