# 練習 23：三叉搜索樹 > 原文：[Exercise 23: Ternary Search Trees](https://learncodethehardway.org/more-python-book/ex23.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 我們將研究的最后一個數據結構稱為三叉搜索樹（TSTree），它可以在一組字符串中快速查找字符串。它類似于`BSTree`，但是它有三個子節點，而不是兩個，每個子節點只是一個字符而不是整個字符串。在`BSTree`中，左子節點和右子節點是樹的“小于”和“大于”的分支。在`TSTree`中，左子節點，中子節點和右子節點是“小于”，“等于”和“大于”的分支。這可以讓你選取一個字符串，將其分解成字符，然后遍歷`TSTree`，每次一個字符，直到找到它或者你到達了末尾。 通過將你要搜索的一組鍵拆成單個字符的節點，`TSTree`高效地使用空間換取時間。每一個這些節點將占用比`BSTree`更多的空間，但這允許你僅僅通過比較鍵中的字符來搜索鍵。使用`BSTree`，你必須比較每個節點的鍵和被搜索鍵中的大多數字符。使用`TSTree`，你只需要比較被搜索鍵的每個字母，當你到達末尾，就完成了。 `TSTree`的另一件不錯的事情是，它知道一個鍵何時不存在于集合中。想象一下，你的鍵的長度為 10 個字符，你需要在一組其他的鍵中找到它，但是如果鍵不存在，則需要快速停止。使用`TSTree`，你可以在一到兩個字符的地方停止，到達樹的末尾，并且知道這個鍵不存在。你最多只能比較鍵中的 10 個字符來發現它，字符比較比`BSTree`少得多。 ## 挑戰練習 這個練習中，你打算完成另一個“代碼大師復制”的一部分，之后獨立完成`TSTree `。你所需的代碼是： ```py class TSTreeNode(object): def __init__(self, key, value, low, eq, high): self.key = key self.low = low self.eq = eq self.high = high self.value = value class TSTree(object): def __init__(self): self.root = None def _get(self, node, keys): key = keys[0] if key < node.key: return self._get(node.low, keys) elif key == node.key: if len(keys) > 1: return self._get(node.eq, keys[1:]) else: return node.value else: return self._get(node.high, keys) def get(self, key): keys = [x for x in key] return self._get(self.root, keys) def _set(self, node, keys, value): next_key = keys[0] if not node: # what happens if you add the value here? node = TSTreeNode(next_key, None, None, None, None) if next_key < node.key: node.low = self._set(node.low, keys, value) elif next_key == node.key: if len(keys) > 1: node.eq = self._set(node.eq, keys[1:], value) else: # what happens if you DO NOT add the value here? node.value = value else: node.high = self._set(node.high, keys, value) return node def set(self, key, value): keys = [x for x in key] self.root = self._set(self.root, keys, value) ``` 你需要使用你學到的“代碼大師復制”方法學習。要特別注意如何處理`node.eq`路徑以及如何設置`node.value`。一旦你了解了`get`和`set`的工作方式，你將實現剩下的函數和所有的測試。要實現的函數有： > `find_shortest` > 給定一個關鍵字`K`，找到以`K`開頭的最短鍵/值對。這意味著如果你的`set`中有`apple`和`application` ，那么調用`find_shortest("appl")`將返回關聯`apple`的值。 > `find_longest` > 給定一個關鍵字`K`，找到以`K`開頭的最長鍵/值對。這意味著如果你的`set`中有`apple`和`application` ，那么調用`find_shortest("appl")`將返回關聯`application`的值。 > `find_all` > 給定一個關鍵字`K`，找到以`K`開頭的所有鍵/值對。我會先實現它，然后基于它實現`find_shortest`和`find_longest`。 > `find_part` > 給定一個關鍵字`K`，找到最短的鍵，它擁有`K`的開頭的一部分。研究如何以及在哪里設置`node.value`來使其生效。 ## 研究性學習 + 查看原始代碼的注釋，看看在`_set`過程中，在哪里放置`value`。修改它會修改`get`的含義嗎？為什么？ + 確保你使用隨機數據來測試，并測量一些性能。 + 你也可以在`TSTree`中進行模糊匹配。我認為這是一個附加題，所以嘗試實現它們，看看你想出了什么。模糊匹配是，`'a.p.e'`匹配`"apple"`、`"anpxe"`和`"ajpqe"`。 + 如何搜索字符串的結尾？提示：不要過度考慮它。