二叉搜索树的搜索时间
有谁知道如何计算二叉搜索树的搜索时间（即最坏情况、最佳情况和平均情况）？
Does anyone know how to figure out search time for a binary search tree(i.e. worst-case, best-case, and average-case)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于非自平衡树（可能但对于搜索树来说不常见），最坏情况是 O(n)，这适用于退化二叉树（链表）。
在这种情况下，您平均必须搜索一半的列表才能找到所需的元素。
完美平衡树的最佳情况是 O(log2 n)，因为您将每个树级别的搜索空间减半。
平均情况介于两者之间，完全取决于数据:-)
由于您很少能够控制将数据插入树中的顺序，因此自平衡树通常更可取，因为它们会添加少量的每次插入或删除的时间，它们大大加快了搜索速度。 它们最坏的情况比不平衡的树要好得多。
在这个完美平衡的树中，您可以看到每
n层都有 2n-1 个节点。 这意味着对于 15 个节点，您无需搜索超过 4 个节点即可找到它（例如，要查找13，您可以搜索8、12、14和13）。 这就是 log2n 数字的来源。正如已经说过的，退化的不平衡树是一个链表。 如果您的数据按顺序到达并将其插入不平衡二叉树中，您将得到：
在这种情况下要查找
13，您需要搜索1，2、3、4、5、6、7< /code>、，因此 O(n)。8、9、10、11、12和 <代码>13For a non-self-balancing tree (possible but unusual for a search tree), worst case is O(n), which is for the degenerate binary tree (a linked list).
In this case, you have to search, on average, half the list before finding your desired element.
Best case is O(log2 n) for a perfectly balanced tree, since you cut the search space in half for every tree level.
Average case is somewhere in between those two and depends entirely on the data :-)
Since you rarely get to control the sequence in which data is inserted into a tree, self-balancing trees are usually preferable since, while they add a small amount of time to each insertion or deletion, they greatly speed up searching. Their worst case is so much better than unbalanced trees.
In this perfectly balanced tree, you can see that you get 2n-1 nodes for every
nlevels. That means for 15 nodes, you never have to search more than four nodes to find it (e.g., to find13, you search8,12,14and13). That's where the log2n figure comes from.A degenerate unbalanced tree, as already stated, is a linked list. If your data arrived in sequence and you inserted it into an unbalanced binary tree, you'd get:
To find
13in that case, you'd need to search1,2,3,4,5,6,7,8,9,10,11,12and13, hence O(n).可能想将其标记为“作业”。 这是一个很好的起点：http://en.wikipedia.org/wiki/Binary_search_tree
，平衡二叉搜索树的最坏情况查找为 O(log n)，最好情况为 O(1)（当所需值为根时），平均情况为 O(log n) n) （叶子包含的值比它们的父辈多得多）。
最坏的情况是最有趣的，通过认识到二叉树的第一层有 1 个节点，第二层有 2 个节点，第三层有 4 个节点，依此类推，很容易看出最坏的情况。 因此，深度n的二叉树中的节点数恰好是2^n - 1。 指数函数的数学反函数是对数，因此：O(log n)。
不平衡树可能与链表一样糟糕，并且可能具有如下形状：
在这种情况下，最坏情况的访问时间是O(n)。
Might want to tag this one as "homework". Here's a good starting point: http://en.wikipedia.org/wiki/Binary_search_tree
In general, a balanced binary search tree has a worst-case lookup of O(log n), best case of O(1) (when the desired value is the root) and an average case of O(log n) (the leaves contain exponentially more values than their parents).
The worst case is the most interesting and is easily seen by recognizing that the first level of a binary tree has 1 node, the second has 2, the third has 4 and so on. Thus, the number of nodes in a binary tree of depth n is precisely 2^n - 1. The mathematical inverse of the exponential function is the logarithm, thus: O(log n).
An unbalanced tree can be as bad as a linked list and may have a shape like the following:
In this situation, the worst-case access time is O(n).
最好的情况是 O(1)。 第一个元素可能是您正在寻找的项目。 最坏情况是 O(n)，即在倾斜树中，平均情况是 O(lg n)。
Best case is O(1). the first element could be the item you are looking for. worst case is O(n) ie in a skewed tree and average case is O(lg n).