先看一个平衡二叉树创建的例子。假设现在表中关键字序列为(13,24,37),具体的平衡二叉树创建过程如下图所示:
我们可以发现结点37的插入导致二叉树的根结点13的平衡因子变为-2,此时二叉树没有达到平衡状态。其中离插入结点最近且平衡因子绝对值超过1的祖先结点,以该结点为根的子树称为最小不平衡树, 我们可将重新平衡的范围局限于这颗树或子树。
一般情况下,假设最小不平衡树的根结点为A,则失去平衡后进行调整的规律可归纳为以下四种情况,注意新加节点的位置变化
由于在A左子树根结点的左子树上插入结点C,A的平衡因子由1增至2,致使以A为根的子树失去平衡,则需要进行一次向右的顺时针旋转操作,如下图所示。
这里对B的右子树Br,操作后会成为A(B的父节点)的左子树
由于在A的右子树根结点的右子树上插入结点C,A的平衡因子由-1变为-2,致使以A为根结点的子树失去平衡,则需进行一次向左的逆时针旋转操作,如下图所示。
这里对B的左子树Bl,操作后会成为A(B的父节点)的右子树
由于在A的左子树根结点的右子树上插入结点,A的平衡因子由1增至2,致使以A为根结点的子树失去平衡,则需要进行二次旋转操作。第一次对B及其右子树进行逆时针旋转,C转上去成为B的根,这时变成了LL型,所以第二次进行LL型的顺时针旋转即可恢复平衡。如果C原来有左子树,则调整C的左子树为B的右子树,如下图所示。
这里Cl会变成B的右子树(变成LL型),再变成B的右子树
如果是Cr,会变成C的右子树(变成LL型),再变成A的左子树
由于在A的右子树根结点的左子树上插入结点,A的平衡因子由-1变为-2,致使以A为根结点的子树失去平衡,则旋转方法和LR型相对称,也需进行两次旋转,第一次对B及其左子树进行顺时针右旋,C转上去成为B的根,这时变成了RR型,再进行RR型的逆时针左旋,如下图所示。
这里Cl先变成C的左子树(变成RR型),再变成A的右子树
如果是Cr,先变成B的左子树(变成RR型),再变成B的左子树
综上,LL型与RR型对称,LR型和RL型对称。我们可以由中序遍历(左->根->右)所得关键字序列自小到大有序来证明平衡调整的正确;另外,平衡二叉树的深度在插入结点前和插入结点并平衡调整之后是相同的。
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论