[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。 >>耶！這是 -