二叉排序树查找不成功的平均查找长度 在看二叉排序树查找分析时，对“二叉排序树查找不成功的平均查找长度”不是很理解，上网查了一下，稍微小结一下： 假如一棵二叉排序树如下： 
那么查找不成功的平均查找长度是：（2*2+3*3+4*2）/7=21/7 比如说一个数如果比62<x<74,那他应该是在74左接点,但是现在74左接点不存在,所以查找不成功,那么就是查找了2次。 你再查找x>74的接点,他应该是在74右接点上,但是不存在,也是两次。所以由于74左右孩子不存在,查找62<x<74和x>74的总次数是2*2 15的左右孩子不存在，当查找x<15和15<x<30查找的次数是2*3，56右孩子不存在,查找的次数是1*3，而2*3+1*3=3*3。 48左右孩子都不存在，所以查找不成功的次数是4*2。 查找不成功的可能性有7种，即 x<15,15<x<30,30<x<48,48<x<56,56<x<62,62<x<74,x>74。 假设这7种可能性相同的话，不成功时平均查找长度为：（2*2+3*3+4*2）/7=21/7。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/68708.html
