## 練習 20：二叉搜索樹 > 原文：[Exercise 20: Binary Search Trees](https://learncodethehardway.org/more-python-book/ex20.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 在本練習中，我將讓你將數據結構的中文描述翻譯成工作代碼。你已經知道如何使用“大師復制”方法，分析算法或數據結構的代碼。你還可以了解如何閱讀算法的偽代碼描述。現在你將結合二者，并學習如何拆分一個相當松散的二進制搜索樹的英文描述。 我打算馬上開始，并提醒你，當你做這個練習的時候，不要訪問維基百科頁面。維基百科的二進制搜索樹描述擁有可以工作的 Python 代碼，因此它會使此練習失敗。如果你卡住了，那么你可以閱讀任何你可以使用的資源，但是首先嘗試按照這里我的描述來實現。 ## 二叉搜索樹 在練習 16 中，你了解了“歸并排序”接受扁平的鏈表，將其轉換為已排序部分的樹。它將列表切成小塊，然后通過排序左側較小值的部分，以及右側較大值的部分，將其重新組合在一起。在某種程度上，二叉搜索樹（`BSTree`）是一種數據結構，本身就是有序的，并且不會使用列表來儲存元素。`BSTree`的一個主要用途是，用一棵樹來組織`key = value`節點的偶對，在你插入或者刪除它們的時候，保持它們有序。 最開始，`BSTree`擁有一個`key=value`根節點，它擁有左子節點或者右子節點（都是鏈接）。如果插入一個新的`key=value`，那么`BSTree`的任務是，從根節點開始，將`key`與每一個節點進行比較：如果新的鍵小于或等于它，走左邊；如果新的鍵大于它，走右邊。最終，`BSTree`在樹中找到一個位置，如果你遵循原始路徑，你應該按照相同的過程找到它。之后的所有操作都是一樣的，通過將任何鍵與每個節點，左移或者右移，直到找到節點或到達末尾。 這樣，`BSTree`是練習 17 中的`Dictionary`的替代品，因此它應該具有相同的操作。基本的`BSTreeNode`將需要`left`，`right`，`key`和`value`屬性來創建樹結構。你可能還需要`parent`屬性，具體取決于你如何執行此操作。（譯者注：如果你在遍歷過程中記錄父節點，就不用這個屬性。）然后，`BSTree`需要在根 `BSTreeNode`上進行以下操作： > `get` > 提供一個鍵，遍歷樹，找到節點，或者如果到達末尾，返回`None`。如果提供的鍵是小于等于節點的鍵，走左邊。如果鍵大于節點的鍵，走右邊。如果你碰到一個沒有左子節點或右子節點的節點，那么你已經遍歷完了，并且該節點不存在。可以使用遞歸或使用`while`循環。 > `set` > 這和`get`幾乎一樣，除了一旦你到達末尾的節點，你只需將一個新的`BSTreeNode`掛載到左子節點或右子節點，從而將樹向下延伸了一個分支。 > `delete` > 從`BSTree`刪除節點是一個復雜的操作，所以我有一個完整的部分只是講刪除。簡而言之有三個情況：節點是葉子（沒有子節點），有一個子節點，或者有兩個子節點。如果它是葉子，那么只是刪除它。如果有一個子節點，然后將其替換為子節點。如果它有兩個子節點，那么它變得非常復雜，因此請閱讀下面刪除的部分。 > `list` > 遍歷樹，打印一切東西。`list `的重要內容是，你可以以不同的方式遍歷樹，Kauai產生不同的輸出。如果你遍歷`left`，之后是`right`，那么你會得到一些不同于反著執行的東西。如果你走了所有到底部的路，然后當你朝著`root`向上走的時候，打印結果，你會得到另一種類型的輸出。你也可以在向下遍歷樹的時候打印節點，從`root`到“葉子”。嘗試不同的風格，看看它們都做了什么。 ## 刪除 記住，刪除節點時我們需要處理三個情況（我稱之為`D`）： + `D`節點是“葉子”節點，因為它有沒有子節點（左子節點或者右子節點）。只需從父節點刪除它。 + `D`節點只有一個子節點（左子節點或者右子節點，但不是二者）。在這種情況下，你可以將該子節點的值移動到`D`節點，然后刪除該子節點。這有效地替換了`D`節點與子節點（或“將子節點向上移動”）。 + `D`節點有左子節點和右子節點，這意味著這時候需要做一些大的操作。首先，找到的`D.right`節點的最小子節點，成為`successor`。將`D.key`賦為`successor.key`，然后對`successor`的子節點使用它的鍵，做相同的刪除操作。 你最有可能還需要`find_minimum`和`replace_node_in_parent`操作，來執行這兩個操作。我提到你可能需要`parent `屬性，具體取決于你實現它的方式。我會假設使用`parent `節點，因為這在大多數情況下更容易。 > 注意 > 每個人都討厭樹的刪除操作。這是一個復雜的操作，甚至是我最喜歡的參考書，Steven S. Skiena 的[《算法設計手冊》](http://amzn.to/2qIA3ai)都跳過了它，因為實現“看起來有點可怕”。如果你很難弄清楚`delete`，不要氣餒。 ## 挑戰練習 你將使用這個故意模糊的描述實現你的`BSTree`。當你第一次嘗試時，嘗試不要看太多的參考，然后當你卡住時，去閱讀他人的實現方式。這個練習的重點是，嘗試從一個糟糕的描述中解決一個復雜的問題。 解決這個問題的竅門是，首先將英文段落翻譯成粗糙的偽代碼。然后將粗糙的偽代碼轉換為更精確的偽代碼。一旦你有了更精確的偽代碼，你可以把它翻譯成 Python 代碼。特別注意具體的單詞，例如單個英文單詞可能意味著 Python 中的很多東西。有時你只需要猜測并運行你的測試，看看是否正確。 測試也非常重要，對這個問題應用“測試第一”的方法，可能是一個好主意。你知道這些操作應該做什么，所以你可以為它編寫一個測試，然后讓測試工作。 ## 研究性學習 + 你是否可以開發一個病態的測試，以某種方式插入元素，使`BSTree`只不過是一個花式鏈表？ + 當你嘗試刪除這個`BSTree`的“極點”時，會發生什么？ + 與你的最近優化的`Dictionary`相比，`BSTree`的速度如何？ + 使用你的性能分析和調整流程，你能多快實現`BSTree`？