>> [音乐播放]
道格·劳埃德：所以我们一直在缓慢接近 而接近该数据的圣杯
结构，一个我们可以插入 成，删除，并查找
在固定的时间。
对。
这是排序的目标。
我们希望能够做 事情非常，非常快。
>> 难道我们发现这里的时候， 我们谈论的尝试？
好吧，让我们一起来看看。
因此，我们已经看到一些 不同的数据结构
该处理的映射 所谓键 - 值对，
一些映射数据块 其他一些数据片段
所以我们知道在哪里可以找到 在结构信息。
>> 因此对于阵列，例如，该 关键是该元素索引或阵列
位置0或阵列1等。
和的值是数据 存在在该位置。
那么，什么是存储在阵列0？
什么是存储在阵列1与刚 0和1，这将是键。
>> 利用哈希表是 排序相同的想法。
利用哈希表，我们有这个哈希 函数生成散列码。
所以关键是数据的哈希码。
和的值，特别是 我们谈到链接
在哈希表的视频， 是数据的链表
该散列到哈希码。
对。
那么另一种方法 这种方法有关系吗？
怎么样的方法，其中 键被保证是唯一的，
哈希表，在那里我们可以不像 结了两段数据
具有相同的哈希码。
然后，我们必须处理 通过两种探测以上
最好链接来解决这个问题。
>> 所以，现在我们可以保证 我们的重点将是独一无二的。
如果我们的价值是什么 只是一些容易
作为真假，它告诉我们，无论是 不能说资料片
在结构上存在？
布尔可能是简单的一个位。
现实情况可能是一个 字节不是位的可能性较大。
但是，这是一个很大小于 存储可能是50个字符的字符串，
例如。
>> 所以尝试，类似于哈希表， 其中结合阵列和链表，
尝试结合阵列， 结构，和指针
一起将数据存储在 一个有趣的方式，是
从相当不同 什么我们到目前为止看到的。
现在我们用数据作为路线图 导航这个数据结构。
如果我们可以按照 路线图，如果我们能
按照从数据 自始至终，我们将
知道是该数据 存在于线索。
>> 如果我们不能按照地图 从意味着结束可言，
数据不能存在。
再次，键这里是 保证是唯一的。
所以一个哈希表不同的是，我们永远不会 必须处理的冲突在这里。
并没有两段数据 有完全相同的路线图
除非该数据是相同的。
>> 如果我们插入约翰的话 我们寻找约翰。
这是两个相同的块 数据吧，我们期待通过。
但除此之外，任何 两个数据是
保证有独特的路线图 通过这个数据结构。
而且我们要看看 一会儿就好了一个视觉这一点。
>> 我们将通过努力做到这一点 创建一个新的数据结构，
映射以下键值对。
在这种情况下，我们不打算使用 一些简单的布尔。
实际上，我们将存储字符串。
而该字符串是要 是一所大学的名字。
>> 关键是要在今年 当大学成立。
所有年大学 将要四位数字。
因此，我们将使用这四个数字来 导航通过这个数据结构。
而且我们可以看到，同样，如何 我们这样做，在短短一秒钟。
>> 在路径的末端， 我们将看到名称
对应的大学 到那个键，这四个数字。
后面一个线索的基本思想 就是我们有一个中央的路线。
所以，想想它像一棵树。
这是拼写相似 并在概念上树。
通常，当我们想到 树木在现实世界中，
他们有一个根目录是在 地面和他们向上生长
他们有分支机构 并且他们有叶。
与基本思路 一线索是完全一样的，
除了根锚定 竖立在天空。
和叶子是在底部。
>> 因此，它是一种像服用一棵树 和刚刚翻转倒扣。
但仍有分支。
而这些将是我们的途径， 这些将是我们连接
从根到叶。
在这种情况下，这些 路径，这些分支
贴有告诉我们数字 去从那里我们走哪条路。
>> 如果我们看到一个0，我们再往这个分支， 如果我们看到一个1，我们再往这个分支，
等等。
那么，这是什么意思？
嗯，这意味着， 在每一个结点
和中的每一个节点 中，每一个分支，
有10种可能的 的地方，我们可以走了。
因此，有10球 从每一个位置。
>> 而这正是试图能得到 有点吓人的人
谁是没有很多 在计算机科学之前的经验。
但尝试是真的很漂亮真棒。
如果你有 有机会与他们一起工作
并且你愿意去挖掘，在 并与他们进行试验，
他们真的很有趣 数据结构一起工作。
如果我们要插入元素 到线索，我们需要做的
正在建设的正确道路 从根到叶。
以下是每一步都顺 的方式可能看起来像。
我们要定义一个新的数据 结构为一个新的节点称为线索。
>> 和这些数据的内 结构有两片。
我们要保存 一所大学的名字。
而且我们要存储 指针数组
到相同类型的其他节点。
所以，再一次，这是排序 无处不在的概念
我们是，我们在10个可能的 的地方，我们可以走了。
如果我们看到一个0，我们走上这条分支。
如果我们看到一个1，这个分支， 等等等等等等。
如果说9，我们走上这条分支。
因此，在每一个结点， 我们可以去10个可能的地方。
因此，每个节点必须包含10个三分球 到其他节点，对其他10个节点。
>> 我们要存储的数据是 大学只是名字。
因此，让我们建立一个线索。
让我们插入一对夫妇 的物品进入我们的线索。
因此，在最高层， 这是我们的根节点。
这可能将是什么 你会在全球范围内申报。
而你要在全球范围内保持 一个指向该节点始终。
>> 你会说， 根等于和你
将自己的malloc字典树节点。
而且你永远也不会 再次触及根本。
你想每次 开始导航通过，
您设置另一个指针 等于根，如TRAV，
这是例子，我 在我的很多影片使用
在这里栈和队列 和链接列表等。
>> 您可以设置另一个指针 所谓TRAV遍历。
并使用TRAV导航 通过的数据结构。
因此，让我们看看这个看起来。
所以，现在，是什么 没有一个节点是什么样子？
好了，就像我们的数据 结构声明指出，
我们有一个字符串，它 在这种情况下是空的。
这里没有什么。
>> 和10指针数组。
而现在，我们只 在这个线索1个节点。
还有没有别的它。
因此，所有的10个国家 指针指向为null。
这就是红色表示。
>> 让我们插入字符串哈佛。
让我们插入的大学 哈佛的这个线索，这
始建于1636年。
我们要使用的密钥， 1636年，告诉我们，我们是
将存储在哈佛的线索。
现在，我们如何才能做到这一点？
>> 它可能是这个样子。
我们从根开始。
我们有这10个地方，我们可以走了。
根就像任何 该线索的其他节点。
有10个地方，我们可以从这里走。
>> 我们在哪里可能要 去，如果关键的是1636？
这确实两个选项。
对。
我们可以建立从关键 从右到左，并开始与6。
或者我们可以建立从关键 从左到右，从1开始。
>> 它可能更 直观的作为一个人
了解我们 刚去左到右。
所以，如果我想插入 哈佛的这个线索，
我可能要开始 通过从根开始，
看我10选项 在我面前，说
我想下井1路。
好。
>> 现在，1路目前为空。
所以，如果我想继续沿着这条道路 插入这个元素为线索，
我对malloc一个新的节点，有1 点在那里，然后我好去。
>> 所以我基本上是在 点我站在那里
在树或根 线索并有10个分支机构。
但是，每个分支都有 门在它的前面。
对。
因为没有什么别的有。
没有安全通道。
这意味着什么 下所有的分支。
如果我想开建 什么的，我想删除的大门。
我想删除的门 在1号的前面。
我希望走的。
我想建立 另一个地方，我去。
>> 这就是我在这里所做的。
所以1不再指向空。
我说，这是安全的走下来这里。
我建了另一个节点。
当我到达这个节点，我 有另外的决定。
我要去哪里，从这里去？
>> 好吧，我已经走了下来1。
所以，现在我可能要下井6。
对。
再有，我有10个位置，我可以选择。
现在让我们往下走6号。
所以我清除门 在号码6的前方。
而我走那里。
我建一个节点。
而且我已经达到了另一个结点。
>> 再有，我有10个选择 为在那里我可以走了。
我搬到从1到6。
所以，现在我可能要到3。
3，没有什么地方我可以去。
所以我开道 和自己建​​一个新的空间。
然后再从3，我在哪里要去？
我想下去6。
>> 而且，再一次，我不得不 清除做到这一点的方式。
所以，现在我用我的钥匙插入创建 节点，并开始建立这个线索。
我已经在根开始。
我已经走了下来1636。
现在我在底部 在该节点上存在。
你也许能 看到它在屏幕上。
>> 它以黄色突出显示。
这就是我目前。
我的键完成。
我用尽我的钥匙每个位置上。
因此，我不能再往前走。
因此，在这点上，所有的余 真正需要做的是说好。
那种这就像找 下来在地上，
如果你设想 自己作为这种路径
具有不同的连接。
排序看不起排序和 喷在地面上画哈佛。
这就是此名称。
知道这是什么，在这个位置。
如果我们从根开始，我们下去 1，然后6，然后3，然后6，
我们在哪？
那么，如果我们往下看 我们看到哈佛，然后
我们知道，哈佛 成立于1636年的基础上的方式
我们正在实施这个数据结构。
所以这是希望简单。
我们要做两个插入。
并希望它会帮助 看到这样做的两倍以上。
>> 现在，让我们插入另一所大学。
让我们耶鲁插入到这个线索。
耶鲁大学成立于1701年。
因此，我们将开始在 根，因为我们总是这样。
我们设定一个遍历指针。
我们将用它来移动通过。
我们要的第一件事情 做的是往下走的1路。
这是我们的关键的第一位。
但幸运的是，我们不这样做 做任何工作，这个时候。
1.路径已被清除。
我以前当我清除了 在1636插入哈佛大学。
因此，我可以安全地移动 下来1，只是去那里。
如果能下移1。
>> 但现在，我想去7。
我扫清了道路6。
我知道，我可以放心地 继续向下进行6路径。
但我需要继续在7路径。
那么，我需要做什么？
嗯，就像以前一样，我只需要 清除门，走出去的方式，
并建立从7路一个新的节点。
像这样。
>> 所以，现在我已经搬到1，然后7。
而现在发现，我有点 在这个新的支行。
对。
其他的一切，从16 对，我不关心。
我没有做任何事情16。
我做17的东西。
>> 所以现在17，我要 排序这里开拓创新。
下一个数字我的关键是0。
我显然不能取得任何进展。
我刚刚建立了这个节点。
所以，我知道有没有 路径向前从这里开始。
所以，我必须作出一个自己。
>> 所以，我的malloc一个新的节点 并具有0点出现。
再一次，我的malloc一个 新的节点，并有一个点出现。
再次，我已经用尽了我的钥匙，1701。
所以，我看下来，我喷漆耶鲁。
这是这个节点的名称。
>> 所以，现在如果我以往任何时候都需要的，如果耶鲁看 在这个线索，我从根开始，
我下去1701，往下看。
如果我看到耶鲁喷雾 涂到地面，再
我知道耶鲁存在于这个线索。
让我们做一个。
让我们来达特茅斯插入到这个 特里，这是成立于1769年。
>> 再从根开始。
我的钥匙我的第一个数字是1。
我可以肯定地向下移动，这条道路。
已经存在。
我的钥匙的下一个数字是7。
我可以肯定地向下移动，这条道路。
它的存在也是如此。
>> 我的下一个是6。
从这里，从那里我目前 在这中间节点黄色那里，
6目前被锁定了。
如果我想要走这条路， 我必须建立它自己。
所以，我的malloc一个新的节点 并有6点在那里。
然后，再次，我 在这里开拓创新。
>> 所以，我的malloc一个新的节点，以便从 这node--路径编号9-然后现在
如果我游1769年，我往下看。
没有什么目前 喷漆那里。
我可以写达特茅斯。
我也插 达特茅斯到线索。
>> 所以这是插入 事情到线索。
现在，我们要寻找的东西。
我们如何寻找东西的线索？
嗯，这几乎是同样的想法。
现在我们只是使用的关键数字 看看我们是否能够从根本导航
到我们想去的线索。
>> 如果我们在任何时候进入了死胡同，然后 我们知道，该元件不能存在
否则这条道路会 已经被清除。
如果我们让它一路 最后，我们需要做的
是往下看，看看是否是 我们正在寻找的元素。
如果是，成功。
如果不是的话，失败。
>> 因此，让我们搜索 哈佛大学在这个线索。
我们从根开始。
并再次，我们要 创建一个遍历指针
做我们的动作我们。
从根我们知道 我们需要去第一个地方是1，
我们能做到这一点？
我们可以。
如果安全存在。
我们可以去那里。
>> 现在，我们需要去下一个地方是6。
请问6路从这里存在吗？
是的，确实如此。
我们可以去6个路径。
而我们在这里结束。
>> 我们可以去从这里的3路？
嗯，事实证明， 是的，存在了。
而且我们可以得到从这里的6路？
我们可以。
>> 我们还没有完全回答 这个问题呢。
但还有一个更 步骤，这是现在
我们需要往下看， 看看这actually--
如果我们要寻找的哈佛大学，是 我们发现后，我们用尽了钥匙吗？
在这个例子中，我们使用的是在这里， 这些年来始终是四位数字。
但是，你可能会使用的例子， 你是存储单词的词典。
>> 因此，而不是具有10个三分球 我的位置，你可能有26。
一个用于每个字母。
还有一些话像蝙蝠， 这是批量的一个子集，例如。
所以，即使你到了 关键的结束，你看下来，
你可能不会看到什么 你正在寻找。
>> 所以，你总是要遍历 整个路径，然后
如果你能够成功 遍历整个路径，
往下看，做一个最后的确认。
那是我在找什么？
好吧，我开始后往下看 在顶部和去1636。
我往下看。
我看到哈佛。
所以，是的，我成功了。
如果什么什么我在寻找 是不是在线索，虽然。
如果我在寻找普林斯顿， 该公司成立于1746年。
所以，1746成为我的钥匙 浏览该线索。
好吧，我从根开始。
我希望首位 到下山的1路。
我能做到吗？
我可以。
>> 我可以下去从那里的7路？
是的，我可以。
存在了。
但我可以去​​从这里的4路？
这就像问一个问题，就可以 我继续向下的小广场
我在黄已经强调？
有什么也没有。
对。
>> 有没有办法前进下来的4路。
如果普林斯顿在这个线索，即4 已被清除我们了。
因此在这一点上 我们已经到了一个死胡同。
我们不能再往前走。
因此，我们可以说，明确，没有。
普林斯顿并不在此线索存在。
>> 那么，这意味着什么？
对。
有很多怎么回事。
有指针所有的地方。
而且，正如你所看到的 刚刚从图中，
有很多节点的 都是那种飞来飞去。
但是请注意，每次我们想时间 检查东西是否是在特里，
我们只有使4举动。
>> 我们希望每一次 在线索中插入一些东西，
我们必须做出4的动作，有可能 mallocing沿途的一些东西。
但正如我们看到的，当我们插入 达特茅斯到线索，
有时一些路径的 可能已经被清除了我们。
所以作为我们的线索变得更大， 更大，我们有充分的时间少做工作
插入新事物 因为我们已把
内置了很多中间的 沿途分支。
如果我们永远只能来看看 4东西，4仅仅是一个常数。
那种我们确实正在接近 恒定的时间插入
和恒定的时间查找。
权衡，当然，在于 这个线索，因为你可能会说，
是巨大的。
这些节点中的每一个 占用了大量的空间。
>> 但是，这是权衡。
如果我们要真正快速 插入，真的很快删除，
真正快速查找，我们要 有大量的数据到处乱飞。
我们必须预留了很大的空间 和存储器，用于该数据结构
存在。
>> 所以这就是权衡。
但看起来我们 可能已经找到了它。
我们可能会发现， 数据结构的圣杯
与快速插入， 缺失和查找。
也许这将是一个 合适的数据结构
用于任何信息 我们试图店。
我是道格·劳埃德，这是CS50。