Dutor

AVL是一种二叉搜索树(Binary Search Tree)，被称为平衡树(Balanced Binary Tree)，由Adelsonr Velskii 和Landis 提出并以他们的名字命名。

今天看严蔚敏老太太的数据结构，她老人家是这么描述AVL的：AVL，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子：BF)的绝对值不超过1。看着这么个定义很别扭，总觉得对平衡因子的要求比较弱，也可能是我悟性较弱吧，在这句话上我很是下了一番功夫……如果这样来定义的话，可能会让我更容易理解一些：

1. 根的左子树和右子树的高度差的最大值为1，空树的高度为0。
2. 根的左子树和右子树都是AVL树。