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

平衡二叉树（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）平衡调整算法：修改相关结点的指针。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!