二叉搜索树的搜索次数 [英] Search times for binary search tree

问题描述

有谁知道如何计算二叉搜索树的搜索时间(即最坏情况、最好情况和平均情况)?

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

推荐答案

对于非自平衡树(对于搜索树来说可能但不常见)，最坏情况是 O(n)，即退化二叉树(一个链表).

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.

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

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

在这个完美平衡的树中，您可以看到每个 n 层都有 2ⁿ-1 个节点.这意味着对于 15 个节点，你永远不必搜索超过四个节点来找到它(例如，要找到 13，你搜索 8、12>、14 和 13).这就是 log₂n 数字的来源.

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

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

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屋！