[音樂播放] 道格·勞埃德：所以我們一直在緩慢接近 而接近該數據的聖杯 結構，一個我們可以插入 成，刪除，並查找 在固定的時間。 右。 這是排序的目標。 我們希望能夠做 事情非常，非常快。 

難道我們發現這裡的時候， 我們談論的嘗試？ 好吧，讓我們一起來看看。 因此，我們已經看到一些 不同的數據結構 該處理的映射 所謂鍵 - 值對， 一些映射數據塊 其他一些數據片段 所以我們知道在哪裡可以找到 在結構信息。 

因此對於陣列，例如，該 關鍵是該元素索引或陣列 位置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。