在算法中，4 th Robert Sedgewick的Edition，不同算法的时间复杂表的表现为：
基于此表，bST的搜索时间复杂性为n，并且本身的二进制搜索是logn。
两者有什么区别？我已经看到了对这些的解释，但它们是有道理的，但是，我似乎不明白为什么bst的搜索时间复杂性不是logn，因为我们通过不断将树折断并忽略其他部分来搜索。
In Algorithms, 4th edition by Robert Sedgewick, the time complexity table for different algorithms is given as:
Based on this table, the searching time complexity of a BST is N, and of binary search in and of itself is logN.
What is the difference between the two? I have seen explanations about these separately and they made sense, however, I can't seem to understand why the searching time complexity of a BST isn't logN, as we are searching by continually breaking the tree in half and ignoring the other parts.
发布评论
评论（2）
来自
因此，您有点期望log（n），但不能绝对保证。
From binary-search-trees-bst-explained-with-examples
So, you kind of expect log(N) but it's not absolutely guaranteed.
区别在于，排序阵列上的二进制搜索始终始于中间元素（即 n 是奇数时的中间）。这不能在BST中保证。 root 可能是中间元素，但不必是。
例如，这是一个有效的BST：
...但是它不是一个平衡的BST，因此在鉴于该树根的根部找到值1的过程将包括访问其节点 all 。但是，如果在排序列表中显示相同的值（
1,2,5,8,10），则二进制搜索将从5开始，从不访问8或10。平衡树与表平衡
我们可以使用自我平衡搜索树（如AVL）扩展给定表，然后我们得到：
The difference is that a binary search on a sorted array always starts at the middle element (i.e. the median when n is odd). This cannot be guaranteed in a BST. The root might be the middle element, but it doesn't have to be.
For instance, this is a valid BST:
...but it is not a balanced one, and so the process of finding the value 1 given the root of that tree, will include visiting all its nodes. If however the same values were presented in a sorted list (
1,2,5,8,10), a binary search would start at 5 and never visit 8 or 10.Adding self-balancing trees to the table
We can extend the given table with self-balancing search trees, like AVL, and then we get this: