runtime - 二叉搜索树的搜索时间

Question

有谁知道如何计算二叉搜索树的搜索时间（即最坏情况、最佳情况和平均情况）？

Answer 1

对于非自平衡树（对于搜索树可能但不常见），最坏的情况是 O(n)，这是退化二叉树（链表）的情况。

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

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

平均情况介于这两者之间，完全取决于数据:-)

由于您很少能够控制数据插入树的顺序，因此自平衡树通常更可取，因为虽然它们为每次插入或删除增加了少量时间，但它们大大加快了搜索速度。他们最坏的情况比不平衡的树好得多。

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

在这棵完美平衡的树中，您可以看到每个级别都有 2 ^{n -1 个节点。}n这意味着对于 15 个节点，您无需搜索超过四个节点即可找到它（例如，要查找、13您搜索8、12和）。这就是 log ₂ n 数字的来源。1413

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

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)。

Answer 2

可能想将此标记为“作业”。这是一个很好的起点：http ://en.wikipedia.org/wiki/Binary_search_tree

一般来说，平衡二叉搜索树的最坏情况查找为 O(log n)，最佳情况为 O(1)（当所需值是根时）和平均情况为 O(log n)（叶子包含比其父级更多的值）。

最坏的情况是最有趣的，并且很容易通过识别二叉树的第一级有 1 个节点，第二级有 2 个，第三级有 4 个等来看出。因此，深度为n的二叉树中的节点数正好是2^n - 1。指数函数的数学逆是对数，因此：O(log n)。

不平衡的树可能与链表一样糟糕，并且可能具有如下形状：

  1
 / \
    2
   / \
      3
     / \
        4
       / \

在这种情况下，最坏情况的访问时间是O(n)。

Answer 3

最好的情况是 O(1)。第一个元素可能是您要查找的项目。最坏的情况是 O(n)，即在一棵倾斜的树中，平均情况是 O(lg n)。