在平衡二叉搜索树中搜索

Question

我在读平衡二叉搜索树。我发现了关于在这样的树中搜索的声明：

It is not true that when you are looking for something in a balanced binary search tree with n elements, it can in worst case needed n/2 comparisons.

为什么不是真的？

不是我们看树的右边或左边所以比较应该是n/2吗？

Answer 1

想象一下有 10 个节点的树：1,2,3,4,5..10。如果您要查找 5，需要进行多少次比较？如果你找 10 个怎么样？实际上从来没有 N/2.

Answer 2

最坏的情况是您要搜索的元素是一片叶子（或不包含在树中），然后比较的次数等于树的高度，即 log2(n)。

Answer 3

Balanced Binary Search tree 的搜索最坏情况由其高度决定。它是 O(height) 高度是 log2(n) 因为它是平衡的。

在最坏的情况下，我们要查找的节点位于叶子中或根本不存在，因此我们需要从根遍历树到叶子，即O( lgn) 而不是 O(n/2)

Answer 4

考虑以下 n=7 的平衡二叉树（这实际上是一个完整的二叉搜索树，但我们将其排除在讨论之外，因为完整的二叉搜索树也是一个平衡的二叉搜索树).

          5                    depth 1 (root)
     /----+----\ 
    2           6              depth 2
 /--+--\     /--+--\ 
1       3   4       7          depth 3

对于在这棵树中搜索任何数字，最坏的情况是我们达到树的最大深度（例如，在这种情况下为 3），直到我们终止搜索。在深度 3，我们进行了 3 次比较，因此，在任意深度 l，我们将进行 l 次比较。

现在，对于如上所示的任意大小的完整二叉搜索树，我们可以容纳 1 + 2^(maxDepth-1) 个不同的数字。现在，假设我们有一个完整的二叉搜索树，其中正好有 n（不同的）数字。那么下面成立

n = 1 + 2^(maxDepth-1)  (+)

因此

(+) <=> 2^(maxDepth-1) = n - 1 
    <=> log2(2^(maxDepth - 1)) = log2(n - 1)
    <=> maxDepth - 1 = log2(n - 1)

        => maxDepth = log2(n - 1) + 1

回想一下上面 maxDepth 告诉我们最坏情况下的比较次数，以便我们在完整的二叉树中找到一个数字（或者它是 non-existance）。因此

worst case scenario, n nodes : log2(n-1) + 1

为了研究此搜索的渐近或限制行为，n可以被认为足够大，因此log2(n) ~= log2(n-1) 成立，随后，我们可以说算法的一个非常好的（紧）上限是 O(log2(n))。因此

The time complexity for searching in a complete binary tree, for n nodes, is O(log2(n))

对于non-complete二叉搜索树，与上述类似的推理导致相同的时间复杂度。请注意，对于 non-balanced 搜索树， n 节点的最坏情况是 n 比较。

答案： 从上面可以看出，O(n/2) 不是大小为 n 的二叉搜索树时间复杂度的适当界限；然而 O(log2(n)) 是。（请注意，对于足够大的 n，先验可能是 正确的 界限，但不是非常 good/tight 的界限！）

Answer 5

最好的平衡二叉树是AVL树。我说 "the best" 条件是他们的修改操作是 O(log(n))。如果树是完美平衡的，那么它的高度仍然更小（但不知道在 O(log(n)) 中修改它的方法。

可以证明AVL树的最大高度小于

1.4404 log(n+2) - 0.3277

因此，在 AVL 树中搜索的最坏情况是不成功的搜索，其从根的路径终止于最深的节点。但是根据前面的结果，这条路径不能超过 1.4404 log(n+2) - 0.3277。

并且由于 1.4404 log(n+2) - 0.3277 < n/2，该陈述是错误的（假设 n 足够大）

Answer 6

让我们先看看 BST（二叉搜索树）的属性，它告诉我们..

-- root must be > then left_child 

-- root must be < right child


                  10
                 /  \
               8     12
              / \    /  \ 
             5  9   11   15
            / \          / \
           1   7        14  25

给定树的高度为 3（最长路径 10-14 中的边数）。

假设您查询要在给定的平衡 BST 中搜索 14

          node--  10          14 > 10
                 /  \         go to right sub tree because all nodes  
               8     12       in right sub tree are > 10
              / \    /  \ 
             5  9   11   15    n = 11 total node
            / \          / \
           1   7        14  25  


        node--   12           14 > 12   
                /  \          again go to right sub tree..
              11   15
                   / \        n = 5   
                  14  25   


         node--  15       14 > 15 
                /  \      this time node value is > required value so 
               14  25       goto left sub tree
                           n = 3



             'node --  14       14 == 14 value find
                               n = 1'

从上面的例子我们可以看到，在每次比较问题的大小（节点数）减半时，我们也可以说在每次比较时我们切换到下一级，因此树的高度增加 1 。

因为平衡 BST 的最大高度是 log(N) 在最坏的情况下我们需要去树的叶子因此我们采取 log(N) 步骤来这样做..

因此BST搜索的O是log(N)。

在平衡二叉搜索树中搜索

Searching in a balanced binary search tree

binary-tree

data-structures