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

为了避免树的高度增长过快，降低二叉排序树的性能，我们规定
在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL 树）。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0 或 1。

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

（2）平衡二叉树的插入

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

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

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

1. （编辑：浙我家）

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