[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。
>>耶！这是 -