二叉排序树查找性能分析

1. 一棵二叉查找树的平均查找长度（ASL），见下图公式（1）。2. 一棵满二叉排序树的平均查找长度，见下图公式（2）。

3. 一棵斜二叉排序树的平均查找长度，见下图公式（3）。

?

? ? ? ? ? 由上面可以分析得知，对于二叉排序查找性能，最坏是斜树情况下的查找，最好的在一棵满树状态下查找。也就是说性能在公式（2）和公式（3）计算的值之间。当然一实际中，一般很少是满树，因此，在构造二叉排序树时，要尽量生成平衡树。