练习 23:三叉搜索树

原文:Exercise 23: Ternary Search Trees

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们将研究的最后一个数据结构称为三叉搜索树(TSTree),它可以在一组字符串中快速查找字符串。它类似于BSTree,但是它有三个子节点,而不是两个,每个子节点只是一个字符而不是整个字符串。在BSTree中,左子节点和右子节点是树的“小于”和“大于”的分支。在TSTree中,左子节点,中子节点和右子节点是“小于”,“等于”和“大于”的分支。这可以让你选取一个字符串,将其分解成字符,然后遍历TSTree,每次一个字符,直到找到它或者你到达了末尾。

通过将你要搜索的一组键拆成单个字符的节点,TSTree高效地使用空间换取时间。每一个这些节点将占用比BSTree更多的空间,但这允许你仅仅通过比较键中的字符来搜索键。使用BSTree,你必须比较每个节点的键和被搜索键中的大多数字符。使用TSTree,你只需要比较被搜索键的每个字母,当你到达末尾,就完成了。

TSTree的另一件不错的事情是,它知道一个键何时不存在于集合中。想象一下,你的键的长度为 10 个字符,你需要在一组其他的键中找到它,但是如果键不存在,则需要快速停止。使用TSTree,你可以在一到两个字符的地方停止,到达树的末尾,并且知道这个键不存在。你最多只能比较键中的 10 个字符来发现它,字符比较比BSTree少得多。

挑战练习

这个练习中,你打算完成另一个“代码大师复制”的一部分,之后独立完成TSTree。你所需的代码是:

  1. class TSTreeNode(object):
  2. def __init__(self, key, value, low, eq, high):
  3. self.key = key
  4. self.low = low
  5. self.eq = eq
  6. self.high = high
  7. self.value = value
  8. class TSTree(object):
  9. def __init__(self):
  10. self.root = None
  11. def _get(self, node, keys):
  12. key = keys[0]
  13. if key < node.key:
  14. return self._get(node.low, keys)
  15. elif key == node.key:
  16. if len(keys) > 1:
  17. return self._get(node.eq, keys[1:])
  18. else:
  19. return node.value
  20. else:
  21. return self._get(node.high, keys)
  22. def get(self, key):
  23. keys = [x for x in key]
  24. return self._get(self.root, keys)
  25. def _set(self, node, keys, value):
  26. next_key = keys[0]
  27. if not node:
  28. # what happens if you add the value here?
  29. node = TSTreeNode(next_key, None, None, None, None)
  30. if next_key < node.key:
  31. node.low = self._set(node.low, keys, value)
  32. elif next_key == node.key:
  33. if len(keys) > 1:
  34. node.eq = self._set(node.eq, keys[1:], value)
  35. else:
  36. # what happens if you DO NOT add the value here?
  37. node.value = value
  38. else:
  39. node.high = self._set(node.high, keys, value)
  40. return node
  41. def set(self, key, value):
  42. keys = [x for x in key]
  43. self.root = self._set(self.root, keys, value)

你需要使用你学到的“代码大师复制”方法学习。要特别注意如何处理node.eq路径以及如何设置node.value。一旦你了解了getset的工作方式,你将实现剩下的函数和所有的测试。要实现的函数有:

find_shortest

给定一个关键字K,找到以K开头的最短键/值对。这意味着如果你的set中有appleapplication ,那么调用find_shortest("appl")将返回关联apple的值。

find_longest

给定一个关键字K,找到以K开头的最长键/值对。这意味着如果你的set中有appleapplication ,那么调用find_shortest("appl")将返回关联application的值。

find_all

给定一个关键字K,找到以K开头的所有键/值对。我会先实现它,然后基于它实现find_shortestfind_longest

find_part

给定一个关键字K,找到最短的键,它拥有K的开头的一部分。研究如何以及在哪里设置node.value来使其生效。

研究性学习

  • 查看原始代码的注释,看看在_set过程中,在哪里放置value。修改它会修改get的含义吗?为什么?
  • 确保你使用随机数据来测试,并测量一些性能。
  • 你也可以在TSTree中进行模糊匹配。我认为这是一个附加题,所以尝试实现它们,看看你想出了什么。模糊匹配是,'a.p.e'匹配"apple""anpxe""ajpqe"
  • 如何搜索字符串的结尾?提示:不要过度考虑它。