二叉搜索树的搜索时间

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

对于非自平衡树(搜索树可能但不常见),最坏的情况是O(n),它用于简并二叉树(链表).

在这种情况下,您必须在找到所需元素之前平均搜索一半列表.

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

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

由于您很少控制将数据插入树中的顺序,因此通常优选自平衡树,因为虽然它们为每次插入或删除添加了少量时间,但它们大大加快了搜索速度.他们最糟糕的情况比不平衡的树木好得多.

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

在这个完美平衡的树中,您可以看到每个级别都有2 ⁿ -1个节点n.这意味着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).

可能想把这个标记为"作业".这是一个很好的起点: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).