二叉查找(搜索)树的时间复杂度是什么?

二叉查找(搜索)树的时间复杂度是什么?
二叉排序树的性能分析

二叉查找树中查找的运行时间与树T的高度成正比。因为有n个结点的树的高度小则为O(logn),大则为O(n).;

对于有n个关键字元素的数据项,高度为h的二叉查找树T,空间复杂度为O(n);其中,查找元素,插入元素,删除元素的时间复杂度均为O(h);

二叉排序树的查找过程与二分法相似,也是一个逐步缩小查找范围的过程。若查找成功,则走了一条从根结点到待查结点的路径;若失败,则是走了一条根结点到某个叶子结点的路径。因而,查找过程中和关键字的比较次数不超过树的深度。

由于含有n个结点的二叉排序树不唯一,因而有n个结点的二叉排序树的平均查找长度为树的形态有关;

最好的情况:二叉排序树和二叉判定树形态相同;

最坏的情况:二叉排序树为单支树,这时平均查找长度与顺序查找时相同;

就平均性能而言,二叉排序树上的查找与二分查找相差不大,且二叉排序树上的插入和删除结点十分方便,不用大量移动结点。

发表评论

您的电子邮箱地址不会被公开。