[Powered by Google Translate] [二进制搜索] [帕特里克·施密德 - 哈佛大学] [这是CS50。 -  CS50.TV] 

如果我给你的迪士尼人物名称按字母顺序排列的列表 问你找到米老鼠， 你会如何​​去这样做呢？ 一个显而易见的方法将是从开始扫描列表 并检查每一个名字，看它是否是米奇。 但是，当你阅读阿拉丁，爱丽丝，碧浪，等等， 你很快就会意识到，在前面的列表是不是一个好主意。 好吧，也许你应该开始从列表末尾向后工作。 现在你看泰山，史迪仔，白雪公主，等等。 不过，这似乎并不像最好的方式去了解它。 

那么，另一种方式，你可以去这样做的，是尽量缩小 名称的列表，你必须看。 既然你知道，他们是按字母顺序排列， 在中间的列表中，你可以看名字 检查，如果米老鼠这个名字之前或之后。 在第二列中的最后一个名称综观 你会意识到M的米奇在J茉莉， 所以，你会简单地忽略上半年的列表。 然后，你可能会在顶部的最后一列 ，并认为它与长发姑娘开始。 米奇之前，长发姑娘，看起来我们可以忽略的最后一列。 继续搜索策略，你很快就会发现，米奇 是在其它的名称列表中的第一个一半的 终于找到米奇隐藏在梅林和米妮之间。 

你刚才做的基本上是二进制搜索。 正如这个名字所暗示的，它执行它的搜索策略，在一个二进制的问题。 这是什么意思呢？ 那么，给出一个列表排序的项目，二进制搜索算法使得一个二进制的决定 -  左或右，大于或小于，之前或之后的字母顺序 - 在每一个点。 现在，我们有一个名字伴随着本次搜索算法， 让我们来看看另一个例子，但这次的列表排序的数字。 说我们正在为数字144在此列表中的排序号码。 就像以前一样，我们发现在中间的数字 -  在这种情况下是13  - 和看到，如果144是大于或小于13。 因为它是明显大于13，我们可以忽略一切，这是13或更小 只集中在剩下的一半。 因为我们现在有一个偶数留下的物品， 我们简单地选择一个数字，接近中间。 在这种情况下，我们选择55。 我们可以很容易地选择89。 好吧。同样，144是大于55，所以我们去的权利。 幸运的是，在未来的中间数是144， 我们正在寻找的。 因此，为了找到144使用二进制搜索，我们可以找到它的只有3个步骤。 如果我们将使用线性搜索，将采取12个步骤。 事实上，由于这个搜索方法的项目数减半 它的每一步看，会发现它正在寻找的项目 大约在日志列表中的项目的数目。 现在，我们已经看到了2个例子，让我们一起来看看 一个递归函数的伪代码实现二进制搜索。 从顶部开始，我们可以看到，我们必须找到一个函数，它接受4个参数： 键，阵列，最小和最大。 最关键的是我们正在寻找的数字，所以144在前面的例子。 数组是数字列表，我们正在寻找。 min和max是最小和最大位置的指数，其中 我们正在寻找。 因此，当我们开始的时候，min将是零和最大将是最大的索引的数组。 当我们缩小搜索范围，我们将更新的最小值和最大值 的范围内，我们仍然往里看。 

让我们先跳到最有趣的部分。 我们做的第一件事是找到中点， 该指数中间的最小值和最大值的数组，我们还在考虑。 然后我们看一下，中点位置的值的数组 看到，我们正在寻找的数字，如果是小于该键。 如果在该位置上的数目比较少， 那么它意味着关键是大于所有编号，以该位置的左侧的。 因此，我们可以称之为二进制搜索功能， 但这次更新的最小值和最大值参数只读取一半 也就是大于或等于的值，我们刚刚看到的。 在另一方面，如果该键的数目小于在当前阵列中点， 我们想要去的左侧，而忽略所有的数字是更大的。 同样，我们称之为二进制搜索，但这个时间范围内的最小值和最大值更新 以仅包括下半部。 如果阵列中的当前的中点处的值既不是 大于也不小于键，那么它必须是相等的关键。 因此，我们可以简单地返回当前的中点指数，我们就大功告成了。 最后，这里此检查为的情况下，数字 实际上不是在数组中的数字，我们正在寻找。 如果在最大的范围内，我们正在寻找的指数 高于最低要求是越来越少，这意味着我们已经走得太远了。 由于数字输入数组中，我们返回-1 表明，没有被发现。 

您可能已经注意到了这个算法的工作， 的号码列表进行排序。 换句话说，我们只能找到144使用二进制搜索 如果所有的数字都下令从最低到最高。 如果不是这样的情况下，我们将无法排除一半的数字在每个步骤。 因此，我们有2个选择。 要么我们可以采取一个无序的列表，并使用二进制搜索，排序前， 或者我们可以肯定，我们将号码添加到列表中的数字进行排序。 因此，而不是排序的时候，我们要搜索​​， 为什么不排序的列表，在任何时候都保持？ 

同时允许排序的方式，让一个数字列表 一个添加或移动号码从这个名单 是通过使用一种称为二叉搜索树。 二叉搜索树是一种数据结构，有3个属性。 首先，左子树中的任何节点只包含值小于 或等于节点的值。 其次，节点的右子树中包含的值大于 或等于节点的值。 以及最后，无论是左和右子树的所有节点 二叉搜索树。 让我们看一个例子，与我们之前使用的相同的号码。 对于那些你从来没有见过计算机科学树前， 首先，让我告诉你，计算机科学树是向下增长的。 是的，不像你习惯的树木， 计算机科学树的根是在顶部， 和叶子都在底部。 每个小方块被称为一个节点，节点由边缘彼此连接。 因此，这棵树的根是一个节点值的值13， 具有2个孩子的节点的值5和34。 子树是树，形成整个树在第。 

例如，左边的子树的节点3是建立的树由节点0，1和2。 所以，如果我们回到一个二叉搜索树的性质， 我们可以看到，在树中的每个节点符合所有3个属性，即， 左子树仅包含节点的值小于或等于的值; 所有节点的右子树 只包含节点的值大于或等于值; 左，右子树的所有节点也有二叉搜索树。 虽然这棵树看起来不一样，这是一个有效的二叉搜索树 对于同一组的数字。 事实上，有许多可能的方式，你可以创建 从这些数字的一个有效的二叉搜索树。 好吧，让我们回到我们创建的第一个。 所以，我们可以做什么与这些树呢？ 好了，我们可以很简单地找到的最低值和最高值。 可以找到的最小值总是要在左边 直到有没有更多的节点访问。 相反，找到的最大的仅仅只是下山的权利在每个时间。 

查找任何其他数目的最小值或最大值 也很容易。 假设我们正在寻找数89。 我们简单地检查每个节点的值，向左或向右， 根据节点的值是否小于或大于 我们正在寻找的。 所以，从13根，我们可以看到，89， 所以我们去正确的。 然后，我们看到了34节点，我们再次去正确的。 89大于55，所以我们继续去合适。 然后，我们来到了一个节点的值144，和去左边。 你瞧，89是正确的。 

我们可以做的另一件事，是打印出所有进行中序遍历。 中序遍历是指打印任何事物的左子树 随后由打印节点本身 然后印刷一切在右子树。 例如，让我们最喜欢的二叉搜索树 的排序顺序打印出来的数字。 首先，我们在13根的，但我们必须在打印前13打印出 一切都在左子树。 因此，我们转到5。我们仍然有更深入的倒在了树，直到我们找到了最左边的节点， 这是零。 印刷零后，我们回去到1，并打印了这一点。 然后我们去的右子树，也就是2，打印了这一点。 现在，我们已经完成了该子树， 我们可以回去了3个，并把它打印出来。 持续回升，我们打印5和8。 现在，我们已经完成了整个左子树， 我们可以打印出13个，并开始工作的右子树。 我们跳了34，但我们必须在打印前34打印出其左子树。 所以，我们打印出21，然后打印出34，访问右子树。 由于55没有左子树，我们打印出来，并继续其右子树。 144有一个左子树，所以我们打印出89，其次是144， 233，最后最右边的节点。 有你有它，所有的号码都打印出来，以便从最低到最高。 

添加的树是什么，以及相对无痛的。 我们要做的是确保我们按照二叉搜索树性能 然后插入值有空间的地方。 比方说，我们要插入的值是7。 自7是小于13，我们去左边。 但它大于5，所以我们遍历的权利。 由于它是小于8和图8是一个叶节点，我们添加7至8的左子。 瞧！我们已经添加了一个数字，我们的二叉搜索树。 

如果我们可以添加的东西，我们最好是能够删除的东西。 不幸的是，对我们来说，删除是一个有点复杂 -  虽然不大，但只是一点点。 有3种不同的情况下，我们要考虑的 删除元素时，从二叉搜索树。 首先，最简单的情况是，该元素是一个叶节点。 在这种情况下，我们简单地将其删除，并继续与我们的业务。 假设我们要删除我们刚才添加的7。 好了，我们只要找到它，删除它，就是这样。 接下来的情况是，如果节点只有1名儿童。 在这里，我们可以删除该节点，但我们首先必须确保 连接的子树，现在是离开父母双亡的孤儿 节点的父节点，我们只是删除了。 假设我们从我们的树，要删除3。 我们把该节点的子元素，并将它附加到节点的父节点。 在这种情况下，我们现在将1到5。 这没有问题，因为我们知道，根据二叉搜索树的性质， 3的左子树，一切均小于5。 现在，3的子树的照顾，我们可以将其删除。 第三个和最后的情况是最复杂的。 这是我们要删除的节点有2个孩子的情况下。 为了做到这一点，我们首先要找到的节点有一个最大的价值， 交换了两下，然后删除有问题的节点。 请注意，节点，下一个最大的值不能有2个孩子 因为它的左孩子为下一个最大的将是一个更好的人选。 因此，删除一个节点有2个孩子，2个节点交换， 然后删除处理由1 2上述规则。 例如，让我们说，我们要删除的根节点，13。 我们做的第一件事情是，我们发现在树中的下一个最大的价值 其中，在这种情况下，为21。 然后，我们交换的2个节点，13叶和21个中心组节点。 现在，我们可以简单地删除13。 

正如前面提到的，有许多可能的方法来进行有效的二叉搜索树。 不幸的是，对我们来说，有些是比别人差。 例如，会发生什么事时，我们建立了一个二叉搜索树 从排序列表中的号码吗？ 所有的数字都只是添加到右边的每一步。 当我们要搜索​​一个数字， 我们别无选择，只有看的权利，在每一个步骤。 这是不是比在所有的线性搜索。 虽然我们不会掩盖他们在这里，还有其他更复杂的， 数据结构，确保不会发生这种情况。 然而，一个简单的事情可以做，以避免这种情况的是 只是随机洗牌的输入值。 这是极不可能的，一个偶然的机会洗牌的数字列表进行排序。 如果是这样的话，赌场会不会留在企业长久的。 

有你有它。 您现在所了解的二进制搜索和二叉搜索树。 我是帕特里克·施密德，这是CS50。 [CS50.TV] 一个明显的方法是将扫描列表... [哔] 的项目数...是的 [笑] ...发布节点234 ... augh。 >>耶！这是 -