>> KEVIN SCHMID：有時候，構建一個時 程序，你可能想利用
稱為字典的數據結構。
字典映射鍵，這是 通常是字符串，將值，整數，
字符，一個指針到某些對象， 任何我們想要的。
這就像普通的字典 那個地圖的話，通過定義。
>> 字典為我們提供了 存儲信息的能力
與相關的東西 後來看看它。
那麼，如何才能真正實現一 字典，比方說，C代碼，我們可以
在我們的計劃之一使用？
嗯，有很多的方式， 我們可以實現一個字典。
>> 首先，我們可以使用一個數組，我們 動態調整大小，或者我們可以使用一個
鍊錶，哈希表 或二叉樹。
但無論我們選擇，我們應該 銘記效率和
實施的績效。
我們應該想想所使用的算法 插入和查找物品進入
我們的數據結構。
>> 現在，讓我們假設我們 要使用字符串作為鍵。
讓我們來談談一種可能性， 一個數據結構，稱為特里。
所以這裡有一個可視化表示 的線索。
>> 作為圖像顯示，一個線索 是一個樹形數據結構與
節點連接在一起。
我們看到，有清楚的根 節點與一些鏈接延伸到
其他節點。
但什麼是每個節點組成的呢？
如果我們假設我們正在存儲密鑰 只有字母字符，並
我們不關心資本化， 這裡有一個節點的定義，
就足夠了。
>> 其類型的對象是結構 節點有兩個部分
所謂的數據和兒童。
我們已經離開了數據部分為註釋 由一個部件來代替
申報時結構節點 在C程序中。
一個節點的數據部分可能是一個 布爾值，表示是否
不是節點為完成 的字典鍵或者它可能是一個
表示定義字符串 在字典中的詞。
>> 我們將使用一個笑臉來表示 當數據存在於一個節點。
有26個元素我們 兒童陣列，一個索引
每個字母字符。
我們將看到的意義 這很快。
>> 讓我們根節點仔細看看 在我們的圖表，它沒有數據
與它相關的，由所指示的 沒有在笑臉的
數據部分。
從該部件延伸的箭頭 孩子們數組表示非節點
指針到其他節點。
例如，箭頭從延伸 兒童的第二元件
代表字母B 在字典鍵。
並且在較大的圖 我們用B。貼上標籤
>> 需要注意的是在更大的框圖，當我們 繪製一個指針到另一個節點，它
不要緊其中箭頭 符合該另一節點。
我們的樣本字典包含特里 兩個詞，那和變焦。
讓我們通過一個例子 查找數據的關鍵。
>> 假設我們要查找 為密鑰浴相應值。
我們將開始我們的樣子了 在根節點。
然後，我們將利用我們的第一個字母 鍵，B和找到對應
發現我們的孩子陣列。
請注意，恰好有26點 數組，一個用於每個字母在
字母表。
我們將有斑點代表 字母表中的順序中的字母。
>> 我們來看看第二個索引的話， 索引1，為B。在一般情況下，如果我們
有一些字母字母C我們 可確定相應的點
在使用兒童陣列 計算是這樣的。
我們可以使用一個較大的孩子 如果數組我們希望提供的看看了
具有更廣泛的字符鍵， 如在整個
ASCII字符集。
>> 在這種情況下，指針 在我們的孩子在陣列
指標之一是不為null。
因此，我們將繼續尋找 了關鍵洗澡。
如果我們曾經遇到過一個空指針 在孩子正確點
數組，而我們所走過的節點， 那麼我們將不得不說，我們
找不到任何為關鍵。
>> 現在，我們將採取的第二個字母 我們的關鍵，A，並繼續以下
這樣的指針，直到我們 達到我們的主要的結束。
如果我們達到了關鍵的結束不 擊中任何死角，空指針，
因為是這裡的情況，那麼我們只 必須檢查一件事。
這是真正的關鍵 在字典？
>> 如果是這樣，我們應該找到一個值，以及一個 在我們的圖表笑臉圖標在那裡
這個詞結束。
如果還有別的東西與存儲 的數據，那麼我們就可以返回。
例如，關鍵動物園不在 字典，即使我們可以有
達到了這個關鍵的結束而沒有 打一個空指針，而我們
遍歷線索。
>> 如果我們試圖尋找出關鍵洗澡時， 倒數第二個節點的數組索引，
對應的字母H，將 舉行一個空指針。
所以洗澡是不是在字典中。
和這樣一個線索是獨特的，該密鑰 從來沒有明確地存儲在
的數據結構。
那麼，我們如何將東西 成特里？
>> 讓我們來插入鑰匙 動物園到我們的線索。
請記住，在一個節點一個笑臉 可以在代碼中對應於一個簡單的
Boolean值，表明動物園 在字典中，或者它可以
對應的詳細信息，我們 希望與關鍵動物園相關聯，
類似的定義 字或別的東西。
在某些方面，這個過程要插入 事成特里類似於
仰視的東西在特里。
>> 我們先從根節點再次， 對應下面的指針
我們主要的字母。
幸運的是，我們能夠跟隨指針 所有，直到我們到達方式
該鍵的末端。
由於動物園是這個詞的前綴 變焦，這是其中一個成員
字典，我們不需要 分配任何新的節點。
>> 我們可以修改節點，以指示 字符導致的路徑
它代表了我們的字典的一個關鍵。
現在，讓我們嘗試插入 關鍵沐浴到特里。
我們將開始在根節點 並再次跟隨指針。
但在這種情況下，我們打一個死 最終我們能夠到達之前
關鍵的結束。
現在，我們需要分配一些新的 節點需要分配一個新的
節點的每個剩餘 我們的主要的信。
>> 在這種情況下，我們只需要 分配一個新的節點。
然後，我們將需要使H指數 引用該新節點。
再次，我們可以通過修改節點 顯示的字符的路徑
導致它代表一個 關鍵在我們的字典。
讓我們來推理漸近 我們的程序，這些複雜性
兩個操作。
>> 我們注意到，在這兩種情況下的數 步驟我們的算法是拿了
成比例的數量 信中的關鍵字。
這是正確的。
當你想查找的單詞 特里，你只需要遍歷
字母一個接一個，直到您 達到該字的結尾或
在特里打了一個死胡同。
>> 而當你想插入一個關鍵 值對成特里使用
過程中，我們討論了，最壞的情況下 將你分配一個新節點
每個字母。
我們將假設分配 是一個常數時間的操作。
所以，如果我們假設密鑰長度為 由一個固定的常數，二者有界
插入和查找是不變的 運營時間為線索。
>> 如果我們不做出這種假設， 密鑰的長度是由一個固定的範圍內
常數，則插入和查詢， 在最壞的情況下，是線性的
長的關鍵。
請注意，保存的項目數量 在該線索不影響它的外表向上
或插入時間。
它只能由受影響 長的關鍵。
>> 相比之下，添加條目，比方說， 哈希表往往使
未來看起來更慢。
雖然這聽起來吸引人起初， 我們應該記住，一個
有利的漸近複雜性不 意味著在實踐中，數據
結構是必然 無可非議。
我們還必須考慮到存儲 字在字典樹，我們所需要的，在最壞的
情況下，節點數量成比例 於字本身的長度。
>> 嘗試傾向於使用大量的空間。
這是相對於一個哈希表， 在這裡我們只需要一個新的節點
存儲一些鍵值對。
現在，再從理論上講，空間大 消費似乎並不像一個大
處理，特別是考慮到現代 電腦有千兆字節和
GB的內存。
但事實證明，我們仍然有 不用擔心內存使用和
組織為求 性能，因為現代計算機
有下建立了相關機制 油煙機，以加快內存訪問。
>> 但這些機制最好的工作時 內存訪問是在緊湊的製作
區域或地區。
和特里的節點可以駐留 在堆中的任何地方。
但這些都是權衡 我們必須考慮的問題。
>> 請記住，選擇一個數據時， 結構有一定的任務，我們
應該想想什麼樣的 操作的數據結構需要
支持和多少的性能 這些每個的
操作事項給我們。
這些操作可能連 超越只是
基本外觀和插入。
假設我們要實現一個樣 自動完成功能，多
像谷歌搜索引擎一樣。
也就是說，退還所有鑰匙和 潛在的價值觀，
有一個給定的前綴。
>> 字典樹是唯一有用的 進行此操作。
這是簡單的遍歷 該線索進行的每一個字符
前綴。
就像一個查找操作， 我們可以遵循的指針
逐個字符。
然後，當我們在的底到達 前綴，我們可以遍歷
該數據結構的其餘部分 因為任何按鍵超越
這點有前綴。
>> 它也很容易得到此房產 自中按字母順序
孩子們數組中的元素 按字母順序排序。
所以希望你們能考慮 捐贈試圖一試。
我是凱文·施密德，這是CS50。
>> 啊，這是開始 的下降。
對不起。
抱歉。
>> 罷工四人。
我走了。
抱歉。
對不起，讓誰的人 要編輯這個發瘋。
>> 抱歉。
抱歉。
>> 揚聲器1：幹得好。
這是真的做得很好。