【数据结构】4. 树与二叉树

因此，平衡二叉树可定义为它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
如图 4-24(a) 所示是平衡二叉树，图 4-24(b) 所示是不平衡的二叉树。
结点中的值为该结点的平衡因子。

（2）平衡二叉树的插入

二叉排序树保证平衡的基本思想：每当在二叉排序树中插入（或删除）一个结点时，首先要检査其插入路径上的结点是否因为此次操作而导致了不平衡。
如果导致了不平衡. 则先找到插入路径上离插入结点最近的平衡因子绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意：
每次调整的对象都是最小不平衡子树，即在插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。如图 4-25 所示虚线框内为最小不平衡子树。

平衡二叉树的插入过程前半部分与二叉排序树相同，但是在新结点插入后，如果造成了査找路径上某个结点不再平衡，需要做出相应的调整。
一般可将失去平衡后进行调整的规律归纳为下列 4 种情况：

1. （编辑：ASP站长）

   【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。