[Powered by Google Translate] [二進制搜索]
[帕特里克·施密德 - 哈佛大學]
[這是CS50。 - CS50.TV]
>> 如果我給你的迪士尼人物名稱按字母順序排列的列表
問你找到米老鼠，
你會如何去這樣做呢？
一個顯而易見的方法將是從開始掃描列表
並檢查每一個名字，看它是否是米奇。
但是，當你閱讀阿拉丁，愛麗絲，碧浪，等等，
你很快就會意識到，在前面的列表是不是一個好主意。
好吧，也許你應該開始從列表末尾向後工作。
現在你看泰山，史迪仔，白雪公主，等等。
不過，這似乎並不像最好的方式去了解它。
>> 那麼，另一種方式，你可以去這樣做的，是盡量縮小
名稱的列表，你必須看。
既然你知道，他們是按字母順序排列，
在中間的列表中，你可以看名字
檢查，如果米老鼠這個名字之前或之後。
在第二列中的最後一個名稱綜觀
你會意識到M的米奇在J茉莉，
所以，你會簡單地忽略上半年的列表。
然後，你可能會在頂部的最後一列
，並認為它與長發姑娘開始。
米奇之前，長發姑娘，看起來我們可以忽略的最後一列。
繼續搜索策略，你很快就會發現，米奇
是在其它的名稱列表中的第一個一半的
終於找到米奇隱藏在梅林和米妮之間。
>> 你剛才做的基本上是二進制搜索。
正如這個名字所暗示的，它執行它的搜索策略，在一個二進制的問題。
這是什麼意思呢？
那麼，給出一個列表排序的項目，二進制搜索算法使得一個二進制的決定 -
左或右，大於或小於，之前或之後的字母順序 - 在每一個點。
現在，我們有一個名字伴隨著本次搜索算法，
讓我們來看看另一個例子，但這次的列表排序的數字。
說我們正在為數字144在此列表中的排序號碼。
就像以前一樣，我們發現在中間的數字 -
在這種情況下是13 - 和看到，如果144是大於或小於13。
因為它是明顯大於13，我們可以忽略一切，這是13或更小
只集中在剩下的一半。
因為我們現在有一個偶數留下的物品，
我們簡單地選擇一個數字，接近中間。
在這種情況下，我們選擇55。
我們可以很容易地選擇89。
好吧。同樣，144是大於55，所以我們去的權利。
幸運的是，在未來的中間數是144，
我們正在尋找的。
因此，為了找到144使用二進制搜索，我們可以找到它的只有3個步驟。
如果我們將使用線性搜索，將採取12個步驟。
事實上，由於這個搜索方法的項目數減半
它的每一步看，會發現它正在尋找的項目
大約在日誌列表中的項目的數目。
現在，我們已經看到了2個例子，讓我們一起來看看
一個遞歸函數的偽代碼實現二進制搜索。
從頂部開始，我們可以看到，我們必須找到一個函數，它接受4個參數：
鍵，陣列，最小和最大。
最關鍵的是我們正在尋找的數字，所以144在前面的例子。
數組是數字列表，我們正在尋找。
min和max是最小和最大位置的指數，其中
我們正在尋找。
因此，當我們開始的時候，min將是零和最大將是最大的索引的數組。
當我們縮小搜索範圍，我們將更新的最小值和最大值
的範圍內，我們仍然往裡看。
>> 讓我們先跳到最有趣的部分。
我們做的第一件事是找到中點，
該指數中間的最小值和最大值的數組，我們還在考慮。
然後我們看一下，中點位置的值的數組
看到，我們正在尋找的數字，如果是小於該鍵。
如果在該位置上的數目比較少，
那麼它意味著關鍵是大於所有編號，以該位置的左側的。
因此，我們可以稱之為二進制搜索功能，
但這次更新的最小值和最大值參數只讀取一半
也就是大於或等於的值，我們剛剛看到的。
在另一方面，如果該鍵的數目小於在當前陣列中點，
我們想要去的左側，而忽略所有的數字是更大的。
同樣，我們稱之為二進制搜索，但這個時間範圍內的最小值和最大值更新
以僅包括下半部。
如果陣列中的當前的中點處的值既不是
大於也不小於鍵，那麼它必須是相等的關鍵。
因此，我們可以簡單地返回當前的中點指數，我們就大功告成了。
最後，這裡此檢查為的情況下，數字
實際上不是在數組中的數字，我們正在尋找。
如果在最大的範圍內，我們正在尋找的指數
高於最低要求是越來越少，這意味著我們已經走得太遠了。
由於數字輸入數組中，我們返回-1
表明，沒有被發現。
>> 您可能已經注意到了這個算法的工作，
的號碼列表進行排序。
換句話說，我們只能找到144使用二進制搜索
如果所有的數字都下令從最低到最高。
如果不是這樣的情況下，我們將無法排除一半的數字在每個步驟。
因此，我們有2個選擇。
要么我們可以採取一個無序的列表，並使用二進制搜索，排序前，
或者我們可以肯定，我們將號碼添加到列表中的數字進行排序。
因此，而不是排序的時候，我們要搜索，
為什麼不排序的列表，在任何時候都保持？
>> 同時允許排序的方式，讓一個數字列表
一個添加或移動號碼從這個名單
是通過使用一種稱為二叉搜索樹。
二叉搜索樹是一種數據結構，有3個屬性。
首先，左子樹中的任何節點只包含值小於
或等於節點的值。
其次，節點的右子樹中包含的值大於
或等於節點的值。
以及最後，無論是左和右子樹的所有節點
二叉搜索樹。
讓我們看一個例子，與我們之前使用的相同的號碼。
對於那些你從來沒有見過計算機科學樹前，
首先，讓我告訴你，計算機科學樹是向下增長的。
是的，不像你習慣的樹木，
計算機科學樹的根是在頂部，
和葉子都在底部。
每個小方塊被稱為一個節點，節點由邊緣彼此連接。
因此，這棵樹的根是一個節點值的值13，
具有2個孩子的節點的值5和34。
子樹是樹，形成整個樹在第。
>> 例如，左邊的子樹的節點3是建立的樹由節點0，1和2。
所以，如果我們回到一個二叉搜索樹的性質，
我們可以看到，在樹中的每個節點符合所有3個屬性，即，
左子樹僅包含節點的值小於或等於的值;
所有節點的右子樹
只包含節點的值大於或等於值;
左，右子樹的所有節點也有二叉​​搜索樹。
雖然這棵樹看起來不一樣，這是一個有效的二叉搜索樹
對於同一組的數字。
事實上，有許多可能的方式，你可以創建
從這些數字的一個有效的二叉搜索樹。
好吧，讓我們回到我們創建的第一個。
所以，我們可以做什麼與這些樹呢？
好了，我們可以很簡單地找到的最低值和最高值。
可以找到的最小值總是要在左邊
直到有沒有更多的節點訪問。
相反，找到的最大的僅僅只是下山的權利在每個時間。
>> 查找任何其他數目的最小值或最大值
也很容易。
假設我們正在尋找數89。
我們簡單地檢查每個節點的值，向左或向右，
根據節點的值是否小於或大於
我們正在尋找的。
所以，從13根，我們可以看到，89，
所以我們去正確的。
然後，我們看到了34節點，我們再次去正確的。
89大於55，所以我們繼續去合適。
然後，我們來到了一個節點的值144，和去左邊。
你瞧，89是正確的。
>> 我們可以做的另一件事，是打印出所有進行中序遍歷。
中序遍歷是指打印任何事物的左子樹
隨後由打印節點本身
然後印刷一切在右子樹。
例如，讓我們最喜歡的二叉搜索樹
的排序順序打印出來的數字。
首先，我們在13根的，但我們必須在打印前13打印出
一切都在左子樹。
因此，我們轉到5。我們仍然有更深入的倒在了樹，直到我們找到了最左邊的節點，
這是零。
印刷零後，我們回去到1，並打印了這一點。
然後我們去的右子樹，也就是2，打印了這一點。
現在，我們已經完成了該子樹，
我們可以回去了3個，並把它打印出來。
持續回升，我們打印5和8。
現在，我們已經完成了整個左子樹，
我們可以打印出13個，並開始工作的右子樹。
我們跳了34，但我們必須在打印前34打印出其左子樹。
所以，我們打印出21，然後打印出34，訪問右子樹。
由於55沒有左子樹，我們打印出來，並繼續其右子樹。
144有一個左子樹，所以我們打印出89，其次是144，
233，最後最右邊的節點。
有你有它，所有的號碼都打印出來，以便從最低到最高。
>> 添加的樹是什麼，以及相對無痛的。
我們要做的是確保我們按照二叉搜索樹性能
然後插入值有空間的地方。
比方說，我們要插入的值是7。
自7是小於13，我們去左邊。
但它大於5，所以我們遍歷的權利。
由於它是小於8和圖8是一個葉節點，我們添加7至8的左子。
瞧！我們已經添加了一個數字，我們的二叉搜索樹。
>> 如果我們可以添加的東西，我們最好是能夠刪除的東西。
不幸的是，對我們來說，刪除是一個有點複雜 -
雖然不大，但只是一點點。
有3種不同的情況下，我們要考慮的
刪除元素時，從二叉搜索樹。
首先，最簡單的情況是，該元素是一個葉節點。
在這種情況下，我們簡單地將其刪除，並繼續與我們的業務。
假設我們要刪除我們剛才添加的7。
好了，我們只要找到它，刪除它，就是這樣。
接下來的情況是，如果節點只有1名兒童。
在這裡，我們可以刪除該節點，但我們首先必須確保
連接的子樹，現在是離開父母雙亡的孤兒
節點的父節點，我們只是刪除了。
假設我們從我們的樹，要刪除3。
我們把該節點的子元素，並將它附加到節點的父節點。
在這種情況下，我們現在將1到5。
這沒有問題，因為我們知道，根據二叉搜索樹的性質，
3的左子樹，一切均小於5。
現在，3的子樹的照顧，我們可以將其刪除。
第三個和最後的情況是最複雜的。
這是我們要刪除的節點有2個孩子的情況下。
為了做到這一點，我們首先要找到的節點有一個最大的價值，
交換了兩下，然後刪除有問題的節點。
請注意，節點，下一個最大的值不能有2個孩子
因為它的左孩子為下一個最大的將是一個更好的人選。
因此，刪除一個節點有2個孩子，2個節點交換，
然後刪除處理由1 2上述規則。
例如，讓我們說，我們要刪除的根節點，13。
我們做的第一件事情是，我們發現在樹中的下一個最大的價值
其中，在這種情況下，為21。
然後，我們交換的2個節點，13葉和21個中心組節點。
現在，我們可以簡單地刪除13。
>> 正如前面提到的，有許多可能的方法來進行有效的二叉搜索樹。
不幸的是，對我們來說，有些是比別人差。
例如，會發生什麼事時，我們建立了一個二叉搜索樹
從排序列表中的號碼嗎？
所有的數字都只是添加到右邊的每一步。
當我們要搜索一個數字，
我們別無選擇，只有看的權利，在每一個步驟。
這是不是比在所有的線性搜索。
雖然我們不會掩蓋他們在這裡，還有其他更複雜的，
數據結構，確保不會發生這種情況。
然而，一個簡單的事情可以做，以避免這種情況的是
只是隨機洗牌的輸入值。
這是極不可能的，一個偶然的機會洗牌的數字列表進行排序。
如果是這樣的話，賭場會不會留在企業長久的。
>> 有你有它。
您現在所了解的二進制搜索和二叉搜索樹。
我是帕特里克·施密德，這是CS50。
[CS50.TV]
一個明顯的方法是將掃描列表... [嗶]
的項目數...是的
[笑]
...發布節點234 ... augh。
>>耶！這是 -