第十三章二叉搜索樹 · 數據結構思維中文版

# 第十三章二叉搜索樹 > 原文：[Chapter 13 Binary search tree](http://greenteapress.com/thinkdast/html/thinkdast014.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 本章介紹了上一個練習的解決方案，然后測試樹形映射的性能。我展示了一個實現的問題，并解釋了 Java 的`TreeMap`如何解決它。 ## 13.1 簡單的`MyTreeMap` 上一個練習中，我給了你`MyTreeMap`的大綱，并讓你填充缺失的方法。現在我會展示結果，從`findNode`開始： ```java private Node findNode(Object target) { // some implementations can handle null as a key, but not this one if (target == null) { throw new IllegalArgumentException(); } // something to make the compiler happy @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) target; // the actual search Node node = root; while (node != null) { int cmp = k.compareTo(node.key); if (cmp < 0) node = node.left; else if (cmp > 0) node = node.right; else return node; } return null; } ``` `findNode`是`containsKey`和`get`所使用的一個私有方法；它不是`Map`接口的一部分。參數`target`是我們要查找的鍵。我在上一個練習中解釋了這種方法的第一部分： + 在這個實現中，`null`不是鍵的合法值。 + 在我們可以在`target`上調用`compareTo`之前，我們必須把它強制轉換為某種形式的`Comparable`。這里使用的“類型通配符”會盡可能允許；也就是說，它適用于任何實現`Comparable`類型，并且它的`compareTo`接受`K`或者任和`K`的超類。之后，實際搜索比較簡單。我們初始化一個循環變量`node`來引用根節點。每次循環中，我們將目標與`node.key`比較。如果目標小于當前鍵，我們移動到左子樹。如果它更大，我們移動到右子樹。如果相等，我們返回當前節點。如果在沒有找到目標的情況下，我們到達樹的底部，我就認為，它不在樹中并返回`null`。 ## 13.2 搜索值我在前面的練習中解釋了，`findNode`運行時間與樹的高度成正比，而不是節點的數量，因為我們不必搜索整個樹。但是對于`containsValue`，我們必須搜索值，而不是鍵；BST 的特性不適用于值，因此我們必須搜索整個樹。我的解法是遞歸的： ```java public boolean containsValue(Object target) { return containsValueHelper(root, target); } private boolean containsValueHelper(Node node, Object target) { if (node == null) { return false; } if (equals(target, node.value)) { return true; } if (containsValueHelper(node.left, target)) { return true; } if (containsValueHelper(node.right, target)) { return true; } return false; } ``` `containsValue`將目標值作為參數，并立即調用`containsValueHelper`，傳遞樹的根節點作為附加參數。這是`containsValueHelper`的工作原理： + 第一個`if`語句檢查遞歸的邊界情況。如果`node`是`null`，那意味著我們已經遞歸到樹的底部，沒有找到`target`，所以我們應該返回`false`。請注意，這只意味著目標沒有出現在樹的一條路徑上；它仍然可能會在另一條路徑上被發現。 + 第二種情況檢查我們是否找到了我們正在尋找的東西。如果是這樣，我們返回`true`。否則，我們必須繼續。 + 第三種情況是執行遞歸調用，在左子樹中搜索`target`。如果我們找到它，我們可以立即返回`true`，而不搜索右子樹。否則我們繼續。 + 第四種情況是搜索右子樹。同樣，如果我們找到我們正在尋找的東西，我們返回`true`。否則，我們搜索完了整棵樹，返回`false`。該方法“訪問”了樹中的每個節點，所以它的所需時間與節點數成正比。 ## 13.3 實現`put` `put`方法比起`get`要復雜一些，因為要處理兩種情況：（1）如果給定的鍵已經在樹中，則替換并返回舊值；（2）否則必須在樹中添加一個新的節點，在正確的地方。在上一個練習中，我提供了這個起始代碼： ```java public V put(K key, V value) { if (key == null) { throw new IllegalArgumentException(); } if (root == null) { root = new Node(key, value); size++; return null; } return putHelper(root, key, value); } ``` 并且讓你填充`putHelper`。這里是我的答案： ```java private V putHelper(Node node, K key, V value) { Comparable<? super K> k = (Comparable<? super K>) key; int cmp = k.compareTo(node.key); if (cmp < 0) { if (node.left == null) { node.left = new Node(key, value); size++; return null; } else { return putHelper(node.left, key, value); } } if (cmp > 0) { if (node.right == null) { node.right = new Node(key, value); size++; return null; } else { return putHelper(node.right, key, value); } } V oldValue = node.value; node.value = value; return oldValue; } ``` 第一個參數`node`最初是樹的根，但是每次我們執行遞歸調用，它指向了不同的子樹。就像`get`一樣，我們用`compareTo`方法來弄清楚，跟隨哪一條樹的路徑。如果`cmp < 0`，我們添加的鍵小于`node.key`，那么我們要走左子樹。有兩種情況： + 如果左子樹為空，那就是，如果`node.left`是`null`，我們已經到達樹的底部而沒有找到`key`。這個時候，我們知道`key`不在樹上，我們知道它應該放在哪里。所以我們創建一個新節點，并將它添加為`node`的左子樹。 + 否則我們進行遞歸調用來搜索左子樹。如果`cmp > 0`，我們添加的鍵大于`node.key`，那么我們要走右子樹。我們處理的兩個案例與上一個分支相同。最后，如果`cmp == 0`，我們在樹中找到了鍵，那么我們更改它并返回舊的值。我使用遞歸編寫了這個方法，使它更易于閱讀，但它可以直接用迭代重寫一遍，你可能想留作練習。 ## 13.4 中序遍歷我要求你編寫的最后一個方法是`keySet`，它返回一個`Set`，按升序包含樹中的鍵。在其他`Map`實現中，`keySet`返回的鍵沒有特定的順序，但是樹形實現的一個功能是，對鍵進行簡單而有效的排序。所以我們應該利用它。這是我的答案： ```java public Set<K> keySet() { Set<K> set = new LinkedHashSet<K>(); addInOrder(root, set); return set; } private void addInOrder(Node node, Set<K> set) { if (node == null) return; addInOrder(node.left, set); set.add(node.key); addInOrder(node.right, set); } ``` 在`keySet`中，我們創建一個`LinkedHashSet`，這是一個`Set`實現，使元素保持有序（與大多數其他`Set`實現不同）。然后我們調用`addInOrder`來遍歷樹。第一個參數`node`最初是樹的根，但正如你的期望，我們用它來遞歸地遍歷樹。`addInOrder`對樹執行經典的“中序遍歷”。如果`node`是`null`，這意味著子樹是空的，所以我們返回，而不向`set`添加任何東西。否則我們： 1. 按順序遍歷左子樹。 1. 添加`node.key`。 1. 按順序遍歷右子樹。請記住，BST 的特性保證左子樹中的所有節點都小于`node.key`，并且右子樹中的所有節點都更大。所以我們知道，`node.key`已按正確的順序添加。遞歸地應用相同的參數，我們知道左子樹中的元素是有序的，右子樹中的元素也一樣。并且邊界情況是正確的：如果子樹為空，則不添加任何鍵。所以我們可以認為，該方法以正確的順序添加所有鍵。因為`containsValue`方法訪問樹中的每個節點，所以所需時間與`n`成正比。 ## 13.5 對數時間的方法在`MyTreeMap`中，`get`和`put`方法所需時間與樹的高度`h`成正比。在上一個練習中，我們展示了如果樹是滿的 - 如果樹的每一層都包含最大數量的節點 - 樹的高度與`log n`成橫臂。我也說了，`get`和`put`是對數時間的；也就是說，他們的所需時間與`logn`成正比。但是對于大多數應用程序，不能保證樹是滿的。一般來說，樹的形狀取決于鍵和添加順序。為了看看這在實踐中是怎么回事，我們將用兩個樣本數據集來測試我們的實現：隨機字符串的列表和升序的時間戳列表。這是生成隨機字符串的代碼： ```java Map<String, Integer> map = new MyTreeMap<String, Integer>(); for (int i=0; i<n; i++) { String uuid = UUID.randomUUID().toString(); map.put(uuid, 0); } ``` `UUID`是`java.util`中的類，可以生成隨機的“通用唯一標識符”。UUID 對于各種應用是有用的，但在這個例子中，我們利用一種簡單的方法來生成隨機字符串。我使用`n=16384`來運行這個代碼，并測量了最后的樹的運行時間和高度。以下是輸出： ``` Time in milliseconds = 151 Final size of MyTreeMap = 16384 log base 2 of size of MyTreeMap = 14.0 Final height of MyTreeMap = 33 ``` 我包含了“`MyTreeMap`大小的`2`為底的對數”，看看如果它已滿，樹將是多高。結果表明，高度為`14`的完整樹包含`16384`個節點。隨機字符串的樹高度實際為33，這遠大于理論上的最小值，但不是太差。要查找`16,384`個鍵中的一個，我們只需要進行`33`次比較。與線性搜索相比，速度快了近`500`倍。這種性能通常是隨機字符串，或其他不按照特定順序添加的鍵。樹的最終高度可能是理論最小值的`2~3`倍，但它仍然與`log n`成正比，這遠小于`n`。事實上，隨著`n`的增加，`logn`會慢慢增加，在實踐中，可能很難將對數時間與常數時間區分開。然而，二叉搜索樹并不總是表現良好。讓我們看看，當我們以升序添加鍵時會發生什么。下面是一個示例，以微秒為單位測量時間戳，并將其用作鍵： ```java MyTreeMap<String, Integer> map = new MyTreeMap<String, Integer>(); for (int i=0; i<n; i++) { String timestamp = Long.toString(System.nanoTime()); map.put(timestamp, 0); } ``` `System.nanoTime`返回一個`long`類型的整數，表示以微秒為單位的啟動時間。每次我們調用它時，我們得到一個更大的數字。當我們將這些時間戳轉換為字符串時，它們按字典序增加。讓我們看看當我們運行它時會發生什么： ```java Time in milliseconds = 1158 Final size of MyTreeMap = 16384 log base 2 of size of MyTreeMap = 14.0 Final height of MyTreeMap = 16384 ``` 運行時間是以前的時間的七倍多。時間更長。如果你想知道為什么，看看樹的最后的高度：`16384`！ ![](https://img.kancloud.cn/4a/d0/4ad05c266542a0f472ea804f6c8ea003_680x229.jpg) 圖 13.1：二叉搜索樹，平衡（左邊）和不平衡（右邊）如果你思考`put`如何工作，你可以弄清楚發生了什么。每次添加一個新的鍵時，它都大于樹中的所有鍵，所以我們總是選擇右子樹，并且總是將新節點添加為，最右邊的節點的右子節點。結果是一個“不平衡”的樹，只包含右子節點。這種樹的高度正比于`n`，不是`logn`，所以`get`和`put`的性能是線性的，不是對數的。圖 13.1 顯示了平衡和不平衡樹的示例。在平衡樹中，高度為`4`，節點總數為`2^4 - 1 = 15`。在節點數相同的不平衡樹中，高度為`15`。 ## 13.6 自平衡樹這個問題有兩種可能的解決方案：你可以避免向`Map`按順序添加鍵。但這并不總是可能的。你可以制作一棵樹，如果碰巧按順序處理鍵，那么它會更好地處理鍵。第二個解決方案是更好的，有幾種方法可以做到。最常見的是修改`put`，以便它檢測樹何時開始變得不平衡，如果是，則重新排列節點。具有這種能力的樹被稱為“自平衡樹”。普通的自平衡樹包括 AVL 樹（“AVL”是發明者的縮寫），以及紅黑樹，這是 Java`TreeMap`所使用的。在我們的示例代碼中，如果我們用 Java 的`MyTreeMap`替換，隨機字符串和時間戳的運行時間大致相同。實際上，時間戳運行速度更快，即使它們有序，可能是因為它們花費的時間較少。總而言之，二叉搜索樹可以以對數時間實現`get`和`put`，但是只能按照使得樹足夠平衡的順序添加鍵。自平衡樹通過每次添加新鍵時，進行一些額外的工作來避免這個問題。你可以在 <http://thinkdast.com/balancing> 上閱讀自平衡樹的更多信息。 ## 13.7 更多練習在上一個練習中，你不必實現`remove`，但你可能需要嘗試。如果從樹中央刪除節點，則必須重新排列剩余的節點，來恢復 BST 的特性。你可以自己弄清楚如何實現，或者你可以閱讀 <http://thinkdast.com/bstdel> 上的說明。刪除一個節點并重新平衡一個樹是類似的操作：如果你做這個練習，你將更好地了解自平衡樹如何工作。