平衡二叉树 构造方法(绝妙)

平衡二叉树 构造方法 平衡二叉树平衡二叉树 对于二叉查找树 尽管查找 插入及删除操作的平均运行时间为 O logn 但是它们的最 差运行时间都是 O n 原因在于对树的形状没有限制 平衡二叉树又称为 AVL 树 它或者是一棵空树 或者是有下列性质的二叉树 它的左子树 和右子树都是平衡二叉树 且左右子树的深度之差的绝对值不超过 1 二叉树的的平衡因 子 BF 为 该结点的左子树的深度减去它的右子树的深度该结点的左子树的深度减去它的右子树的深度 则平衡二叉树的所有结点的平 衡因子为只可能是 1 0 和 1 一棵好的平衡二叉树的特征 1 保证有 n 个结点的树的高度为 O logn 2 容易维护 也就是说 在做数据项的插入或删除操作时 为平衡树所做的一些辅助 操作时间开销为 O 1 一 平衡二叉树的构造 在一棵二叉查找树中插入结点后 调整其为平衡二叉树 若向平衡二叉树中插入一个新结 点后破坏了平衡二叉树的平衡性 首先要找出插入新结点后失去平衡的最小子树根结点的 指针 然后再调整这个子树中有关结点之间的链接关系 使之成为新的平衡子树 当失去 平衡的最小子树被调整为平衡子树后 原有其他所有不平衡子树无需调整 整个二叉排序 树就又成为一棵平衡二叉树 1 调整方法 1 插入点位置必须满足二叉查找树的性质 即任意一棵子树的左结点都小于根结点 右结点大于根结点 2 找出插入结点后不平衡的最小二叉树不平衡的最小二叉树 进行调整 如果是整个树不平衡 才进行整个 树的调整 2 调整方式 1 LL 型 LL 型 插入位置为左子树的左结点 进行向右旋转为左子树的左结点 进行向右旋转 由于在 A 的左孩子 B 的左子树上插入结点 F 使使 A 的平衡因子由 1 变为 2 成为不平衡的成为不平衡的 最小二叉树根结点最小二叉树根结点 此时 A 结点顺时针右旋转 旋转过程中遵循 旋转优先 的规则 A 结 点替换 D 结点成为 B 结点的右子树 D 结点成为 A 结点的左孩子 2 RR 型 RR 型 插入位置为右子树的右孩子 进行向左旋转为右子树的右孩子 进行向左旋转 由于在 A 的右子树 C 的右子树插入了结点 F A 的平衡因子由 1 变为 2 成为不平衡的最 小二叉树根结点 此时 A 结点逆时针左旋转 遵循 旋转优先 的规则 A 结点替换 D 结 点成为 C 的左子树 D 结点成为 A 的右子树 3 LR 型 LR 型 插入位置为左子树的右孩子 要进行两次旋转 先左旋转 再右旋转 第一次最小左子树的右孩子 要进行两次旋转 先左旋转 再右旋转 第一次最小 不平衡子树的根结点先不动 调整插入结点所在的子树 第二次再调整最小不平衡子树 不平衡子树的根结点先不动 调整插入结点所在的子树 第二次再调整最小不平衡子树 由于在 A 的左子树 B 的右子树上插入了结点 F A 的平衡因子由 1 变为了 2 成为不平衡 的最小二叉树根结点 第一次旋转 A 结点不动 先将先将 B 的右子树的根结点的右子树的根结点 D 向左上旋转向左上旋转 提升到提升到 B 结点的位置结点的位置 然后再把该然后再把该 D 结点向右上旋转提升到结点向右上旋转