C# · 12月 20, 2021

数据结构知识整理 – 平衡二叉树

平衡二叉树(Balanced Binary Tree)

平衡二叉树是由一般的二叉排序树经过平衡调整得到的,每个结点的左右子树深度差小于等于1的特殊的二叉排序树。

已经提到,二叉排序树的平均查找长度与它的形态有关,其中平衡二叉树就是一种最好的形态。

特征:

1)左右子树深度差的绝对值小于等于1;

2)左右子树也是平衡二叉树。(递归)

为了表示左右子树的深度差,我们给每个结点增加一个属性——平衡因子(Balance Factor),记录每个结点左右子树的深度差,结点值 = 左子树深度 – 右子树深度。只要有一个结点的平衡因子的绝对值大于1,这棵二叉排序树就是不平衡的。

当平衡的二叉排序树因插入结点而失去平衡时,仅需对最小不平衡子树进行平衡调整即可,即 以 离插入结点最近的,结点平衡因子等于2或-2的结点 为根结点的 子树。

插入结点的情况分为四种,相应地,平衡调整的方法也分为四种:

(根结点只表示一个位置,其余颜色代表具体的结点)

1)在根结点的左子树根结点的左子树上插入结点(LL型):

左子树根结点的左子树相当于树的“外层”,对此情况只需要将根结点左移(不违反二叉排序树的特征),即以左子树根结点作为新的根结点。但是左子树根结点上可能存在右子树,如果只是简单地将根结点左移,可能会出现三叉树的情况。所以我们将左子树根结点上的右子树挂接到原来的根结点上。

2)在根结点的右子树根结点的右子树上插入结点(RR型):

这种情况与LL型的平衡调整对称。

3)在根结点的左子树根结点的右子树上插入结点(LR型):

左子树根结点的右子树相当于树的“内层”,对此情况需要新增一个操作结点,即根结点的左子树根结点的右子树根结点。

由于根结点左移并不能改变左右子树的深度差,所以我们应该设法将插入结点“抬上去”。

具体操作是将右子树根结点变成新的根结点。

若右子树根结点存在左子树(LRL型),则将其左子树挂接到左子树根结点上;若右子树根结点存在右子树(LRR型),则将其右子树挂接到根结点上。

4)在根结点的右子树根结点的左子树上插入结点(RL型):

这种情况与LL型的平衡调整对称。

新增一个操作结点——根结点的右子树根结点的左子树根结点,并将左子树根结点变成新的根结点。

若左子树根结点存在左子树(RLL型),则将其左子树挂接到根结点上;若左子树根结点存在右子树(RLR型),则将其右子树挂接到右子树根结点上。

(回顾二叉排序树算法)

1)插入算法:在二叉排序树上插入新结点;

2)查找算法:判断插入结点的情况;

3)平衡调整算法:修改相关结点的指针。