二分搜索和二叉搜索树之间的区别？

Question

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

它们是一样的吗？阅读互联网似乎第二个仅适用于树(最多2个子节点),二分搜索不遵循此规则.我没理得.

Answer 1

二叉搜索树

二叉树中的节点是具有元素的数据结构,以及对两个其他二叉树的引用,通常称为左子树和右子树.即,节点呈现如下界面:

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

二叉搜索树是二叉树(即,通常称为根的节点),其具有左右子树也是二叉搜索树的属性,并且左子树中的所有节点的所有元素都小于root的元素,右子树中所有节点的所有元素都大于root的元素.例如,

     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

数组二进制搜索

二进制搜索通常表示为已排序数组的搜索方法.这与上面的描述不矛盾.事实上,它突出了我们实际上并不关心如何实现二叉搜索树的事实; 我们只关心我们可以拿一个对象并用它做三件事:获取一个元素,获得一个左子对象,并获得一个正确的子对象(当然,主题是关于左边元素的约束小于元素,右边的元素更大,等等.

我们可以使用排序数组完成所有这三件事.对于排序数组,"element"是数组的中间元素,左侧子对象是其左侧的子数组,右侧子对象是其右侧的子数组.例如,阵列

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

结论

如通常所示,二进制搜索是指这里给出的基于阵列的算法,二叉搜索树是指具有某些属性的基于树的数据结构.但是,二进制搜索所需的属性和二进制搜索树所具有的属性使这两个方面成为同一个硬币.作为二叉搜索树通常意味着特定的实现,但实际上它是提供某些操作并满足某些约束的问题.二进制搜索是一种算法,它在具有这些操作并满足这些约束的数据结构上起作用.

Answer 2

不,他们不一样.

二叉搜索树:

• 树数据结构
• 每个节点最多有2个孩子
• 节点的左子树仅包含键小于节点键的节点
• 节点的右子树仅包含键大于节点键的节点

二进制搜索:

• 一种算法,用于排序数据结构(通常但不一定是数组),并在每一步中查看中间的值并递归到左侧或右侧,具体取决于目标值是否更小或大于中间的值(如果相等则停止).

当然,数据结构是:

一种在计算机中存储和组织数据的特定方式,以便可以有效地使用它.

虽然算法是:

计算的分步过程.

二叉搜索树中的搜索过程(我们在树中查找特定值)可以被认为类似于(或者是一个实例,取决于您的定义以及您是否使用平衡BST)二进制搜索,因为这也会查看'middle'元素并向左或向右递归,具体取决于该值与目标值之间的比较结果.

Answer 3

对于那些来这里快速检查使用哪个的人。除了上面发布的答案之外，我还想增加这两种技术操作的复杂性。

二叉搜索树：

搜索：？（的log（n）） ，最坏情况（O（n））的用于不平衡BST，

插入节点：？（的log（n）） ，最坏情况（O（N））的不平衡BST

删除节点：?(log(n)) , ,不平衡 BST 的最坏情况(O(n))

平衡二叉搜索树：

搜索: 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)将较大的数组项移动到相邻的左侧）

所以根据您的需求，您可以选择是否需要快速插入和删除。如果您不需要这些，那么将内容保存在排序数组中对您有用，因为与树相比，数组占用的内存更少