二进制搜索树的搜索时间 [英] Search times for binary search tree

问题描述

有人知道如何找出二叉搜索树的搜索时间(即最坏情况，最佳情况和平均情况)吗?

解决方案

对于非自平衡树(可能，但对于搜索树而言不常见)，最坏的情况是O(n)，它是退化的二叉树(链接列表).

在这种情况下，您必须平均搜索列表的一半，然后才能找到所需的元素.

对于完美平衡的树，最好的情况是O(log ₂ n)，因为您将每个树级别的搜索空间减少了一半.

平均大小写介于两者之间，并且完全取决于数据:-)

由于很少能控制将数据插入树的顺序，因此通常最好使用自平衡树，因为它们会为每次插入或删除增加少量时间，但会大大加快搜索速度.他们最坏的情况比不平衡的树木好得多.

                 8
         _______/ \_______
        /                 \
       4                  12
    __/ \__             __/ \__
   /       \           /       \
  2         6        10        14
 / \       / \       / \       / \
1   3     5   7     9  11    13  15

在这棵完美平衡的树中，您可以看到每个n级别得到2 ⁿ -1个节点.这意味着对于15个节点，您不必搜索四个以上的节点即可找到它(例如，要找到13，搜索8，12，14和13).这就是log ₂ n数字的来源.

如前所述，退化的不平衡树是一个链表.如果您的数据是按顺序到达的，并且将其插入到不平衡的二叉树中，则会得到:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
                                           |
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15

要在这种情况下查找13，您需要搜索1，2，3，4，5，6，7，8， 9，10，11，12和13，因此为O(n).

Does anyone know how to figure out search time for a binary search tree(i.e. worst-case, best-case, and average-case)?

解决方案

For 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(log₂ 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.

                 8
         _______/ \_______
        /                 \
       4                  12
    __/ \__             __/ \__
   /       \           /       \
  2         6        10        14
 / \       / \       / \       / \
1   3     5   7     9  11    13  15

In this perfectly balanced tree, you can see that you get 2ⁿ-1 nodes for every n levels. That means for 15 nodes, you never have to search more than four nodes to find it (e.g., to find 13, you search 8, 12, 14 and 13). That's where the log₂n 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:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
                                           |
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15

To find 13 in that case, you'd need to search 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 and 13, hence O(n).

这篇关于二进制搜索树的搜索时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！