什么是平衡二叉树（上）

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

AVL树得名于它的发明者G. M. Adelson-Velsky 和Evgenii Landis，他们在1962年的论文《Analgorithm for the organization of information》中公开了这一数据结构。

（引用自wiki）

二叉搜索树一定程度上可以提高搜索效率，二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。故而当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种树就是平衡二叉树。

平衡二叉树，是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。

从平衡二叉树（Self-BalancingBinary Search Tree 或Height-Balancing BinarySearch Tree）的英文名字来看，它是一种自动平衡或高度平衡的二叉搜索树。

自平衡是指，在对平衡二叉树执行插入或删除节点操作后，可能会导致树中某个节点的平衡因子绝对值超过1，即平衡二叉树变得“不平衡”，为了保持该节点左右子树的平衡，需要做一些必要的操作。

那什么叫做高度平衡呢?

意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。我们将二叉树上结点的左子树高度减去右子树高度的值称为平衡因子BF(BalanceFactor)，那么平衡二叉树上所有结点的平衡因乎只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1 ，则该二叉树就是不平衡的。

①如下图，为什么图1是平衡二叉树，而图2不是？

这里就是考查我们对平衡二叉树的定义的理解，它的前提首先是一颗二叉排序树，图2中结点45比结点40大，却是结点40的左子树，这不符合二叉排序树的定义，更不能是平衡二叉树。

②如下图，为什么图4是平衡二叉树，而图3不是？

首先图3、图4都是二叉排序树，但图3中结点40的左子树高度为3，而右子树为空，二者差大于了绝对值1，因此它是不平衡的。而进行适当的调整后图4，它就符合了定义，因此图4是平衡二叉树。

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

今天带大家初步认识了什么是平衡二叉树，之后会带大家了解平衡二叉树实现原理。

西安盛图科技

高端IT培训第一品牌