>> [音樂播放]
道格·勞埃德：所以我們一直在緩慢接近 而接近該數據的聖杯
結構，一個我們可以插入 成，刪除，並查找
在固定的時間。
右。
這是排序的目標。
我們希望能夠做 事情非常，非常快。
>> 難道我們發現這裡的時候， 我們談論的嘗試？
好吧，讓我們一起來看看。
因此，我們已經看到一些 不同的數據結構
該處理的映射 所謂鍵 - 值對，
一些映射數據塊 其他一些數據片段
所以我們知道在哪裡可以找到 在結構信息。
>> 因此對於陣列，例如，該 關鍵是該元素索引或陣列
位置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。