徐州制作手机网站,建设网站的必要与可行性,html电子商务网站模板下载,深圳市网络营销推广平台目录
前言
一#xff0c;概念
二#xff0c;定义
三#xff0c;insert
1. 插入情况
情况一#xff1a;
情况二#xff1a;
情况三#xff1a;
2. 旋转方法
法一#xff1a;左单旋法
法二#xff1a;右单旋法
法三#xff1a;先左后右双旋法
法四#xf…
目录
前言
一概念
二定义
三insert
1. 插入情况
情况一
情况二
情况三
2. 旋转方法
法一左单旋法
法二右单旋法
法三先左后右双旋法
法四先右后左双旋法
测试判断一棵树是否是AVL树
代码如下
3. 随机值案例
四删除 前言
map,set这两个容器有个共同点是 其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 搜索二叉树请查看本篇博文【C】搜索二叉树底层实现_花果山~程序猿的博客-CSDN博客 一概念
二叉搜索树虽可以缩短查找的效率但 如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 1. 它的左右子树都是AVL树 2. 左右子树高度之差(简称平衡因子)的绝对值不超过 1 (-1/0/1) AVL树不一定用平衡因子进行实现 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O(log_2 n)搜索时间复杂度O(log_2 n)。 二定义 为方便循序渐进的学习这里只放最出初始的树结点定义。 template class K, class V
class AVL_Data
{
public:pairK, V _kv;AVL_DataK, V* left nullptr;AVL_DataK, V* right nullptr;AVL_DataK, V* parent nullptr;int _bf 0; // ballance factorAVL_Data(const pairK, V p):_kv(p){}};上面定义在后面会进行完善修改。 三insert
根据前面搜索二叉树的经验我们能快速写完插入函数但AVL树是特殊的搜索二叉树我们需要对树的高度进行调整。那么我们插入时就会遇到三种情况 1. 插入情况
情况一 情况二 情况三 代码实现如下
template class K, class V
class AVL_Tree
{typedef AVL_DataK, V AVL_Data;AVL_Data* root nullptr;public:bool insert(const pairK, V p){AVL_Data* new_a_d new AVL_Data(p);if (!root){root new_a_d;}else{AVL_Data* cur root;AVL_Data* parent nullptr;while (cur){if (p.first cur-_kv.first){parent cur;cur cur-left;}else if (p.first cur-_kv.first){parent cur;cur cur-right;}else{delete(new_a_d); // 插入失败删除新建结点return false;}}if (p.first parent-_kv.first){parent-left new_a_d;}else{parent-right new_a_d;}new_a_d-parent parent;cur new_a_d;//完成插入进行平衡while (parent){ // 插入修改parent平衡因子if (cur parent-right){parent-_bf;}else{parent-_bf--;}// 判断parent平衡因子是否是0如果非0则需要向祖先更新平衡因子if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-parent;}else if (parent-_bf 0){break;}else if(parent-_bf 2 || parent-_bf -2){ // 处理绝对值大于1,下面代码目的是记录未修改的平衡因子。// 需要旋转处理这个我们下面再讲cur parent;parent parent-parent;}else{// 出现其他情况在插入时这棵AVL树本身就是异常AVL树assert(false);}}return true;}}
}; 2. 旋转方法
法一左单旋法
我们以下面图为讲解例子a,b,c表示的是子树。
h 表示子树的高度。 请看下面场景: h 3, 4...组合方式会更多这里画出图没什么意义问题是失去平衡我们如何解决
通过下面方法解决 总结
1. 右边高则向左旋转。
2. C树发生插入平衡因子发生改变进而发生旋转。 void RotateL(AVL_Data* parent){assert(parent-right);AVL_Data* par parent;AVL_Data* par_R par-right;AVL_Data* par_RL par-right-left;AVL_Data* ppnode par-parent;par-right par_RL;if (par_RL)par_RL-parent par;par_R-left par;par-parent par_R;par_R-parent ppnode;if (!ppnode){root par_R;}else if (ppnode-left par){ppnode-left par_R;}else{ppnode-right par_R;}par-_bf 0;par_R-_bf 0;}// 实验例子AVL_Treeint, string tree;tree.insert(make_pair(30 , 李四));tree.insert(make_pair(20, 二麻子));tree.insert(make_pair(60, 张三));tree.insert(make_pair(45, 王五));tree.insert(make_pair(75, 王五));tree.insert(make_pair(65, 王五));法二右单旋法
思路跟左旋法差不多图像是相反这里就只给场景解法模板 h 0, 1, 2的发生场景 学会了法一自然会了法二
void RotateR(AVL_Data* parent){assert(parent-left);AVL_Data* par parent;AVL_Data* par_L par-left;AVL_Data* par_LR par-left-right;AVL_Data* ppnode par-parent;par-left par_LR;if (par_LR)par_LR-parent par;par_L-right par;par-parent par_L;par_L-parent ppnode;if (!ppnode){root par_L;}else if (ppnode-left par){ppnode-left par_L;}else{ppnode-right par_L;}par-_bf 0;par_L-_bf 0;} 法三先左后右双旋法
跟单旋一样我们首先展示当h 012时需要左右双旋处理的场景。 双旋法步骤变化流程如下 从结果来看就是将60这个位置推上去置于“根”。
代码如下
void RotateLR(AVL_Data* parent){assert(parent-left);AVL_Data* par parent;AVL_Data* par_L par-left;AVL_Data* par_LR par-left-right;AVL_Data* ppnode par-parent;int par_LR_bf par_LR-_bf;RotateL(par_L);RotateR(par);if (par_LR_bf -1){par-_bf 1;par_L-_bf 0;}else if (par_LR_bf 1){par-_bf 0;par_L-_bf -1;}else if (par_LR_bf 0){par-_bf 0;par_L-_bf 0;}else{assert(false);}par_LR-_bf 0;}// 测试案例
void Test_insert_L()
{AVL_Treeint, string tree;tree.insert(make_pair(90, 李四));tree.insert(make_pair(30, 二麻子));tree.insert(make_pair(100, 张三));tree.insert(make_pair(25, 王五));tree.insert(make_pair(60, 王五));tree.insert(make_pair(50, 王五));
} 法四先右后左双旋法
我们学会法三后照葫芦画瓢即可。 各场景 代码
void RotateRL(AVL_Data* parent){assert(parent-right);AVL_Data* par parent;AVL_Data* par_R par-right;AVL_Data* par_RL par-right-left;AVL_Data* ppnode par-parent;int par_RL_bf par_RL-_bf;RotateR(par_R);RotateL(par);if (par_RL_bf -1){par-_bf 0;par_R-_bf 1;}else if (par_RL_bf 1){par-_bf -1;par_R-_bf 0;}else if (par_RL_bf 0){par-_bf 0;par_R-_bf 0;}else{assert(false);}par_RL-_bf 0;}// 测试案例
void Test_insert_L()
{AVL_Treeint, string tree;tree.insert(make_pair(30, 李四));tree.insert(make_pair(20, 二麻子));tree.insert(make_pair(90, 张三));tree.insert(make_pair(15, 王五));tree.insert(make_pair(60, 王五));tree.insert(make_pair(100, 王五));tree.insert(make_pair(55, 王五));tree.insert(make_pair(67, 王五));tree.insert(make_pair(95, 王五));tree.insert(make_pair(50, 王五));
} 测试判断一棵树是否是AVL树
思路 1. 检查高度AVL中每棵子树都是AVL树。 2. 检查平衡因子是否正确。 代码如下
int Hight(const AVL_Data* root){if (root nullptr)return 0;int left_H Hight(root-left);int left_R Hight(root-right);return left_H left_R ? left_H 1 : left_R 1;}bool B_balance(){return _B_balance(root);}bool _B_balance(const AVL_Data* root){if (root nullptr)return true;int left_root Hight(root-left);int right_root Hight(root-right);if ((right_root - left_root) ! root-_bf) // 利用Hight进行平衡因子判断return false; return abs(left_root - right_root) 2 _B_balance(root-left) _B_balance(root-right);} 3. 随机值案例
用这个代码多跑几次差不多能遍历所有环境。
void Random_Test()
{srand(time(0));const size_t N 10000000;AVL_Treeint, int t;for (size_t i 0; i N; i){size_t x rand();t.insert(make_pair(x, x));}cout t.B_balance() endl;
}
快来测试自己的代码吧 insert全代码
bool insert(const pairK, V p){AVL_Data* new_a_d new AVL_Data(p);if (!root){root new_a_d;}else{AVL_Data* cur root;AVL_Data* parent nullptr;while (cur){if (p.first cur-_kv.first){parent cur;cur cur-left;}else if (p.first cur-_kv.first){parent cur;cur cur-right;}else{delete(new_a_d); // 插入失败删除新建结点return false;}}if (p.first parent-_kv.first){parent-left new_a_d;}else{parent-right new_a_d;}new_a_d-parent parent;cur new_a_d;//完成插入进行平衡while (parent){ // 插入修改parent平衡因子if (cur parent-right){parent-_bf;}else{parent-_bf--;}// 判断parent平衡因子是否是0如果非0则需要向祖先更新平衡因子if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-parent; }else if (parent-_bf 0){break;}else if (parent-_bf -2 || parent-_bf 2){if (parent-_bf 2 cur-_bf 1){RotateL(parent);// cout RotateL endl;}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);// cout RotateR endl;}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);// cout RotateLR endl;}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);// cout RotateRL endl;}else{// 出现其他情况在插入时这棵AVL树本身就是异常AVL树// 问题出现在旋转方法assert(false);}break;}else{assert(false);}}return true;}} 四删除 因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不 错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 具体实现学生们可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。 下期预告 红黑树 结语 本小节就到这里了感谢小伙伴的浏览如果有什么建议欢迎在评论区评论如果给小伙伴带来一些收获请留下你的小赞你的点赞和关注将会成为博主创作的动力。
