平衡二叉树算法详细解释
5星 · 超过95%的资源 需积分: 17 4 浏览量
2010-05-15
19:50:42
上传
评论 2
收藏 120KB DOC 举报 
平衡二叉树
形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ，其严格定义是：
一棵空树是平衡二叉树；若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl
和 hr 分别为左、右子树的深度。当且仅当
① TL 、 TR 都是平衡二叉树；
② ｜ hl － hr ｜≤ 1；
时，则 T 是平衡二叉树。
【例】如图 8.4 所示。
（a）平衡二叉树:::::::::::（b）非平衡二叉树
图 8.3 平衡二叉树与非平衡二叉树
相应地定义 hl － hr 为二叉平衡树的平衡因子 (balance factor) 。因此，平衡二叉树上所有结
点的平衡因子可能是 -1 ， 0 ， 1 。换言之，若一棵二叉树上任一结点的平衡因子的绝对值
都不大于 1 ，则该树是就平衡二叉树。
动态平衡技术
1.动态平衡技术
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：
在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树
的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持
排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。
通常将这样得到的平衡二叉排序树简称为 AVL 树。
2.最小不平衡子树
以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论，
不妨假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规律可归纳为下列
四种情况：
（1） LL 型：
新结点 X 插在 A 的左孩子的左子树里。调整方法见图 8.5(a) 。图中以 B 为轴心，将 A
结点从 B 的右上方转到 B 的右下侧，使 A 成为 B 的右孩子。
剩余12页未读，继续阅读
评论13
最新资源