二叉搜索树

二叉树中的节点是一种数据结构，它具有一个元素，以及对另外两个二叉树的引用，通常称为左子树和右子树。即，一个节点提供了这样的接口：

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

结论

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