做网站泉州,wordpress 男科医院主题,永久免费的网站服务器有哪些平台,温州网络学堂目录
1.概念
2.实现
2.1 初始化
2.2 插入
2.2.1 旋转#xff08;重点#xff09;
左单旋
右单旋
双旋
2.❗ 双旋后#xff0c;对平衡因子的处理
2.3 判断测试
完整代码#xff1a;
拓展#xff1a;删除 1.概念
二叉搜索树虽可以缩短查找的效率#xff0c;但…目录
1.概念
2.实现
2.1 初始化
2.2 插入
2.2.1 旋转重点
左单旋
右单旋
双旋
2.❗ 双旋后对平衡因子的处理
2.3 判断测试
完整代码
拓展删除 1.概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。
因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
高度之差右子树高度 - 左子树高度 AVL 高度平衡二叉树搜索树
由于AVL树的自平衡特性它适用于需要频繁插入和删除操作的场景尤其是对于需要快速搜索和有序遍历的数据集合。 平衡为什么不是高度差相等而是高度差不超过 1 为了涵盖更多的情况例如为节点个数为 4 如下高度差 1 也相对平衡了 为什么 满二叉树和 AVL 树是同一个 level 增删查改高度次-OlogN
最后一 h 层有 2^(h-1)个节点 满二叉树 2^h-1N AVL 树 2^h-XN //最后一行还存在缺失 X 范围[1, 2^(h-1)-1] 满二叉树和 AVL 树 在量级上都是约等于 log N 的
2.实现
2.1 初始化
AVL树的节点定义包括以下几个属性
值每个节点存储的值可以是任意类型通常是一个关键字或数据。左子节点指针指向当前节点的左子节点的指针。左子节点的值应该小于或等于当前节点的值。右子节点指针指向当前节点的右子节点的指针。右子节点的值应该大于当前节点的值。父节点指针指向当前节点的父节点的指针。根节点的父节点指针为空。为了便于后面更好的更新设计的平衡因子表示当前节点的左子树高度和右子树高度之差。平衡因子可以为-1、0或1。
下面是一个示例代码来定义一个AVL树的节点结构
templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0) //balance factor{}
};
2.2 插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, 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现在插入导致严重不平衡违反规则就地处理—旋转。 什么时候结束呢 _bf0 或者更新到了根节点的时候
实现平衡因子的更新
// ... 控制平衡// 更新平衡因子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-rightcur-left;
cur-leftparent;
如下情况都会用到左旋 代码
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.h0 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的左子节点AsubL和节点A的右子节点DsubLR然后对节点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()
{AVLTreeint, 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
#includeiostream
#includeassert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, 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 factorwhile (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 pairT, 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;elseparent-_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);elseRotateR(parent);}else{if (sign 1)RotateRL(parent);elseRotateLR(parent);}cur parent;parent cur-_parent;}else{assert(false);}}return true;
}
这一部分用于在删除节点后更新平衡因子并处理旋转以保持树的平衡
平衡因子为 ±1子树高度没有变化直接返回。平衡因子为 0子树高度减少继续向上更新平衡因子。平衡因子为 ±2子树严重不平衡需要旋转。根据较高子树的平衡因子选择合适的旋转方式 如果较高子树的平衡因子为 0进行单旋转。如果较高子树的平衡因子与父节点相同进行单旋转。如果较高子树的平衡因子与父节点不同进行双旋转。
通过这些操作就可以确保树在删除节点后仍然保持平衡啦
