平衡二叉树的插入与调整 | Chen0495的空间站

¶平衡二叉树相关概念

平衡二叉树(AVL): 树上任一节点的左子树与右子树高度之差不超过1.
节点的平衡因子: 节点的左子树与与右子树高度之差.
最小不平衡子树: 平衡树中插入一个新节点后出现了不平衡的现象,从该新插入节点所在分支进行回溯,找到第一个不平衡的节点,以该节点为根的子树叫最小不平衡子树.
只要将最小不平衡子树调整到平衡状态,插入节点所影响的所有祖先节点的平衡因子也会恢复正常.

[{"url":"https://img.chen0495.top/img/20210528195844.png","alt":"平衡二叉树"},{"url":"https://img.chen0495.top/img/20210528200420.png","alt":"非平衡二叉树"},{"url":"https://img.chen0495.top/img/20210528200829.png","alt":"最小不平衡子树"},{"url":"https://img.chen0495.top/img/20210528201032.png","alt":"平衡树的恢复"}]

¶平衡二叉树的恢复

平衡二叉树的平衡被破坏的情况可分为以下四种.其恢复操作也不尽相同.

¶LL平衡旋转(右单旋转)

即在最小不平衡树的根节点A的左孩子的左树上插入导致的不平衡.此处注意A是结果而非提前知道.
如下图:
LL_0
我们在BL上插入新节点,导致A第一个不平衡,这意味着A的原平衡因子是1,B的平衡因子是0,于是我们假设BL、BR、AR的高度相等且都为H.
之后的情况也与之同理,不再重复.
于是我们可以得到BL < B < BR < A < AR.插入之后BL高度变为H+1,B和A的平衡因子也加一.
LL恢复
恢复手段是将其拆分并重新组合(不失顺序,且不能用BL,AR为根,因为可能高度为0即均没有节点),将B作为根节点,A作为B的右树,B原右树作为A的左树.
教科书上则用旋转来描述: 令节点A的左孩子B右上旋替代A作为根节点,并将A节点向右下旋成为B的右子树的根节点,而B的原右子树作为A节点的左子树.

¶RR平衡旋转(左单旋转)

即在最小平衡树的根节点A的右孩子的右树上插入导致的不平衡.

我们得到序列AL < A < BL < B < BR.恢复手段是拆分组合,将B作为根节点,A作为B的左树,B原来的左树作为A的右树.
下面是王道树上的解释: RR平衡旋转

¶LR平衡旋转(左右双旋)

即在最小平衡树的根节点A的左孩子的右子树上插入导致的不平衡.

序列BL < B < BR < A < AR.发现以A,B为根均无法得到序列相同的平衡二叉树,于是我们思考有没有可能用其它节点做根.BL与AR可能为空不能做根,但
BR则新加入了一个节点必不为空,用新入节点做根也不现实,其大小在BR的范围内,做根的话可能与BR内元素序列的顺序关系冲突.
于是我们想让BR的根节点C作为新的根,这样不管新插入节点是不是BR的唯一元素,也不会产生上面说的冲突.
从BR中将C拆分出来后作为根节点,B、A分别作为其左右孩子,C拆分剩下的CL,CR则分别插入B、A.而新插入节点在CL还是CR则不重要,题目要求再细分即可.
王道书上的另一种角度:
LR恢复-文字版
LR恢复-图例
LR恢复-细分