練習 23：三叉搜索樹
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
我們將研究的最后一個數(shù)據(jù)結(jié)構(gòu)稱為三叉搜索樹（TSTree）紊撕，它可以在一組字符串中快速查找字符串。它類似于BSTree，但是它有三個子節(jié)點，而不是兩個，每個子節(jié)點只是一個字符而不是整個字符串蔓肯。在BSTree中阀参，左子節(jié)點和右子節(jié)點是樹的“小于”和“大于”的分支鸣皂。在TSTree中摔踱，左子節(jié)點虐先，中子節(jié)點和右子節(jié)點是“小于”，“等于”和“大于”的分支派敷。這可以讓你選取一個字符串蛹批，將其分解成字符，然后遍歷TSTree篮愉，每次一個字符腐芍，直到找到它或者你到達了末尾。
通過將你要搜索的一組鍵拆成單個字符的節(jié)點试躏，TSTree高效地使用空間換取時間猪勇。每一個這些節(jié)點將占用比BSTree更多的空間，但這允許你僅僅通過比較鍵中的字符來搜索鍵颠蕴。使用BSTree泣刹，你必須比較每個節(jié)點的鍵和被搜索鍵中的大多數(shù)字符。使用TSTree裁替，你只需要比較被搜索鍵的每個字母项玛，當你到達末尾，就完成了弱判。
TSTree的另一件不錯的事情是襟沮，它知道一個鍵何時不存在于集合中。想象一下昌腰，你的鍵的長度為 10 個字符开伏，你需要在一組其他的鍵中找到它，但是如果鍵不存在遭商，則需要快速停止固灵。使用TSTree，你可以在一到兩個字符的地方停止劫流，到達樹的末尾巫玻，并且知道這個鍵不存在。你最多只能比較鍵中的 10 個字符來發(fā)現(xiàn)它祠汇，字符比較比BSTree少得多仍秤。
挑戰(zhàn)練習
這個練習中，你打算完成另一個“代碼大師復(fù)制”的一部分可很，之后獨立完成TSTree诗力。你所需的代碼是：
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)
你需要使用你學到的“代碼大師復(fù)制”方法學習。要特別注意如何處理node.eq路徑以及如何設(shè)置node.value我抠。一旦你了解了get和set的工作方式苇本，你將實現(xiàn)剩下的函數(shù)和所有的測試袜茧。要實現(xiàn)的函數(shù)有：
find_shortest
給定一個關(guān)鍵字
K，找到以K開頭的最短鍵/值對瓣窄。這意味著如果你的set中有apple和application笛厦，那么調(diào)用find_shortest("appl")將返回關(guān)聯(lián)apple的值。
find_longest
給定一個關(guān)鍵字
K康栈，找到以K開頭的最長鍵/值對递递。這意味著如果你的set中有apple和application，那么調(diào)用find_shortest("appl")將返回關(guān)聯(lián)application的值啥么。
find_all
給定一個關(guān)鍵字
K登舞，找到以K開頭的所有鍵/值對。我會先實現(xiàn)它悬荣，然后基于它實現(xiàn)find_shortest和find_longest菠秒。
find_part
給定一個關(guān)鍵字
K，找到最短的鍵氯迂，它擁有K的開頭的一部分践叠。研究如何以及在哪里設(shè)置node.value來使其生效。
研究性學習
- 查看原始代碼的注釋嚼蚀，看看在
_set過程中禁灼，在哪里放置value。修改它會修改get的含義嗎轿曙？為什么弄捕？ - 確保你使用隨機數(shù)據(jù)來測試，并測量一些性能导帝。
- 你也可以在
TSTree中進行模糊匹配守谓。我認為這是一個附加題，所以嘗試實現(xiàn)它們您单，看看你想出了什么斋荞。模糊匹配是，'a.p.e'匹配"apple"虐秦、"anpxe"和"ajpqe"平酿。 - 如何搜索字符串的結(jié)尾？提示：不要過度考慮它悦陋。
