Question

我在网络上，看到过一部德国人制作的叫《平衡》（英文名：Balance）的短片，它在1989年获得奥斯卡最佳短片奖。说的是在空中，悬浮着一个四方的平板，上面站立着5个人，同样的相貌，同样的装束，同样的面无表情。平板的中心是个看不见的支点，为了平衡，5个人必须寻找合适的位置。原本，简单的站在中心就可以了，可是，如同我们一样，他们也好奇于这个世界，想知道下面是什么样子。而随着一个箱子的来临，这种平衡被打破了，箱子带来了音乐，带来了兴奋，也带来了不平衡，带来了分歧和斗争。

平板就是一个世界，当诱惑降临，当人心中的平衡被打破，世界就会混乱，最后留下的只有孤独寂寞失败。这种单调的机械化社会，禁不住诱惑的侵蚀，很容易崩溃。最容易被侵蚀的，恰恰是最空虚的心灵。

图8-7-1《平衡》

尽管这部小短片很精彩，但显然我们课堂上是没时间去观摩的，有兴趣的同学可以自己搜索观看。这里我们主要是讲与平衡这个词相关的数据结构——平衡二叉树。

平衡二叉树（Self-Balancing Binary SearchTree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

有两位俄罗斯数学家G.M. Adelson-Velskii和E.M. Landis在1962年共同发明一种解决平衡二叉树的算法，所以有不少资料中也称这样的平衡二叉树为AVL树。

从平衡二叉树的英文名字，你也可以体会到，它是一种高度平衡的二叉排序树。那什么叫做高度平衡呢？意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor），那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

看图8-7-2，为什么图1是平衡二叉树，而图2却不是呢？这里就是考查我们对平衡二叉树的定义的理解，它的前提首先是一棵二叉排序树，右上图的59比58大，却是58的左子树，这是不符合二叉排序树的定义的。图3不是平衡二叉树的原因就在于，结点58的左子树高度为3，而右子树为空，二者差大于了绝对值1，因此它也不是平衡的。而经过适当的调整后的图4，它就符合了定义，因此它是平衡二叉树。

图8-7-2

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。图8-7-3，当新插入结点37时，距离它最近的平衡因子绝对值超过1的结点是58（即它的左子树高度3减去右子树高度1），所以从58开始以下的子树为最小不平衡子树。

图8-7-3