二分查找和二叉搜索树之间的区别是什么？

Question

二分查找和二叉搜索树之间的区别是什么？

algorithmdata-structuresbinary-search-treebinary-search

39

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

它们是相同的吗？阅读互联网上的内容，似乎后者仅针对树（最多有两个子节点），而二分搜索没有遵循这个规则。我理解不够深刻。

- RollRoll

5

二分查找是一种算法，二叉搜索树是一种数据结构。请参见二叉搜索树和二分查找算法。 - Ken White

1

@KenWhite 我同意你对差异的评论；不过，我认为值得指出的是，当你在某个东西上执行二分查找时，你_隐含地_将该东西视为二叉搜索树。也就是说，这种差异在很大程度上是接口的差异。 - Joshua Taylor

4个回答

16

不，它们不一样。

二叉搜索树:

一种树形数据结构
每个节点最多有两个子节点
节点的左子树只包含键值小于该节点的键值的节点
节点的右子树只包含键值大于该节点的键值的节点

二分查找:

在已排序的数据结构上（通常是数组），每次查看中间的值并根据目标值是比中间值小还是大来递归到左侧或右侧（如果相等则停止）的算法。

当然，数据结构就是:

一种特定的方式，在计算机中存储和组织数据，以便可以高效地使用。

当一个算法是:

一种用于计算的逐步过程。

在二叉搜索树中进行搜索（即查找树中特定值）的过程可以类比于（或者根据您的定义和是否使用平衡BST而视为）二分查找，因为它也查看“中间”元素，并根据该值与目标值之间的比较结果向左或向右递归。

- Bernhard Barker

1

二分查找是一种算法，但请注意，您可以轻松地将其表述为在二叉树上运行的算法：“一种在二叉搜索树上工作的算法，在每个步骤中查看根处的值并根据目标值是小于还是大于根处的值而递归到左侧或右侧，或者在相等时停止。”因此，二叉搜索树实际上只是某些数据的一种“接口”或“表示”。排序数组可以被呈现为二叉搜索树： “根处的值”只是中间元素的… - Joshua Taylor

1

在数组中，左子树是根节点左侧的子数组，右子树是根节点右侧的子数组。 - Joshua Taylor

@JoshuaTaylor 你评论的第一部分正是我在最后一段所试图表达的。 - Bernhard Barker

10

对于那些想要快速检查哪个技术更适合使用的人来说，除了上面提供的答案外，我想补充一下这两种技术的操作复杂度。

二叉搜索树：

搜索：θ(log(n))，最坏情况下为O(n)，对于不平衡的BST；

插入节点：θ(log(n))，最坏情况下为O(n)，对于不平衡的BST；

删除节点：θ(log(n))，最坏情况下为O(n)，对于不平衡的BST。

平衡二叉搜索树：

搜索：log(n)；

插入节点：O(log(n))；

删除节点：O(log(n))。

基于排序数组的二分查找：

搜索：O(log(n))。但是，

插入节点：如果数组是静态分配并且已经满了，则无法插入。否则，O(n)（将数组中较大的项移动到它们右侧相邻的位置需要O(n)）。

删除节点：O(log(n)) + O(n)。（因此，找到删除位置为O(log(n)) + 将数组中较大的项移动到它们左侧相邻的位置所需的O(n)）。

因此，根据您的要求，您可以选择是否需要快速插入和删除。如果不需要这些操作，那么将元素保持在排序数组中会比维护树结构需要更少的内存。

- Alok Nayak

请为BST添加：log n，假设树是平衡的。 - Israel

为什么在查找删除位置时，log(n) + O(n)（O(log(n))）是如何计算出来的？ - shareef

我已经重新格式化了答案。为了找到值的删除位置，可以在这个排序数组上进行二分查找，复杂度将是O(log(n))。 - Alok Nayak

0

使用二分查找搜索元素时，元素应该在顺序内存位置中表示，例如使用数组，需要知道数组的大小才能找到中间元素。而使用二叉搜索树进行搜索时，数据不必在连续位置上，我们需要将元素添加到BST节点中，每个BST节点包含其右侧和左侧的子节点，因此只需知道根节点就足以在树上进行搜索。
由于使用数组进行二分查找，插入和删除操作会很容易，但在BST中，即使在最坏情况下，我们也需要遍历整个树的高度。
要进行二分查找，我们需要元素按排序顺序排列，但BST不遵循此规则。
现在来看搜索时间复杂度：

a）使用二分查找，最坏情况下的复杂度为O(logn)

b）使用BST，最坏情况下的复杂度为O(n)，即如果树是倾斜的，则它就像一个链表一样工作，我们最终会搜索所有元素（这就是为什么我们需要实现平衡BSTs）。
二分查找需要O(1)的空间复杂度，因为位置是连续的，而BST需要O(n)的空间，因为每个节点我们需要额外的空间来存储其子节点的指针。

- sushmitha

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joshua Taylor · Accepted Answer

二叉搜索树

二叉树中的一个节点是一种数据结构，它包含一个元素和对其他两个二叉树的引用，通常称为左子树和右子树。即，一个节点提供了以下接口：

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

这通常是一种有效的搜索方法，因为每一步都可以将搜索空间缩小一半。当然，如果您拥有一个平衡不良的二叉搜索树，它可能效率低下（可能会退化成线性搜索）。例如，在类似下面这样的树中，它的性能很差：

数组的二分查找

二分查找通常被描述为对于有序数组的一种搜索方法。这并不与上面的描述相矛盾，实际上强调了一个事实，即我们并不关心二分查找树是如何实现的；我们只需要知道我们可以对一个对象进行三个操作：获取元素、获取左子对象和获取右子对象（当然，要满足左边的元素小于该元素，右边的元素大于该元素等约束条件）。

我们可以用排序后的数组来完成这三件事情。对于排序后的数组，"元素"就是数组的中间元素，左子对象是它左边的子数组，右子对象是它右边的子数组。例如，下面的数组：

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

结论

通常所说的二分查找是指这里介绍的基于数组的算法，而二叉搜索树是指具有特定属性的基于树的数据结构。然而，二分查找要求的属性和二叉搜索树具有的属性使得它们两个是同一个硬币的不同面。成为二叉搜索树通常意味着一种特定的实现方式，但实际上它只涉及到提供某些操作和满足某些约束条件。二分查找是一个作用于具有这些操作和满足这些约束条件的数据结构上的算法。