文章目录前言一、普通二叉搜索树的删除1. 删除结点的左右结点都不为空2. 删除结点的左结点为空右节点不为空3. 删除结点的右结点为空左节点不为空4. 删除结点的左右结点都不为空二、AVL树的删除1. 删除结点整棵树的高度不变化1.1 parent的平衡因子在删除结点之前为01.1.1 删除结点为parent的左节点1.1.2 删除结点为parent的右节点1.2 parent的平衡因子在调整过程中为21.2.1 删除结点为parent的左节点1.2.1.1 parent的右节点的平衡因子为01.2.1.2 parent的右节点的平衡因子为11.2.2 删除结点为parent的右节点1.2.2.1 parent的左节点的平衡因子为01.2.2.2parent的左节点的平衡因子为 -12. 删除结点整棵树的高度变化2.1 删除结点为parent的左节点2.1.1 parent的平衡因子在删除结点之前为 -12.1.2 parent的平衡因子为2且parent的右结点的平衡因子为-12.1.2.1 PRleft的平衡因子为12.1.2.2 PRleft的平衡因子为-12.2 删除结点为parent的右节点2.1.1 parent的平衡因子在删除结点之后为 02.1.2 parent的平衡因子为-2且parent的左节点的平衡因子为12.1.2.1 PLright的平衡因子为 12.1.2.2 PLright的平衡因子为-1实现代码详细图解建议收藏总结前言由于AVL树也是二叉搜索树为了降低一点难度我们就基于普通二叉搜索树的删除的铺垫再进行相关的操作。一、普通二叉搜索树的删除第一步先找到要删除的结点没有返回false。情况分析1. 删除结点的左右结点都不为空父节点为根节点。例删除1但父节点也是1直接将根节点置为空即可。父节点不为根节点。例删除5结点将其父节点的指向指向空即可。2. 删除结点的左结点为空右节点不为空父节点为根节点删除1这里只需要将2改为根节点。父节点不为根节点。删除5结点将其父节点指向5的右结点即可再删除6即可。3. 删除结点的右结点为空左节点不为空父节点为根节点例直接将0置为根节点即可。父节点不为根节点。例将0的父节点的左孩子的指向改为-1再释放0结点。4. 删除结点的左右结点都不为空这里我们就采用置换法的找左子树的最大节点进行值交换即可。如果删除结点为根节点由于我们置换的是值再对交换后的结点进行讨论交换后的结点必然不为根节点。交换后的结点的右结点必然为空。交换后的结点的左节点可能不为空。交换后的结点其父节点的左边可能为交换后的结点父节点的右边也坑为交换后的结点就此点展开讨论。说明交换后的结点原先为左子树的最大节点我们用left_most_node进行表示。父节点的左节点为left_most_node例待删除结点为1left_most_node为0值交换后1变0, 0变1然后父节点的左节点指向left_most_node的左结点即可。父节点的右节点为left_most_node例待删除结点为1left_most_node为-1值交换后1变-1, -1变1然后父节点的右节点指向left_most_node的左结点即可。如果连普通的二叉搜索树的相关知识有所缺陷可以看一下我之前写的这篇文章——二叉搜索树。本文的普通二叉树的删除也是源自于这篇文章。二、AVL树的删除说明一点在正式讲AVL树之前最好先把AVL树的插入及四种旋转了解清楚因为删除说白了就是在这个基础上分类讨论的结果。如果不清楚, 请看此篇文章AVL树的插入与验证OK铺垫完成正文开始。删除时再基于上面删除的四种情况外我们还要考虑两大类情况。即整棵树的高度变化降一 高度不变化。高度变化会影响上面的树的平衡因子因此需要向上更新。1. 删除结点整棵树的高度不变化两种情况parent的平衡因子为0或者为21.1 parent的平衡因子在删除结点之前为01.1.1 删除结点为parent的左节点整棵树的高度未发生变化调整结束。1.1.2 删除结点为parent的右节点情况与左节点类似上面理解这块可以不用看。整棵树的高度未发生变化调整结束。1.2 parent的平衡因子在调整过程中为21.2.1 删除结点为parent的左节点1.2.1.1 parent的右节点的平衡因子为0进行左旋更新parent_right和parent的平衡因子分别为 -1 与 1整棵树的高度不发生变化调整结束。1.2.1.2 parent的右节点的平衡因子为1左旋之后parent与parent_right的平衡因子变为0结束调整。1.2.2 删除结点为parent的右节点情况与左节点类似上面理解这块可以不用看。1.2.2.1 parent的左节点的平衡因子为0进行右旋更新parent_left与parent的平衡因子分别为1与-1调整结束。1.2.2.2parent的左节点的平衡因子为 -1进行右旋更新parent_left与parent的平衡因子0调整结束。2. 删除结点整棵树的高度变化2.1 删除结点为parent的左节点2.1.1 parent的平衡因子在删除结点之前为 -1调整parent的平衡因子为0继续向上进行调整。2.1.2 parent的平衡因子为2且parent的右结点的平衡因子为-1为了便于描述。这里把parent右节点记作Pright,Pright的左节点记作PRleft2.1.2.1 PRleft的平衡因子为1进行右左双旋且把parent的平衡因子调整为-1PRleft的平衡因子调整为0Pright的平衡因子调整为0。2.1.2.2 PRleft的平衡因子为-1进行右左双旋且把parent的平衡因子调整为0PRleft的平衡因子调整为0Pright的平衡因子调整为1。2.2 删除结点为parent的右节点2.1.1 parent的平衡因子在删除结点之后为 0parent的平衡因子改为0继续向上调整。2.1.2 parent的平衡因子为-2且parent的左节点的平衡因子为1为了便于描述。这里把parent左节点记作Pleft,Pleft的右节点记作PLright2.1.2.1 PLright的平衡因子为 1进行左右双旋调整PLright的平衡因子为0parent的平衡因子为0Pleft的平衡因子为-1。继续向上进行调整。2.1.2.2 PLright的平衡因子为-1进行左右双旋调整PLright的平衡因子为0parent的平衡因子为0Pleft的平衡因子为-1。继续向上进行调整。实现代码每个人的写出来的代码可能不一样但思路还是一致的因此重点不在代码而在分析思路上这里只是贴出来方便大家对照。Node*find(constKeyval){Node*cur_root;while(cur){if(cur-_keyval){//左子树中查找curcur-_left;}elseif(cur-_keyval){//右子树中查找curcur-_right;}else{//找到了returncur;}}returnnullptr;}//为了避免删除时的代码过于冗余将重复利用的代码写成一个函数较好。voidUpDateBFactor(Node*parent,Node*cur){while(parent){if(parent-_leftcur){parent-_bf;}else{parent-_bf--;}//判断平衡因子if(parent-_bf1||parent-_bf-1){break;}elseif(parent-_bf0){curparent;parentparent-_parent;}elseif(parent-_bf2){if(parent-_right-_bf0){//进行左单旋Node*parent_rightparent-_right;RotateL(parent);parent-_bf1;parent_right-_bf-1;//高度不变break;}elseif(parent-_right-_bf1){//左单旋RotateL(parent);//更新平衡因子}else{//进行右左双旋RotateRL(parent);}curparent-_parent;parentcur-_parent;}elseif(parent-_bf-2){//这还有一种特殊情况if(parent-_left-_bf0){Node*parent_leftparent-_left;RotateR(parent);parent-_bf-1;parent_left-_bf1;//此时高度不变break;}elseif(parent-_left-_bf-1){//右单旋RotateR(parent);//高度降低1}else{//左右双旋RotateLR(parent);//高度降低1}curparent-_parent;parentcur-_parent;}else{coutparent-_key:;perror(平衡因子有误);exit(-1);}}}//AVL树结点的删除boolerase(constKeyval){Node*curfind(val);//对cur进行判空if(curnullptr){//说明没找到。returnfalse;}else{Node*parentcur-_parent;Node*delnodecur;Node*delparentcur-_parent;//更新平衡因子然后判断旋转与删除。//左加加右减减//分析四种情况//1.cur的left和right都为空。//2.cur的left为空right不为空。//3.cur的right为空left不为空。//4.cur的right与left都不为空。//在此基础上还要判断cur是否为根节点。//1.cur的left和right都为空。if(cur-_leftnullptrcur-_rightnullptr){//更新平衡因子//判断cur是否为根节点if(cur_root){_rootnullptr;}else{UpDateBFactor(parent,cur);//将父节点的指向清空parentdelnode-_parent;if(parent-_leftdelnode){parent-_leftnullptr;}else{parent-_rightnullptr;}}//删除结点。deletedelnode;}//左不为空并且右为空elseif(cur-_leftcur-_rightnullptr){if(cur_root){//更改根节点_rootcur-_left;//改变根节点的父节点的指向因为平衡因子的绝对值必然小于等于1//因此其左节点只有一个结点。//因此只需更改父节点的指向即可。_root-_parentnullptr;//无需更新平衡因子deletedelnode;}else{Node*cur_leftcur-_left;//更新平衡因子UpDateBFactor(parent,cur);//更新cur_left到cur的位置cur_left-_parentdelnode-_parent;//更新其父节点的指向if(parent-_leftdelnode){parent-_leftcur_left;}else{parent-_rightcur_left;}//删除delnodedeletedelnode;}}elseif(cur-_leftnullptrcur-_right){if(cur_root){//更新根节点_rootcur-_right;//说明为了保证树为AVL树cur-_right必然无左右孩子//更新根节点的信息_root-_parentnullptr;//释放delnodedeletedelnode;}else{Node*parentcur-_parent;Node*cur_rightcur-_right;//更新平衡因子UpDateBFactor(parent,cur);//首先改变cur_right的父节点的指向cur_right-_parentdelparent;//其次改变parent其孩子的指向if(delparent-_leftdelnode){delparent-_leftcur_right;}else{delparent-_rightcur_right;}//最后删除curdeletedelnode;}}//4.cur的right与left都不为空。else{//可以找左子树的最大节点也可以找右子树的最小节点。//进行交换然后更新平衡因子Node*mostleftcur-_left;while(mostleftmostleft-_right){mostleftmostleft-_right;}Node*currmostleft-_left;//直接进行赋值。cur-_keymostleft-_key;cur-_valmostleft-_val;Node*parentmostleft-_parent;UpDateBFactor(parent,mostleft);if(mostleftcur-_left){if(curr!nullptr){//改变cur与curr的指向。curr-_parentcur;cur-_leftcurr;}cur-_leftcurr;}else{Node*parentmostleft-_parent;parent-_rightcurr;if(curr!nullptr){//改变curr的父节点的指向curr-_parentparent;}}//释放mostleftdeletemostleft;//更新平衡因子}returntrue;}}详细图解建议收藏总结删除的例子我们已经举完了那么这里我们再总结一下调整完后整棵树的高度变化降低一个高度会影响上面树的高度需要向上调整。调整完后整棵树的高度不变不会影响上面树的高度无需调整。最坏调整到根节点结束。具体情况的分析我等价替换一下以删除的结点为左节点举例。parent的平衡因子为2且其右节点的平衡因子为-1等价于插入的右左双旋。parent的平衡因子为2且其右节点的平衡因子为1 等价于插入的左双旋。说明 这里的等价是包括平衡因子的调整的核心情况parent的平衡因子为2且parent_right的平衡因子为0.这种情况是需要我们在插入的基础上进行左旋之后手动调平衡因子的。在更新平衡因子时插入是左减减右加加。删除是左加加右减减。判断是否需要向上更新时插入是1或者-1向上调整删除是0向上调整。其实分析了那么多情况其实也就这几点需要我们真正注意的剩余的用插入剩下的轮子套用即可。最后如果觉得文章不错的话点个赞鼓励一下吧
【数据结构】AVL树的删除（解析有点东西哦）
文章目录前言一、普通二叉搜索树的删除1. 删除结点的左右结点都不为空2. 删除结点的左结点为空右节点不为空3. 删除结点的右结点为空左节点不为空4. 删除结点的左右结点都不为空二、AVL树的删除1. 删除结点整棵树的高度不变化1.1 parent的平衡因子在删除结点之前为01.1.1 删除结点为parent的左节点1.1.2 删除结点为parent的右节点1.2 parent的平衡因子在调整过程中为21.2.1 删除结点为parent的左节点1.2.1.1 parent的右节点的平衡因子为01.2.1.2 parent的右节点的平衡因子为11.2.2 删除结点为parent的右节点1.2.2.1 parent的左节点的平衡因子为01.2.2.2parent的左节点的平衡因子为 -12. 删除结点整棵树的高度变化2.1 删除结点为parent的左节点2.1.1 parent的平衡因子在删除结点之前为 -12.1.2 parent的平衡因子为2且parent的右结点的平衡因子为-12.1.2.1 PRleft的平衡因子为12.1.2.2 PRleft的平衡因子为-12.2 删除结点为parent的右节点2.1.1 parent的平衡因子在删除结点之后为 02.1.2 parent的平衡因子为-2且parent的左节点的平衡因子为12.1.2.1 PLright的平衡因子为 12.1.2.2 PLright的平衡因子为-1实现代码详细图解建议收藏总结前言由于AVL树也是二叉搜索树为了降低一点难度我们就基于普通二叉搜索树的删除的铺垫再进行相关的操作。一、普通二叉搜索树的删除第一步先找到要删除的结点没有返回false。情况分析1. 删除结点的左右结点都不为空父节点为根节点。例删除1但父节点也是1直接将根节点置为空即可。父节点不为根节点。例删除5结点将其父节点的指向指向空即可。2. 删除结点的左结点为空右节点不为空父节点为根节点删除1这里只需要将2改为根节点。父节点不为根节点。删除5结点将其父节点指向5的右结点即可再删除6即可。3. 删除结点的右结点为空左节点不为空父节点为根节点例直接将0置为根节点即可。父节点不为根节点。例将0的父节点的左孩子的指向改为-1再释放0结点。4. 删除结点的左右结点都不为空这里我们就采用置换法的找左子树的最大节点进行值交换即可。如果删除结点为根节点由于我们置换的是值再对交换后的结点进行讨论交换后的结点必然不为根节点。交换后的结点的右结点必然为空。交换后的结点的左节点可能不为空。交换后的结点其父节点的左边可能为交换后的结点父节点的右边也坑为交换后的结点就此点展开讨论。说明交换后的结点原先为左子树的最大节点我们用left_most_node进行表示。父节点的左节点为left_most_node例待删除结点为1left_most_node为0值交换后1变0, 0变1然后父节点的左节点指向left_most_node的左结点即可。父节点的右节点为left_most_node例待删除结点为1left_most_node为-1值交换后1变-1, -1变1然后父节点的右节点指向left_most_node的左结点即可。如果连普通的二叉搜索树的相关知识有所缺陷可以看一下我之前写的这篇文章——二叉搜索树。本文的普通二叉树的删除也是源自于这篇文章。二、AVL树的删除说明一点在正式讲AVL树之前最好先把AVL树的插入及四种旋转了解清楚因为删除说白了就是在这个基础上分类讨论的结果。如果不清楚, 请看此篇文章AVL树的插入与验证OK铺垫完成正文开始。删除时再基于上面删除的四种情况外我们还要考虑两大类情况。即整棵树的高度变化降一 高度不变化。高度变化会影响上面的树的平衡因子因此需要向上更新。1. 删除结点整棵树的高度不变化两种情况parent的平衡因子为0或者为21.1 parent的平衡因子在删除结点之前为01.1.1 删除结点为parent的左节点整棵树的高度未发生变化调整结束。1.1.2 删除结点为parent的右节点情况与左节点类似上面理解这块可以不用看。整棵树的高度未发生变化调整结束。1.2 parent的平衡因子在调整过程中为21.2.1 删除结点为parent的左节点1.2.1.1 parent的右节点的平衡因子为0进行左旋更新parent_right和parent的平衡因子分别为 -1 与 1整棵树的高度不发生变化调整结束。1.2.1.2 parent的右节点的平衡因子为1左旋之后parent与parent_right的平衡因子变为0结束调整。1.2.2 删除结点为parent的右节点情况与左节点类似上面理解这块可以不用看。1.2.2.1 parent的左节点的平衡因子为0进行右旋更新parent_left与parent的平衡因子分别为1与-1调整结束。1.2.2.2parent的左节点的平衡因子为 -1进行右旋更新parent_left与parent的平衡因子0调整结束。2. 删除结点整棵树的高度变化2.1 删除结点为parent的左节点2.1.1 parent的平衡因子在删除结点之前为 -1调整parent的平衡因子为0继续向上进行调整。2.1.2 parent的平衡因子为2且parent的右结点的平衡因子为-1为了便于描述。这里把parent右节点记作Pright,Pright的左节点记作PRleft2.1.2.1 PRleft的平衡因子为1进行右左双旋且把parent的平衡因子调整为-1PRleft的平衡因子调整为0Pright的平衡因子调整为0。2.1.2.2 PRleft的平衡因子为-1进行右左双旋且把parent的平衡因子调整为0PRleft的平衡因子调整为0Pright的平衡因子调整为1。2.2 删除结点为parent的右节点2.1.1 parent的平衡因子在删除结点之后为 0parent的平衡因子改为0继续向上调整。2.1.2 parent的平衡因子为-2且parent的左节点的平衡因子为1为了便于描述。这里把parent左节点记作Pleft,Pleft的右节点记作PLright2.1.2.1 PLright的平衡因子为 1进行左右双旋调整PLright的平衡因子为0parent的平衡因子为0Pleft的平衡因子为-1。继续向上进行调整。2.1.2.2 PLright的平衡因子为-1进行左右双旋调整PLright的平衡因子为0parent的平衡因子为0Pleft的平衡因子为-1。继续向上进行调整。实现代码每个人的写出来的代码可能不一样但思路还是一致的因此重点不在代码而在分析思路上这里只是贴出来方便大家对照。Node*find(constKeyval){Node*cur_root;while(cur){if(cur-_keyval){//左子树中查找curcur-_left;}elseif(cur-_keyval){//右子树中查找curcur-_right;}else{//找到了returncur;}}returnnullptr;}//为了避免删除时的代码过于冗余将重复利用的代码写成一个函数较好。voidUpDateBFactor(Node*parent,Node*cur){while(parent){if(parent-_leftcur){parent-_bf;}else{parent-_bf--;}//判断平衡因子if(parent-_bf1||parent-_bf-1){break;}elseif(parent-_bf0){curparent;parentparent-_parent;}elseif(parent-_bf2){if(parent-_right-_bf0){//进行左单旋Node*parent_rightparent-_right;RotateL(parent);parent-_bf1;parent_right-_bf-1;//高度不变break;}elseif(parent-_right-_bf1){//左单旋RotateL(parent);//更新平衡因子}else{//进行右左双旋RotateRL(parent);}curparent-_parent;parentcur-_parent;}elseif(parent-_bf-2){//这还有一种特殊情况if(parent-_left-_bf0){Node*parent_leftparent-_left;RotateR(parent);parent-_bf-1;parent_left-_bf1;//此时高度不变break;}elseif(parent-_left-_bf-1){//右单旋RotateR(parent);//高度降低1}else{//左右双旋RotateLR(parent);//高度降低1}curparent-_parent;parentcur-_parent;}else{coutparent-_key:;perror(平衡因子有误);exit(-1);}}}//AVL树结点的删除boolerase(constKeyval){Node*curfind(val);//对cur进行判空if(curnullptr){//说明没找到。returnfalse;}else{Node*parentcur-_parent;Node*delnodecur;Node*delparentcur-_parent;//更新平衡因子然后判断旋转与删除。//左加加右减减//分析四种情况//1.cur的left和right都为空。//2.cur的left为空right不为空。//3.cur的right为空left不为空。//4.cur的right与left都不为空。//在此基础上还要判断cur是否为根节点。//1.cur的left和right都为空。if(cur-_leftnullptrcur-_rightnullptr){//更新平衡因子//判断cur是否为根节点if(cur_root){_rootnullptr;}else{UpDateBFactor(parent,cur);//将父节点的指向清空parentdelnode-_parent;if(parent-_leftdelnode){parent-_leftnullptr;}else{parent-_rightnullptr;}}//删除结点。deletedelnode;}//左不为空并且右为空elseif(cur-_leftcur-_rightnullptr){if(cur_root){//更改根节点_rootcur-_left;//改变根节点的父节点的指向因为平衡因子的绝对值必然小于等于1//因此其左节点只有一个结点。//因此只需更改父节点的指向即可。_root-_parentnullptr;//无需更新平衡因子deletedelnode;}else{Node*cur_leftcur-_left;//更新平衡因子UpDateBFactor(parent,cur);//更新cur_left到cur的位置cur_left-_parentdelnode-_parent;//更新其父节点的指向if(parent-_leftdelnode){parent-_leftcur_left;}else{parent-_rightcur_left;}//删除delnodedeletedelnode;}}elseif(cur-_leftnullptrcur-_right){if(cur_root){//更新根节点_rootcur-_right;//说明为了保证树为AVL树cur-_right必然无左右孩子//更新根节点的信息_root-_parentnullptr;//释放delnodedeletedelnode;}else{Node*parentcur-_parent;Node*cur_rightcur-_right;//更新平衡因子UpDateBFactor(parent,cur);//首先改变cur_right的父节点的指向cur_right-_parentdelparent;//其次改变parent其孩子的指向if(delparent-_leftdelnode){delparent-_leftcur_right;}else{delparent-_rightcur_right;}//最后删除curdeletedelnode;}}//4.cur的right与left都不为空。else{//可以找左子树的最大节点也可以找右子树的最小节点。//进行交换然后更新平衡因子Node*mostleftcur-_left;while(mostleftmostleft-_right){mostleftmostleft-_right;}Node*currmostleft-_left;//直接进行赋值。cur-_keymostleft-_key;cur-_valmostleft-_val;Node*parentmostleft-_parent;UpDateBFactor(parent,mostleft);if(mostleftcur-_left){if(curr!nullptr){//改变cur与curr的指向。curr-_parentcur;cur-_leftcurr;}cur-_leftcurr;}else{Node*parentmostleft-_parent;parent-_rightcurr;if(curr!nullptr){//改变curr的父节点的指向curr-_parentparent;}}//释放mostleftdeletemostleft;//更新平衡因子}returntrue;}}详细图解建议收藏总结删除的例子我们已经举完了那么这里我们再总结一下调整完后整棵树的高度变化降低一个高度会影响上面树的高度需要向上调整。调整完后整棵树的高度不变不会影响上面树的高度无需调整。最坏调整到根节点结束。具体情况的分析我等价替换一下以删除的结点为左节点举例。parent的平衡因子为2且其右节点的平衡因子为-1等价于插入的右左双旋。parent的平衡因子为2且其右节点的平衡因子为1 等价于插入的左双旋。说明 这里的等价是包括平衡因子的调整的核心情况parent的平衡因子为2且parent_right的平衡因子为0.这种情况是需要我们在插入的基础上进行左旋之后手动调平衡因子的。在更新平衡因子时插入是左减减右加加。删除是左加加右减减。判断是否需要向上更新时插入是1或者-1向上调整删除是0向上调整。其实分析了那么多情况其实也就这几点需要我们真正注意的剩余的用插入剩下的轮子套用即可。最后如果觉得文章不错的话点个赞鼓励一下吧
