algorithm - 二分查找和二分查找树的区别？

Question

二分搜索和二叉搜索树有什么区别？

它们是一样的吗？阅读互联网似乎第二个仅适用于树(最多 2 个子节点)并且二进制搜索不遵循此规则。我不太明白。

Answer 1

二叉搜索树

二叉树中的节点是一种数据结构，它具有一个元素和对其他两个二叉树(通常称为左子树和右子树)的引用。即，节点呈现如下界面:

Node:
  element  (an element of some type)
  left     (a binary tree, or NULL)
  right    (a binary tree, or NULL)

二叉搜索树是一棵二叉树(即一个节点，通常称为根)，其左子树和右子树也是二叉搜索树，并且左子树的所有节点都小于根的元素，右子树的所有节点的所有元素都大于根的元素。例如，

     5
    / \
   /   \
  2     8
 / \   / \
1   3 6   9

二分查找

二分搜索是一种在二叉搜索树中查找元素的算法。 (通常表示为搜索有序集合的一种方式，这是一个等价的描述，等价我会在后面描述。)是这样的:

search( element, tree ) {
  if ( tree == NULL ) {
    return NOT_FOUND
  }
  else if ( element == tree.element ) {
    return FOUND_IT
  }
  else if ( element < tree.element ) {
    return search( element, tree.left )
  }
  else {
    return search( element, tree.right )
  }
}

这通常是一种高效的搜索方法，因为在每一步中，您都可以删除一半的搜索空间。当然，如果您的二叉搜索树平衡性很差，它的效率可能会很低(它可能会退化为线性搜索)。例如，它在像这样的树中表现不佳:

3
 \
  4
   \
    5
     \
      6

数组的二分查找

二分查找通常作为排序数组的查找方法出现。这与上面的描述并不矛盾。事实上，它强调了一个事实，即我们实际上并不关心二叉搜索树是如何实现的；我们只关心我们可以获取一个对象并用它做三件事:获取一个元素，获取一个左子对象，并获取一个右子对象(当然，受制于左侧元素的约束小于元素，右边的元素大于等)。

我们可以用一个排序数组做这三件事。对于排序数组，“元素”是数组的中间元素，左子对象是它左边的子数组，右子对象是它右边的子数组。例如，数组

[1 3 4 5 7 8 11]

对应树:

     5
    / \
   /   \
  3     8
 / \   / \
1  4  7   11

因此，我们可以这样写一个数组的二分查找方法:

search( element, array, begin, end ) {
  if ( end <= begin ) {
    return NOT_FOUND
  }
  else { 
    midpoint = begin+(end-begin)/2
    a_element = array[midpoint]
    if ( element == midpoint ) {
      return FOUND_IT
    }
    else if ( element < midpoint ) {
      return search( element, array, begin, midpoint )
    }
    else {
      return search( element, array, midpoint, end )
    }
  }
}

结论

正如经常提到的那样，二分搜索是指此处介绍的基于数组的算法，而二分搜索树是指具有某些属性的基于树的数据结构。但是，二分搜索所需的属性和二分搜索树所具有的属性使同一枚硬币的这两个方面。作为二叉搜索树通常意味着特定的实现，但实际上它是提供特定操作和满足特定约束的问题。二分查找是一种对具有这些操作并满足这些约束的数据结构起作用的算法。