一.平衡二叉树的插入&删除:

平衡二叉树具有二叉排序树的特性即"左子树结点值<根结点值<右子树结点值",

平衡二叉树在二叉排序树的基础上需要保证每一个结点都是平衡的即平衡二叉树中"树上任一结点的左子树和右子树的高度只差不超过1",

所以对于平衡二叉树的插入操作,首先要保证插入新结点之后,需要保持平衡二叉树中任意结点的"左子树结点值<根结点值<右子树结点值",其次,如果插入的新结点导致二叉树变得不平衡,那么就需要调整使其平衡,共有4种情况"LL、RR、LR、RL",

平衡二叉树的删除操作也是同理,在删除一个结点之后必须要保证它依然是一棵二叉排序树即任意结点的"左子树结点值<根结点值<右子树结点值",结点被删除也有可能导致不平衡的现象,删除结点之后导致的不平衡现象同样有4种情况"LL、RR、LR、RL",

所以插入操作和删除操作有很多类似的地方。


二.平衡二叉树的删除步骤:

如上图:

步骤一:按照二叉排序树删除结点的方法来删除目标结点,大致操作如下图,详情见"7.5.二叉排序树(英文缩写为BST,又名二叉查找树)"

步骤二:删除目标结点之后,如果出现某个结点不平衡的现象,需要"一路向北"即从被删除的结点开始,一路往上找第一个不平衡的结点即最小不平衡子树,调整"最小不平衡子树"使其平衡;如果找不到不平衡的结点,说明整棵树平衡,完结撒花;

注:只有出现不平衡的结点时才走以下步骤:

步骤三:找到最小不平衡子树下面"个头"最高的儿子、孙子;

步骤四:根据孙子的位置,调整平衡(分为四种情况:LL、RR、LR、RL,类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)");

步骤五:如果经过步骤四中的调整之后导致了不平衡向上传导,回到步骤二重复刚才的步骤。


三.平衡二叉树(AVL树)删除操作演示:

1.例一:未出现最小不平衡子树

以上述图片右边的平衡二叉树为例,

在该平衡二叉树中删除关键字为9的结点,平衡二叉树的删除操作与二叉排序树的删除操作一样,

因此由于关键字为9的结点是叶子结点,所以直接删除即可,

如下图:

如上图,

接下来要判断删除结点9之后,结点9的父结点以及结点9的祖先结点是否有不平衡的现象,

所以接下来要"一路向北"找到最小不平衡子树,如果找不到不平衡的结点即找不到最小不平衡子树则直接结束算法,

从删除的结点9出发,在结点9的父结点和结点9的祖先结点中都没有出现不平衡的现象,

所以这就说明删除结点9的操作并没有导致结点9的父结点和结点9的任何一个祖先结点出现不平衡的现象,

至此,该算法结束。

这是最简单的一种情况,删除结点之后没有出现不平衡的情况。

如下图:

2.例二:"RR"情况

如上图,

现在要删除关键字为55的结点,

在该二叉树中关键字为55的结点是叶子结点,按照二叉排序树的规则来看关键字为55的结点可以直接删除,

接下来要判断关键字为55的结点的父结点和关键字为55的结点的所有祖先结点是否有不平衡的现象,

需要"一路向北"找最小不平衡子树,

可知从55结点出发,往上找第一个出现不平衡的结点是75结点,因为75结点此时的左子树的高度为1、右子树的高度为3即平衡因子=1-3=-2,所以以75结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以75结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点75的"个头"最高的儿子、孙子,

根结点75有两个儿子即左孩子60结点和右孩子80结点,

对于60结点,60结点是叶子结点,所以以60结点为根结点的子树的高度为1;

对于80结点,80结点还有子孙结点,所以以80结点为根结点的子树的高度为3,

因此75结点中"个头"最高的儿子是右孩子80结点,

继续在75结点"个头"最高的儿子即80结点中往下找75结点"个头"最高的孙子,

结点80有两个儿子即左孩子77结点和右孩子90结点,

对于77结点,77结点是叶子结点,所以以77结点为根结点的子树的高度为1;

对于90结点,90结点还有儿子结点,所以以90结点为根结点的子树的高度为2,

因此80结点中"个头"最高的儿子是右孩子90结点,

所以75结点中"个头"最高的孙子是90结点,

所以最小不平衡子树即以75结点为根结点的子树下,"个头"最高的儿子是80结点、"个头"最高的孙子是90结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为75结点,"个头"最高的孙子为90结点,

显然90结点位于75结点的右孩子的右子树上,属于RR情况,

对于RR的情况,要把"个头"最高的儿子即80结点左单旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

需要把80结点左单旋,替代75结点的位置,

此时的75结点会变成80结点的左孩子,

80结点原本的左孩子77结点就不能在80结点的左孩子上了,因为80结点的左孩子已经被替代,

根据二叉排序树的特性"左子树结点值<根结点值<右子树结点值"可以把77结点挂在75结点的右孩子上,

如下图:

如上图,

进行左单旋操作之后,最小不平衡子树恢复平衡,

接下来要检查结点不平衡的情况是否有向上传导,什么意思呢?

在未调整最小不平衡子树之前,该最小不平衡子树的高度为4,左旋操作之后该树的高度从4变为3,所以刚才的树的高度产生了变化,这就有可能导致该树的父结点以及祖先结点的平衡性发生影响,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束,

如下图:

3.例三:"RL"情况

以上述图片右边的平衡二叉树为例,

现在要删除关键字为32的结点,由于关键字为32的结点为叶子结点,根据二叉排序树的删除规则可知32结点可以直接删除,

如下图:

如上图,

从关键字为32的结点的位置出发,"一路向北"判断关键字为32的结点的父结点以及祖先结点是否有不平衡的现象,

可知"一路向北"的过程中第一个出现不平衡的结点是44结点,因为44结点此时的左子树的高度为1、右子树的高度为3即平衡因子=1-3=-2,所以以44结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以44结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点44的"个头"最高的儿子、孙子,

根结点44有两个儿子即左孩子17结点和右孩子78结点,

对于17结点,17结点是叶子结点,所以以17结点为根结点的子树的高度为1;

对于78结点,78结点还有子孙结点,所以以78结点为根结点的子树的高度为3,

因此44结点中"个头"最高的儿子是右孩子78结点,

继续在44结点"个头"最高的儿子即78结点中往下找44结点"个头"最高的孙子,

结点78有两个儿子即左孩子50结点和右孩子88结点,

对于50结点,50结点还有儿子结点,所以以50结点为根结点的子树的高度为2,

对于88结点,88结点是叶子结点,所以以88结点为根结点的子树的高度为1;

因此78结点中"个头"最高的儿子是左孩子50结点,

所以44结点中"个头"最高的孙子是50结点,

所以最小不平衡子树即以44结点为根结点的子树下,"个头"最高的儿子是78结点、"个头"最高的孙子是50结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为44结点,"个头"最高的孙子为50结点,

显然50结点位于44结点的右孩子的左子树上,属于RL情况,

对于RL的情况,要把"个头"最高的孙子即50结点先右旋,再左旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

首先把"个头"最高的孙子即50结点进行右旋,使得结点50代替结点78的位置,

以78结点为根结点的子树成为50结点的右孩子,50结点原本的右孩子62结点就不能在50结点的右孩子上了,因为50结点的右孩子已经被替代,

根据二叉排序树的特性即"左子树结点值<根结点值<右子树结点值"可以把62结点挂在78结点的左孩子上

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

再把50结点进行左旋,替代44结点的位置,左旋之后44结点会变成50结点的左孩子,

以44结点为根结点的子树成为50结点的左孩子,50结点原本的左孩子48结点就不能在50结点的左孩子上了,因为50结点的左孩子已经被替代,

根据二叉排序树的特性即"左子树结点值<根结点值<右子树结点值"可以把48结点挂在44结点的右孩子上

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

对"最小不平衡子树"的"个头"最高的孙子先右旋,再左旋的调整之后,该"最小不平衡子树"就恢复了平衡,

接下来要检查结点不平衡的情况是否有向上传导,什么意思呢?

在未调整最小不平衡子树之前,该最小不平衡子树的高度为4,调整之后该树的高度从4变为3,所以刚才的树的高度产生了变化,这就有可能导致该树的父结点以及祖先结点的平衡性发生影响,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束,

如下图:

4.例四:有关"不平衡"向上传导

以上述图片右边的平衡二叉树为例,

现在要删除关键字为32的结点,由于关键字为32的结点为叶子结点,根据二叉排序树的删除规则可知32结点可以直接删除,

如下图:

如上图,

从关键字为32的结点的位置出发,"一路向北"判断关键字为32的结点的父结点以及祖先结点是否有不平衡的现象,

可知"一路向北"的过程中第一个出现不平衡的结点是44结点,因为44结点此时的左子树的高度为1、右子树的高度为3即平衡因子=1-3=-2,所以以44结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以44结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点44的"个头"最高的儿子、孙子,

根结点44有两个儿子即左孩子17结点和右孩子78结点,

对于17结点,17结点是叶子结点,所以以17结点为根结点的子树的高度为1;

对于78结点,78结点还有子孙结点,所以以78结点为根结点的子树的高度为3,

因此44结点中"个头"最高的儿子是右孩子78结点,

继续在44结点"个头"最高的儿子即78结点中往下找44结点"个头"最高的孙子,

结点78有两个儿子即左孩子50结点和右孩子88结点,

对于50结点,50结点还有儿子结点,所以以50结点为根结点的子树的高度为2;

对于88结点,88结点是叶子结点,所以以88结点为根结点的子树的高度为1,

因此78结点中"个头"最高的儿子是左孩子50结点,

所以44结点中"个头"最高的孙子是50结点,

所以最小不平衡子树即以44结点为根结点的子树下,"个头"最高的儿子是78结点、"个头"最高的孙子是50结点,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为44结点,"个头"最高的孙子为50结点,

显然50结点位于44结点的右孩子的左子树上,属于RL情况,

对于RL的情况,要把"个头"最高的孙子即50结点先右旋,再左旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

对"最小不平衡子树"的"个头"最高的孙子先右旋,再左旋的调整之后,该"最小不平衡子树"就恢复了平衡,

接下来要检查结点不平衡的情况是否有向上传导,什么意思呢?

在未调整最小不平衡子树之前,该最小不平衡子树的高度为4,调整之后该树的高度从4变为3,所以刚才的树的高度产生了变化,这就有可能导致该树的父结点以及祖先结点的平衡性发生影响,

本例中该树的父结点33出现了不平衡的现象即不平衡向上传导,

如下图:

如上图,

此时结点33的左子树的高度为5,右子树的高度为3,所以结点33的平衡因子=5-3=2即结点33不平衡,

那么就需要找最小不平衡子树,从刚才调整的子树的根结点50出发"一路向北"找最小不平衡子树,

也就是找到第一个不平衡的祖先结点,显然以33结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以33结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点33的"个头"最高的儿子、孙子,

根结点33有两个儿子即左孩子10结点和右孩子50结点,

对于10结点,10结点还有子孙结点,所以以10结点为根结点的子树的高度为5,

对于50结点,50结点还有子孙结点,所以以50结点为根结点的子树的高度为3,

因此33结点中"个头"最高的儿子是左孩子10结点,

继续在33结点"个头"最高的儿子即10结点中往下找33结点"个头"最高的孙子,

结点10有两个儿子即左孩子5结点和右孩子20结点,

对于5结点,5结点还有子孙结点,所以以5结点为根结点的子树的高度为3,

对于20结点,20结点还有子孙结点,所以以20结点为根结点的子树的高度为4,

因此10结点中"个头"最高的儿子是右孩子20结点,

所以33结点中"个头"最高的孙子是20结点,

所以最小不平衡子树即以33结点为根结点的子树下,"个头"最高的儿子是10结点、"个头"最高的孙子是20结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为33结点,"个头"最高的孙子为20结点,

显然20结点位于33结点的左孩子的右子树上,属于LR情况,

对于LR的情况,要把"个头"最高的孙子即20结点先左旋,再右旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

首先把"个头"最高的孙子即20结点进行左旋,使得结点20代替结点10的位置,

以10结点为根结点的子树成为20结点的左孩子,20结点原本的左子树即以15结点为根结点的子树就不能在20结点的左孩子上了,因为20结点的左孩子已经被替代,

根据二叉排序树的特性即"左子树结点值<根结点值<右子树结点值"可以把以15结点为根结点的子树挂在10结点的右孩子上

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

再把20结点进行右旋,替代33结点的位置,右旋之后33结点会变成20结点的右孩子,

以33结点为根结点的子树成为20结点的右孩子,20结点原本的右子树即以25结点为根结点的子树就不能在20结点的右孩子上了,因为20结点的右孩子已经被替代,

根据二叉排序树的特性即"左子树结点值<根结点值<右子树结点值"可以把25结点挂在33结点的左孩子上

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

对"最小不平衡子树"的"个头"最高的孙子先左旋,再右旋的调整之后,该"最小不平衡子树"就恢复了平衡,

接下来要检查结点不平衡的情况是否有向上传导,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束。

5.例五:理解删除结点的时候如何按照二叉排序树的规则进行删除

以上述图片右边的平衡二叉树为例,

现在要删除关键字为75的结点,按照二叉排序树的删除规则,首先75结点有两棵子树,这种情况下可以用两种方式来处理->方式一:用75结点的前驱结点来替代75结点的位置;方式二:用75结点的后继结点来替代75结点的位置(详情见"7.5.二叉排序树(英文缩写为BST,又名二叉查找树)"),

现在用75结点的前驱结点来替代75结点的位置,如何找到75结点的前驱结点呢?

只需要从当前要删除的结点75的左子树中找到关键字的值最大的结点,用该结点来替代被删除的结点75,

这个过程要找到被删除的结点的左子树中按照中序遍历最后一个被访问的结点,因为中序遍历最后一个被访问的结点一定是最右子树上的结点,根据二叉排序树的特性,最右子树上的结点的关键字的值是最大的(左子树也是二叉排序树,如果中序遍历二叉排序树,可以得到一个递增的有序序列,最后一个被访问的结点就是最大的结点),

所以对于被删除的结点的左子树中按照中序遍历被访问的最后一个结点,该结点就是左子树当中最大的结点(详情见"5.11.在线索二叉树中找前驱和后继"的"二.中序线索二叉树找中序前驱"),

结论:只需要在被删除的结点的左子树当中找到最右下角的结点,这个结点就是被删除的结点的左子树中关键字的值最大的结点,用这个结点替代被删除的结点,这样就可以保证二叉排序树的特性不变。

所以蓝色框的60结点就是75结点的前驱结点,

接下来就要用蓝色框的60结点顶替75结点的位置,这里所谓的"顶替",其实就是数据的复制,

也就是把蓝色框的60结点的数据完全赋值给75结点,赋值完数据之后就可以把删除操作转化为对前驱结点60(下图灰色框的60结点)的删除操作,

如下图:

如上图,

现在就需要删除灰色框的60结点,

继续按照二叉排序树的删除规则来看,灰色框的60结点只有一棵子树,因此只需要用该子树顶替灰色框的60结点的位置即可,

注:这里并不是把灰色框的60结点的子树复制到灰色框的60结点上就行,而是要让灰色框的60结点的子树挂到蓝色框的60结点的左孩子指针上,再把刚才删除的灰色框的60结点直接释放即可,

如下图:

如上图,

刚才删除的位置就是上述图片55结点的位置,

从55结点的位置出发,"一路向北"判断55结点的父结点以及祖先结点是否有不平衡的现象,

可知"一路向北"的过程中第一个出现不平衡的结点是60结点,因为60结点此时的左子树的高度为1、右子树的高度为3即平衡因子=1-3=-2,所以以60结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以60结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点60的"个头"最高的儿子、孙子,

根结点60有两个儿子即左孩子55结点和右孩子80结点,

对于55结点,55结点是叶子结点,所以以55结点为根结点的子树的高度为1;

对于80结点,80结点还有子孙结点,所以以80结点为根结点的子树的高度为3,

因此60结点中"个头"最高的儿子是右孩子80结点,

继续在60结点"个头"最高的儿子即80结点中往下找60结点"个头"最高的孙子,

结点80有两个儿子即左孩子77结点和右孩子90结点,

对于77结点,77结点是叶子结点,所以以77结点为根结点的子树的高度为1;

对于90结点,90结点还有儿子结点,所以以90结点为根结点的子树的高度为2,

因此80结点中"个头"最高的儿子是右孩子90结点,

所以60结点中"个头"最高的孙子90结点,

所以最小不平衡子树即以60结点为根结点的子树下,"个头"最高的儿子是80结点、"个头"最高的孙子是90结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为60结点,"个头"最高的孙子为90结点,

显然90结点位于60结点的右孩子的右子树上,属于RR情况,

对于RR的情况,要把"个头"最高的儿子即80结点左单旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

需要把80结点左单旋,替代60结点的位置,

此时的60结点会变成80结点的左孩子,

80结点原本的左孩子77结点就不能在80结点的左孩子上了,因为80结点的左孩子已经被替代,

根据二叉排序树的特性"左子树结点值<根结点值<右子树结点值"可以把77结点挂在60结点的右孩子上,

如下图:

如上图,

进行左单旋操作之后,最小不平衡子树恢复平衡,

接下来要检查结点不平衡的情况是否有向上传导,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束。

6.例六:例五的另一种方式

以上述图片右边的平衡二叉树为例,

现在要删除关键字为75的结点,按照二叉排序树的删除规则,首先75结点有两棵子树,这种情况下可以用两种方式来处理->方式一:用75结点的前驱结点来替代75结点的位置;方式二:用75结点的后继结点来替代75结点的位置(详情见"7.5.二叉排序树(英文缩写为BST,又名二叉查找树)"),

现在用75结点的后继结点来替代75结点的位置,如何找到75结点的后继结点呢?

只需要从当前要删除的结点75的右子树中找到关键字的值最小的结点,用该结点来替代被删除的结点,

这个过程要找到被删除的结点的右子树中按照中序遍历第一个被访问的结点,因为中序遍历第一个被访问的结点一定是最左子树上的结点,根据二叉排序树的特性,最左子树上的结点的关键字的值是最小的(右子树也是二叉排序树,如果中序遍历二叉排序树,可以得到一个递增的有序序列,第一个被访问的结点就是最小的结点),

所以对于被删除的结点的右子树中按照中序遍历被访问的第一个结点,该结点就是右子树当中最小的结点(详情见"5.11.在线索二叉树中找前驱和后继"的"一.中序线索二叉树找中序后继"),

结论:只需要在被删除的结点的右子树当中找到最左下角的结点,这个结点就是被删除的结点的右子树中关键字的值最小的结点,用这个结点替代被删除的结点,这样就可以保证二叉排序树的特性不变。

所以蓝色框的77结点就是75结点的后继结点,

接下来就要用蓝色框的77结点顶替75结点的位置,这里所谓的"顶替",其实就是数据的复制,

也就是把蓝色框的77结点的数据完全赋值给75结点,赋值完数据之后就可以把删除操作转化为对后继结点77(下图灰色框的60结点)的删除操作,

如下图:

如上图:

由于77结点是叶子结点,所以直接删除即可,

刚才删除的位置就是上述图片77结点的位置,

从77结点的位置出发,"一路向北"判断77结点的父结点以及祖先结点是否有不平衡的现象,

可知"一路向北"的过程中第一个出现不平衡的结点是80结点,因为80结点此时的左子树的高度为0、右子树的高度为2即平衡因子=0-2=-2,所以以80结点为根结点的子树就是最小不平衡子树,

如下图:

如上图,

由于产生了不平衡的现象,就需要调整最小不平衡子树即以80结点为根结点的子树使其平衡,

需要找到最小不平衡子树中根结点80的"个头"最高的儿子、孙子,

根结点80只有一个儿子即右孩子90结点,

因此80结点中"个头"最高的儿子是右孩子90结点,

继续在80结点"个头"最高的儿子即90结点中往下找80结点"个头"最高的孙子,

结点90有两个儿子即左孩子85结点和右孩子95结点,

对于85结点,85结点是叶子结点,所以以85结点为根结点的子树的高度为1;

对于95结点,95结点是叶子结点,所以以95结点为根结点的子树的高度为1;

因此90结点中"个头"最高的儿子可以是左孩子85结点,也可以是右孩子95结点,

所以80结点中"个头"最高的孙子可以是85结点,也可以是95结点,

这里选择选择95结点为80结点中"个头"最高的孙子,

所以最小不平衡子树即以80结点为根结点的子树下,"个头"最高的儿子是90结点、"个头"最高的孙子是95结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为80结点,"个头"最高的孙子为95结点,

显然95结点位于80结点的右孩子的右子树上,属于RR情况,

对于RR的情况,要把"个头"最高的儿子即90结点左单旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

需要把90结点左单旋,替代80结点的位置,

此时的80结点会变成90结点的左孩子,

90结点原本的左孩子85结点就不能在90结点的左孩子上了,因为90结点的左孩子已经被替代,

根据二叉排序树的特性"左子树结点值<根结点值<右子树结点值"可以把85结点挂在80结点的右孩子上,

如下图:

如上图,

进行左单旋操作之后,最小不平衡子树恢复平衡,

接下来要检查结点不平衡的情况是否有向上传导,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束。

如下图:

如上图,

之前在最小不平衡子树即以80结点为根结点的子树下,"个头"最高的儿子是90结点、取"个头"最高的孙子是95结点,

通过之前的分析,80结点中"个头"最高的孙子也可以是85结点,

如下图:

如上图,

根据"个头"最高的孙子的位置,调整"最小不平衡子树"使其平衡,

"最小不平衡子树"的根结点为80结点,"个头"最高的孙子为85结点,

显然85结点位于80结点的右孩子的左子树上,属于RL情况,

对于RL的情况,要把"个头"最高的孙子即85结点先右旋,再左旋(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

首先把"个头"最高的孙子即85结点进行右旋,使得结点85代替结点90的位置,

以90结点为根结点的子树成为85结点的右孩子,

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

再把85结点进行左旋,替代80结点的位置,左旋之后80结点会变成85结点的左孩子,

(类似平衡二叉树的插入操作,详情见"7.6.平衡二叉树(英文缩写为AVL树)"),

如下图:

如上图,

对"最小不平衡子树"的"个头"最高的孙子先右旋,再左旋的调整之后,该"最小不平衡子树"就恢复了平衡,

接下来要检查结点不平衡的情况是否有向上传导,

本例中没有出现不平衡向上传导的现象,至此,整个算法结束。


四.总结:

  • 如果一棵平衡二叉树的结点总数为n,那么该平衡二叉树删除操作的时间复杂度为O(log₂n)


更多推荐