程序员复习：二叉排序树和二分查找的比较 2013年上半年软考指定教材 2013下半年软考培训：在线辅导 面授班 23、二叉排序树（BST, Binary SortTree） 的C++实现 （3）在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关： ①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是（n+1）/2. ②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn. ③插入、删除和查找算法的时间复杂度均为O（lgn）。 （4）二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的查找和二分查找差不多。 就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O（lgn），因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O（n）。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。 //二叉查找树代码 //BTreeNode.h二叉树结点抽象类型 返回目录：软考程序员专用复习资料 编辑推荐：2013年软考程序员理论知识汇总 2013年软考程序员常考知识点锦集
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/83333.html
