目录1.二叉搜索树1.二叉搜索树的基本结构2.节点的插入与删除2.平衡搜索二叉树3.AVL树1.AVL树的节点插入1.平衡因子的更新1.更新后节点的平衡因子变为02.更新后节点的平衡因子变为-1/1和-2/2a.更新后节点的平衡因子变为-1/1b.更新后节点的平衡因子为-2/22.旋转1.右单旋​2.左右双旋2.AVL树平衡检测在学习数据结构时想必大家对二叉搜索树已经不陌生了二叉搜索树也是C中非常重要的数据结构。在数据存储、堆排序等场景中不可或缺但是二叉搜索树有个巨大的缺陷——在极端情况下二叉搜索树退化为单支树或者类似单支这使得二叉搜索树的搜索性能从O(log n)退化为O(n)。这时就体现了平衡搜索二叉树AVL树的作用了当这棵二叉树趋于这种不平衡的状态时树就会通过旋转等操作让这棵二叉树重新趋于平衡变成完全二叉树或者接近完全二叉树。这篇博客就带着大家来认识平衡搜索二叉树。1.二叉搜索树我们先来简单复习一下二叉搜索树1.若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值2.若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值3.它的左右子树也分别为二叉搜索树1.二叉搜索树的基本结构templateclass T struct TreeNode { TreeNode(const T data) :_data(data) ,_left(nullptr) ,_right(nullptr) {} TreeNode* _left; TreeNode* _right; T _data; }; templateclass T class Tree { using Node TreeNodeT; private: Node* _root nullptr; };2.节点的插入与删除插入节点就定义一个cur节点从根开始遍历cur节点存储的值的大小与要插入值比较大的往左走小的往右走反过来也行看个人需求当然要定义一个parent节点存储它的父节点来进行链接操作删除节点就找一个存储数据大小相近的节点来进行替换后进行链接就行了当然里面有很多细节空节点的判定等要注意特殊处理这些二叉搜索树基础操作不过多详解在此简单点一下代码奉上bool Insert(const T data) { if (_root nullptr) { _root new Node(data); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_data data) { parent cur; cur cur-_left; } else if (cur-_data data) { parent cur; cur cur-_right; } else { return false; } } cur new Node(data); if (parent-_data data) { parent-_left cur; } else { parent-_right cur; } return true; } bool Erase(const T data) { Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_data data) { parent cur; cur cur-_left; } else if (cur-_data data) { parent cur; cur cur-_right; } else { if (cur-_left nullptr) { if (parent nullptr) { _root cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; return true; } else if (cur-_right nullptr) { if (parent nullptr) { _root cur-_left; } else { if (parent-_left cur) parent-_left cur-_left; else parent-_right cur-_left; } delete cur; return true; } else // 两边节点都不为空找可代替节点(左子树的最左节点或右子树的最最右节点) { Node* right_min_parent cur; Node* right_min cur-_right; while (right_min-_left) { right_min_parent right_min; right_min right_min-_left; } cur-_data right_min-_data; if (right_min_parent-_left right_min) // 节点数据替换后别忘了链接被代替节点的兄弟节点 { right_min_parent-_left right_min-_right; } else { right_min_parent-_right right_min-_right; } delete right_min; return true; } return true; } } return false; }2.平衡搜索二叉树平衡二叉搜索树是一种特殊的二叉搜索树它除了满足二叉搜索树的基本特点之外本身还存在特定规则这些规则可以保证二叉树的搜索性能保持在O(log n)量级不会出现极端的单支树等类似树状结构将搜索性能降低。比较常见的平衡二叉搜索树有AVL树、红黑树等我们这篇博客就来深度解析一下AVL树的运行逻辑3.AVL树AVL树除了满足二叉搜索树的基本特点之外它还有它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1的规律。为了满足这个规则我们在每个节点处增加一个平衡因子这个平衡因子用于储存它左右子树的高度差_bf 右子树的高度 - 左子树的高度即我们只需要让每个节点的平衡因子的值维持在1/-1/0之中即可为了方便链接我们再加一个parent节点储存父节点。1.AVL树的节点插入当我们新增了平衡因子后在每次插入节点后都需要进行检查、维护所以AVL树插入过程就很明了了1.按二叉搜索树的规则插入节点2.更新平衡因子那么现在就来分析一下平衡因子的更新规律1.平衡因子的更新我们这里就定义右子树的高度 - 左子树的高度为平衡因子的值那么我们只需要判断插入节点是父节点的左子树还是右子树来对parent节点的平衡因子进行-- 或 接着再对parent节点更新后的平衡因子的值来进行分析来判断是否继续向上更新1.更新后节点的平衡因子变为0我们要更新平衡因子就要先知道平衡因子更新到什么时候就可以停下来了——当我们更新到的节点的平衡因子变为0时就能停了节点的平衡因子变为0那么之前的值为-1或1在插入节点之前的以这个节点为根的这棵树它子树一边高一边低那么在插入结点之后这棵树变平衡了它的高度是不变的因此他的父节点的平衡因子也是不用变的2.更新后节点的平衡因子变为-1/1和-2/2为什么没有其他情况就只有这两种情况如果有其他情况的话比如3/-3,那么就说明在更新前他的平衡因子为-2/2或-4/4那么在更新前就已经不是AVL树了那这棵树就出问题了其余情况同理a.更新后节点的平衡因子变为-1/1根据上面的推理我们不难知道更新前平衡因子必定为0那么以这个节点为根的树就由平衡变得不平衡它的高度就增加了那么就要继续往上更新b.更新后节点的平衡因子为-2/2这时树就变得不是AVL树了那么这时候就要进行旋转让它重新变为AVL树2.旋转我们把旋转分为4种情况左单旋/右单旋/左右双旋/右左双旋1.右单旋以上图为例当在a里插入了一个节点后parent节点的平衡因子变为了-2cur节点为-1也就是该树变为了纯粹的左边高。这时候就要让parent节点以cur节点为轴心向右旋转旋转的核心步骤就是让parent变为cur的右子树而cur原来的右子树变为parent的左子树parent再对祖先节点与cur节点进行链接即可在最后将parent和cur的平衡因子置为0右旋的步骤就完成了右单旋代码奉上void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (pParent) { if (pParent-_left parent) pParent-_left subL; else pParent-_right subL; subL-_parent pParent; } else { _root subL; subL-_parent nullptr; } parent-_bf subL-_bf 0; }2.左右双旋如果该树不是纯粹的左边高或右边高那么进行右单旋还会平衡吗可以看到旋转后仍不平衡那么我们可以想办法让这棵树变为纯粹的单边高再来进行旋转那么该怎么做呢那么这时候我们可以先让cur节点左旋一次让这棵树变为纯粹的左边高再让parent右旋一次实现平衡那么其他情形呢如图这个适用于所有的类型但是有些眼睛好的亦菲彦祖们就发现了再上上张图中进行左右双旋的话它的parentsubL及subLR节点的平衡因子在旋转后都变为了0而在上图中subL的平衡因子居然变成了-1那么这就是双旋后对平衡因子的更改的重点1.当新增节点再subLR的左子树时subLR-_bf 1e树高度就为hf树就为h-1旋转链接后不难发现subL变平衡树了而parent变得不平衡了2.当新增节点再subLR的左子树时subLR-_bf -1如上图3.而新增节点就为subLR时subLR-_bf 0它在旋转后该树变为了满二叉树对此可以以subLR的平衡因子的值为根据来进行判断右左双旋同理左右双旋代码奉上void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); if (bf 0) { subL-_bf 0; subLR-_bf 0; parent-_bf 0; } else if (bf -1) { subL-_bf 0; subLR-_bf 0; parent-_bf 1; } else if (bf 1) { subL-_bf -1; subLR-_bf 0; parent-_bf 0; } else assert(false); }2.AVL树平衡检测当我们理解了上述要点就能自己尝试实现AVL树了那我们该如何验证自己写的是正确的呢要验证我们实现的树是正确的无非是检查他是否遵循AVL树的规则1.左右子树高度差不超过12.每个节点的平衡因子的值是准确的也就是我们只要验证上述两点即可我们可以写一个获取二叉树高度的代码让它左右子树的高度相减判断结果是否大于1再递归去遍历每个节点同时判断平衡因子的正确性H左 - H右 2代码奉上int _Height(Node* root) { if (root nullptr) { return 0; } return max(1 _Height(root-_left), 1 _Height(root-_right)); } bool _IsBalanceTree(Node* root) { if (nullptr root) { return true; } int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout root-_data 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_data 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }AVL树的删除也可以自己去试着实现哦以上就是本期博客的所有内容感谢阅读希望能够帮到你也欢迎大家指错及补充