在实践中，只要注意插入和删除数据的顺序，二叉搜索树通常都将会提供非常好的性能 。对于特别偏执的人来说，有一些非常有名的技术（见13.3节）可以被用来实现二叉树，从而保证在插入和删除操作之后，树结构依然平衡 。
7.6 使用二叉搜索树（BST）来实现映射（选读）上一节里，我们描述了如何让BST对象实现类似于有序集合的实现 。因此，我们可以插入元素、删除元素、检查元素是否存在，以及按照排序顺序来获取里面的元素 。树结构通常来说会在类似于数据库的应用程序里被用到 。在这样的程序里，我们不仅会想要知道特定的元素是不是在集合里，而且还要能够查找出具有某些特定表征的元素 。举一个简单的例子，我们可能会需要维护俱乐部会员的名单 。很明显，我们需要能够添加和删除俱乐部的成员，但我们还需要更多的东西 。比如，我们需要一种可以用来为俱乐部的特定成员提供记录的方法，例如获取他们的电话号码 。
【实现树结构的基本算法和相应的数据结构】在这一节里，我们将会了解如何扩展二叉搜索树的功能，来实现类似于Python字典那样通用的映射 。在我们的成员列表示例中，我们使用了由成员名称构造的特殊“键”值，从而能够查找它的数据记录 。假设我们有一个合适的membershipList对象，我们可以通过下面这些代码得到一个人的电话号码：
...info = membershipList["VanRossum, Guido"]print info.home_phone在这里，我们的membershipList是一个映射对象，它把成员的名称和他的具体信息的相应记录进行了映射 。我们可以使用Python字典来完成这项任务，但是字典是一种无序的映射 。而且，我们也还希望能够按照一定的顺序来高效地输出我们的（巨大的！）成员列表 。
解决这个问题的一种方案是重写整个BST类，从而能够让它的所有方法都有一个额外的参数，这个参数被用来获取键 。同时，这些方法还需要在执行的过程中维护这个键值对组成的树结构 。虽然，这比我们真正需要做的工作要多得多，我们还是可以通过使用现有的BST类来实现 。我们可以通过一个包装这个类的包装器来实现通用映射接口，从而获得类似的效果 。这样一来，我们在获得基于树结构的映射对象的优点时，不需要去修改BST类或者复制出另外一个BST类 。一般来说，只要有可能，我们都应该扩展现有的代码，它通常会比复制或修改现有代码的效果更好 。
那么我们如何将这个BST类从一个集合转变为映射呢？这里的关键是利用BST类里已经包含了的现成的排序和查找功能 。我们的BST类可以被用来存储任何可以被比较的对象 。我们将会把集合里的元素存储为键值对，但诀窍是这些元素将会根据它的键进行排序 。因此，第一步是创建一个新的类来表示这些键值对元素 。我们将这个组合元素称为KeyPair 。同时，为了使我们的KeyPair类可以被比较，我们还需要实现一些与比较相关的操作 。
# KeyPair.pyclass KeyPair(object):def __init__(self, key, value=https://www.isolves.com/it/cxkf/sf/2020-06-01/None):self.key = keyself.value = valuedef __eq__(self, other):return self.key == other.keydef __lt__(self, other):return self.key < other.keydef __gt__(self, other):return self.key > other.key在这里，我们只实现了6个比较运算符中的3个，这是因为BST类里的所有方法都只会用到这些比较运算符 。当然，为了安全起见，以防将来BST类的代码发生变化，我们还是应该尽量地去实现其他3个比较运算符 。我们将会把这部分内容作为练习题留给你 。
有了这个KeyPair类之后，我们现在就可以定义一个基于BST类的字典映射了 。这是我们的类的构造函数：
# TreeMap.pyfrom BST import BSTfrom KeyPair import KeyPairclass TreeMap(object):def __init__(self, items=()):self.items = BST()for key, value in items:self.items.insert(KeyPair(key, value))在这段代码里，我们使用了实例变量items来保存将会被用来储存我们的KeyPair元素的BST对象 。正如Python字典可以使用一个序列对其进行初始化一样，我们也允许TreeMap类的构造函数接受一个序列对 。对于这个参数，我们只需要遍历这些数据对，然后调用BST类的insert操作来填充我们的树 。当然，insert方法将会根据键的数据来保持底层二叉搜索树的顺序，而这正是因为我们为KeyPair类实现了相互比较的方法 。
一旦KeyPair对象进入到了我们的BST对象，我们需要能够通过它的键的数据来再次检索它 。这时，我们可以使用BST类的find操作来完成这个任务 。我们将会提供给find操作的参数是一个新的KeyPair对象，它将会等同于我们正在查找的KeyPair（具有相同的键） 。因此，像下面这样的一行代码，就能够解决这个问题：
推荐阅读
- 在生意参谋中通过以下哪个模块可以查看竞品的流量结构 在生意参谋中通过以下哪个模块可以查看竞品的流量结构
- centos7目录结构 理解各个目录的功能
- 茶树菇怎么保存呢,茶树菇怎么炒好吃
- MAC如何实现屏幕缩放
- 懂过古树的口感特点,懂过古茶山
- 成年老茶的别样滋味,新品上市2015老同志深山老树茶生茶上市
- 茶树菇炒羊肉的做法,茶树菇炒里脊肉的做法
- 茶香胡乱炖的做法,茶树菇炖柴鸡的做法
- 倒茶也能端庄大雅,2012年中茶牌布朗大树开汤品鉴
- 茶树菇有哪些功效禁忌,百合菊花茶的功效和禁忌有多少