二进制搜索和二进制搜索树之间的区别？ [英] Difference between binary search and binary search tree?

问题描述

二进制搜索树和二进制搜索树有什么区别？

What is the difference between binary search and binary search tree?

它们相同吗？阅读互联网似乎第二个仅适用于树木（最多2个子节点），并且二进制搜索不遵循此规则。我不太明白。

Are they the same? Reading the internet it seems the second is only for trees (up to 2 children nodes) and binary search doesn't follow this rule. I didn't quite get it.

推荐答案

二叉搜索树

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

Binary Search Trees

A node in a binary tree is a data structure that has an element, and a reference to two other binary trees, typically called the left and right subtrees. I.e., a node presents an interface like this:

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

二叉 search 树是一棵二叉树（即节点，通常称为根），其属性是左右子树也是二叉搜索树，并且所有子元素左子树中的所有节点均小于根元素，而右子树中所有节点的所有元素均大于根元素。例如

A binary search tree is a binary tree (i.e., a node, typically called the root) with the property that the left and right subtrees are also binary search trees, and that all the elements of all the nodes in the left subtree are less than the root's element, and all the elements of all the nodes in the right subtree are greater than the root's element. E.g.,

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

二进制搜索

二进制搜索是一种用于在二进制搜索树中查找元素的算法。 （它通常表示为搜索有序集合的一种方式，这是等效的描述。稍后我将描述其等效性。）就是这样：

Binary Search

Binary search is an algorithm for finding an element in binary search tree. (It's often expressed as a way of searching an ordered collection, and this is an equivalent description. I'll describe the equivalence afterward.) It's this:

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

这通常是一种有效的搜索方法，因为在每个步骤中，您可以删除一半的搜索空间。当然，如果您的二进制搜索树平衡性很差，那么它可能效率很低（它可能会降级为线性搜索）。例如，它在以下树中的性能很差：

This is typically an efficient method of search because at each step, you can remove half the search space. Of course, if you have a poorly balanced binary search tree, it can be inefficient (it can degrade to linear search). For instance, it has poor performance in a tree like:

3
 \
  4
   \
    5
     \
      6

二进制在数组上搜索

二进制搜索通常作为排序数组的搜索方法。这与上面的描述不矛盾。实际上，它突出了一个事实，我们实际上并不关心二进制搜索树的实现方式；我们只是关心我们可以获取一个对象并对其执行三件事：获取一个元素，获取一个左子对象，并获取一个右子对象（当然，要服从对左元素的约束）

Binary Search on Arrays

Binary search is often presented as a search method for sorted arrays. This does not contradict the description above. In fact, it highlights the fact that we don't actually care how a binary search tree is implemented; we just care that we can take an object and do three things with it: get a element, get a left sub-object, and get a right sub-object (subject, of course, to the constraints about the elements in the left being less than the element, and the elements in the right being greater, etc.).

我们可以使用排序的数组来完成所有这三件事。对于排序的数组，元素是数组的中间元素，左侧的子对象是其左侧的子数组，右侧的子对象是其右侧的子数组。例如，数组

We can do all three things with a sorted array. With a sorted array, the "element" is the middle element of the array, the left sub-object is the subarray to the left of it, and the right sub-object is the subarray to the right of it. E.g., the array

[1 3 4 5 7 8 11]

与树对应：

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

因此，我们可以为这样的数组编写二进制搜索方法：

Thus, we can write a binary search method for arrays like this:

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

结论

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

Conclusion

As often presented, binary search refers to the array based algorithm presented here, and binary search tree refers to a tree based data structure with certain properties. However, the properties that binary search requires and the properties that binary search trees have make these two sides of the same coin. Being a binary search tree often implies a particular implementation, but really it's a matter of providing certain operations and satisfying certain constraints. Binary search is an algorithm that functions on data structures that have these operations and meet these constraints.

这篇关于二进制搜索和二进制搜索树之间的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！