hosteons中文网

上一节介绍如何使用二叉排序树实现动态查找表，本节介绍另外一种实现方式——平衡二叉树。

平衡二叉树，又称为 AVL 树。实际上就是遵循以下两个特点的二叉树：

• 每棵子树中的左子树和右子树的深度差不能超过 1；
• 二叉树中每棵子树都要求是平衡二叉树；

其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。

图 1 平衡与不平衡的二叉树及结点的平衡因子