《数据结构》二叉排序树查找性能总结

发布时间：2021-04-02 00:31 所属栏目：53 来源：网络整理

导读：二叉排序树查找性能分析 1. 一棵二叉查找树的平均查找长度（ASL），见下图公式（1）。2. 一棵满二叉排序树的平均查找长度，见下图公式（2）。 3. 一棵斜二叉排序树的平均查找长度，见下图公式（3）。 ? ? ? ? ? ? 由上面可以分析得知，对于二叉排序查找性能

二叉排序树查找性能分析

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

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

《数据结构》二叉排序树查找性能总结

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

（编辑：ASP站长网）