>> KEVIN SCHMID：有时候，构建一个时 程序，你可能想利用
称为字典的数据结构。
字典映射键，这是 通常是字符串，将值，整数，
字符，一个指针到某些对象， 任何我们想要的。
这就像普通的字典 那个地图的话，通过定义。
>> 字典为我们提供了 存储信息的能力
与相关的东西 后来看看它。
那么，如何才能真正实现一 字典，比方说，C代码，我们可以
在我们的计划之一使用？
嗯，有很多的方式， 我们可以实现一个字典。
>> 首先，我们可以使用一个数组，我们 动态调整大小，或者我们可以使用一个
链表，哈希表 或二叉树。
但无论我们选择，我们应该 铭记效率和
实施的绩效。
我们应该想想所使用的算法 插入和查找物品进入
我们的数据结构。
>> 现在，让我们假设我们 要使用字符串作为键。
让我们来谈谈一种可能性， 一个数据结构，称为特里。
所以这里有一个可视化表示 的线索。
>> 作为图像显示，一个线索 是一个树形数据结构与
节点连接在一起。
我们看到，有清楚的根 节点与一些链接延伸到
其他节点。
但什么是每个节点组成的呢？
如果我们假设我们正在存储密钥 只有字母字符，并
我们不关心资本化， 这里有一个节点的定义，
就足够了。
>> 其类型的对象是结构 节点有两个部分
所谓的数据和儿童。
我们已经离开了数据部分为​​注释 由一个部件来代替
申报时结构节点 在C程序中。
一个节点的数据部分可能是一个 布尔值，表示是否
不是节点为完成 的字典键或者它可能是一个
表示定义字符串 在字典中的词。
>> 我们将使用一个笑脸来表示 当数据存在于一个节点。
有26个元素我们 儿童阵列，一个索引
每个字母字符。
我们将看到的意义 这很快。
>> 让我们根节点仔细看看 在我们的图表，它没有数据
与它相关的，由所指示的 没有在笑脸的
数据部分。
从该部件延伸的箭头 孩子们数组表示非节点
指针到其他节点。
例如，箭头从延伸 儿童的第二元件
代表字母B 在字典键。
并且在较大的图 我们用B。贴上标签
>> 需要注意的是在更大的框图，当我们 绘制一个指针到另一个节点，它
不要紧其中箭头 符合该另一节点。
我们的样本字典包含特里 两个词，那和变焦。
让我们通过一个例子 查找数据的关键。
>> 假设我们要查找 为密钥浴相应值。
我们将开始我们的样子了 在根节点。
然后，我们将利用我们的第一个字母 键，B和找到对应
发现我们的孩子阵列。
请注意，恰好有26点 数组，一个用于每个字母在
字母表。
我们将有斑点代表 字母表中的顺序中的字母。
>> 我们来看看第二个索引的话， 索引1，为B。在一般情况下，如果我们
有一些字母字母C我们 可确定相应的点
在使用儿童阵列 计算是这样的。
我们可以使用一个较大的孩子 如果数组我们希望提供的看看了
具有更广泛的字符键， 如在整个
ASCII字符集。
>> 在这种情况下，指针 在我们的孩子在阵列
指标之一是不为null。
因此，我们将继续寻找 了关键洗澡。
如果我们曾经遇到过一个空指针 在孩子正确点
数组，而我们所走过的节点， 那么我们将不得不说，我们
找不到任何为关键。
>> 现在，我们将采取的第二个字母 我们的关键，A，并继续以下
这样的指针，直到我们 达到我们的主要的结束。
如果我们达到了关键的结束不 击中任何死角，空指针，
因为是这里的情况，那么我们只 必须检查一件事。
这是真正的关键 在字典？
>> 如果是这样，我们应该找到一个值，以及一个 在我们的图表笑脸图标在那里
这个词结束。
如果还有别的东西与存储 的数据，那么我们就可以返回。
例如，关键动物园不在 字典，即使我们可以有
达到了这个关键的结束而没有 打一个空指针，而我们
遍历线索。
>> 如果我们试图寻找出关键洗澡时， 倒数第二个节点的数组索引，
对应的字母H，将 举行一个空指针。
所以洗澡是不是在字典中。
和这样一个线索是独特的，该密钥 从来没有明确地存储在
的数据结构。
那么，我们如何将东西 成特里？
>> 让我们来插入钥匙 动物园到我们的线索。
请记住，在一个节点一个笑脸 可以在代码中对应于一个简单的
Boolean值，表明动物园 在字典中，或者它可以
对应的详细信息，我们 希望与关键动物园相关联，
类似的定义 字或别的东西。
在某些方面，这个过程要插入 事成特里类似于
仰视的东西在特里。
>> 我们先从根节点再次， 对应下面的指针
我们主要的字母。
幸运的是，我们能够跟随指针 所有，直到我们到达方式
该键的末端。
由于动物园是这个词的前缀 变焦，这是其中一个成员
字典，我们不需要 分配任何新的节点。
>> 我们可以修改节点，以指示 字符导致的路径
它代表了我们的字典的一个关键。
现在，让我们尝试插入 关键沐浴到特里。
我们将开始在根节点 并再次跟随指针。
但在这种情况下，我们打一个死 最终我们能够到达之前
关键的结束。
现在，我们需要分配一些新的 节点需要分配一个新的
节点的每个剩余 我们的主要的信。
>> 在这种情况下，我们只需要 分配一个新的节点。
然后，我们将需要使H指数 引用该新节点。
再次，我们可以通过修改节点 显示的字符的路径
导致它代表一个 关键在我们的字典。
让我们来推理渐近 我们的程序，这些复杂性
两个操作。
>> 我们注意到，在这两种情况下的数 步骤我们的算法是拿了
成比例的数量 信中的关键字。
这是正确的。
当你想查找的单词 特里，你只需要遍历
字母一个接一个，直到您 达到该字的结尾或
在特里打了一个死胡同。
>> 而当你想插入一个关键 值对成特里使用
过程中，我们讨论了，最坏的情况下 将你分配一个新节点
每个字母。
我们将假设分配 是一个常数时间的操作。
所以，如果我们假设密钥长度为 由一个固定的常数，二者有界
插入和查找是不变的 运营时间为线索。
>> 如果我们不做出这种假设， 密钥的长度是由一个固定的范围内
常数，则插入和查询， 在最坏的情况下，是线性的
长的关键。
请注意，保存的项目数量 在该线索不影响它的外表向上
或插入时间。
它只能由受影响 长的关键。
>> 相比之下，添加条目，比方说， 哈希表往往使
未来看起来更慢。
虽然这听起来吸引人起初， 我们应该记住，一个
有利的渐近复杂性不 意味着在实践中，数据
结构是必然 无可非议。
我们还必须考虑到存储 字在字典树，我们所需要的，在最坏的
情况下，节点数量成比例 于字本身的长度。
>> 尝试倾向于使用大量的空间。
这是相对于一个哈希表， 在这里我们只需要一个新的节点
存储一些键值对。
现在，再从理论上讲，空间大 消费似乎并不像一个大
处理，特别是考虑到现代 电脑有千兆字节和
GB的内存。
但事实证明，我们仍然有 不用担心内存使用和
组织为求 性能，因为现代计算机
有下建立了相关机制 油烟机，以加快内存访问。
>> 但这些机制最好的工作时 内存访问是在紧凑的制作
区域或地区。
和特里的节点可以驻留 在堆中的任何地方。
但这些都是权衡 我们必须考虑的问题。
>> 请记住，选择一个数据时， 结构有一定的任务，我们
应该想想什么样的 操作的数据结构需要
支持和多少的性能 这些每个的
操作事项给我们。
这些操作可能连 超越只是
基本外观和插入。
假设我们要实现一个样 自动完成功能，多
像谷歌搜索引擎一样。
也就是说，退还所有钥匙和 潜在的价值观，
有一个给定的前缀。
>> 字典树是唯一有用的 进行此操作。
这是简单的遍历 该线索进行的每一个字符
前缀。
就像一个查找操作， 我们可以遵循的指针
逐个字符。
然后，当我们在的底到达 前缀，我们可以遍历
该数据结构的其余部分 因为任何按键超越
这点有前缀。
>> 它也很容易得到此房产 自中按字母顺序
孩子们数组中的元素 按字母顺序排序。
所以希望你们能考虑 捐赠试图一试。
我是凯文·施密德，这是CS50。
>> 啊，这是开始 的下降。
对不起。
抱歉。
>> 罢工四人。
我走了。
抱歉。
对不起，让谁的人 要编辑这个发疯。
>> 抱歉。
抱歉。
>> 扬声器1：干得好。
这是真的做得很好。