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

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

二叉排序树查找性能分析

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

3. 一棵斜二叉排序树的平均查找长度,见下图公式(3)。

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

?

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

关于作者: dawei

【声明】:石家庄站长网内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

为您推荐