6.7　创建一种新的集合

创建一个全新的集合需要一些准备工作。需要有新的算法或者新的内部数据结构，它们能够为内置的集合带来重大的改进。在设计新的集合之前，用“Big-O”计算复杂度是非常重要的。在实现了新的集合之后，用timeit确保新的集合确实改进了内置的集合也是非常重要的。

例如，我们或许想要创建一个二叉搜索树（binary search tree）结构用来让所有的元数据都按正确的顺序存储。由于我们希望这是一个可变的结构，因此在设计时必须做下面的几件事。

• 设计基本的二叉搜索树结构。
• 决定使用MutableSequence、MutableMapping还是MutableSet结构作为基类。
• 参考Python基本库文档的8.4.1节，了解collection.abc的集合中有哪些特殊方法。

一个二叉搜索树的节点有两个分支：一个是“小于”分支，用于存放所有小于当前节点的键；另一个是“大于等于”分支，用于存放所有大于或者等于当前节点的键。

我们需要仔细研究如何让我们的集合与Python的抽象基类合理地集成。

• 这不会是一个庞大的序列，因为在二叉搜索树中我们通常不使用索引。通常都是使用键来引用对应元素。但是，强制实现一个整数索引页不是难事。
• 它可以作为一个映射的键，可以让所有的键按顺序存储。这是二叉搜索树的一个常见用途。
• 它可以很好地代替set和Counter类，因为它能够接受多个不同类型的元素，这让我们可以很容易地将它实现成一种类似于包的结构。

我们会介绍如何实现一个有序的多重集合（或者叫包）。这个结构可以存储一个对象的多份备份。它只是依赖于对象间相对简单的比较测试。

这是一个比较复杂的设计，它包括了很多细节。为了能对二叉搜索树有一个基本了解，阅读类似于http://en.wikipedia.org/wiki/Binary_search_tree上面的文章是非常重要的。在前面的维基百科的末页有许多外部的链接，它们提供了关于二叉搜索树的更多信息。阅读一些书对学习基本的算法是非常重要的，例如Cormen、Leiserson、Rivest和Stein所著的Introduction to Algorithms，Aho、Ullman和Hopcroft所著的Data Structures and Algorithms，或者Steven Skiena所著的The Algorithm Design Manual。

6.7.1　一些设计原则

我们会将集合分成两个类：TreeNode和Tree。

TreeNode类会包含所有的元素和more、less和parent引用。我们也会将一些其他功能放在这个类中。

例如，为了能够使用contains()或者discard()搜索一个特定的元素会用一个简单的递归将这个搜索工作委托给节点自身来完成，算法的描述如下。

• 如果目前元素和当前元素相等，那么返回self。
• 如果目标元素比self.item小，那么递归地使用less.find(target item)继续搜索目标元素。
• 如果目标元素比self.item大，那么递归地使用more.find(target.item)继续搜索目标元素。

我们用类似的方式将更多维护树结构的工作委托给TreeNode类完成。

第2个类会使用外观模式（Facade）定义Tree。外观模式也被成为包装模式（Wrapper），主要目的是为一个特定的接口增加属性。我们会为MutableSet抽象基类提供必要的外部接口。

如果空的根节点在比较中总是小于所有其他的键，这个算法会变得更简单，但是在Python中这样做有一些困难。因为我们无法提前知道节点会是哪种数值类型，所以我们没有办法容易地为根节点定义一个最小值。相反，我们将使用特殊值None并且接受用if语句检测根节点所带来的开销。

6.7.2　定义Tree类

这是MutableSet类的一个扩展的主要代码，它提供了所必需的最小方法集。

class Tree(collections.abc.MutableSet):
　　def init( self, iterable=None ):
　　　　self.root= TreeNode(None)
　　　　self.size= 0
　　　　if iterable:
　　　　　　for item in iterable:
　　　　　　　　self.root.add( item )
　　def add( self, item ):
　　　　self.root.add( item )
　　　　self.size += 1
　　def discard( self, item ):
　　　　try:
　　　　　　self.root.more.remove( item )
　　　　　　self.size -= 1
　　　　except KeyError:
　　　　　　pass
　　def contains( self, item ):
　　　　try:
　　　　　　self.root.more.find( item )
　　　　　　return True
　　　　except KeyError:
　　　　　　return False
　　def iter( self ):
　　　　for item in iter(self.root.more):
　　　　　　yield item
　　def len( self ):
　　　　return self.size

初始化方法和Counter对象类似，这个类会接受一个可迭代对象作为参数，并加载对象中的所有元素。

add()和discard()方法会持续更新节点总数。这样当我们需要知道当前节点总数时，就不用遍历整棵树。这些方法也将工作委托给了位于根部的TreeNode对象。

contains()特殊方法会执行递归查找。当发生KeyError异常时，它会返回False。

iter()特殊方法是一个生成器函数。它也将实际的工作委托给了TreeNode类的递归迭代器。

我们定义了discard()，当试图忽略不存在的键时，可变集合需要这个方法可以忽略异常。抽象基类中提供了一个remove()的默认实现，当一个键不存在时会抛出一个异常。两个方法函数都必须定义，我们基于remove()定义了discard()，但是会忽略键不存在时remove()抛出的异常。在一些情况下，基于discard()定义remove()可能会更容易，如果发现问题就抛出一个异常。

6.7.3　定义TreeNode类

整个Tree类都是依赖于TreeNode类来处理添加、删除和迭代包中的不同元素。这个类比较大，所以我们会分3个部分展示它。

这里是第1部分，包括查找和迭代节点。

import weakref
class TreeNode:
　　def init( self, item, less=None, more=None, parent=None ):
　　　　self.item= item
　　　　self.less= less
　　　　self.more= more
　　　　if parent != None:
　　　　　　self.parent = parent
　　@property
　　def parent( self ):
　　　　return self.parentref()
　　@parent.setter
　　def parent( self, value ):
　　　　self.parentref= weakref.ref(value)
　　def repr( self ):
　　　　return( "TreeNode({item!r},{less!r},{more!r})".format(
　　　　　**self.dict ) )
　　def find( self, item ):
　　　　if self.item is None: # Root
　　　　　　if self.more: return self.more.find(item)
　　　　elif self.item == item: return self
　　　　elif self.item > item and self.less: return
　　　　　　self.less.find(item)
　　　　elif self.item < item and self.more: return
　　　　　　self.more.find(item)
　　　　raise KeyError
　　def __iter( self ):
　　　　if self.less:
　　　　　　for item in iter(self.less):
　　　　　　　　yield item
　　　　yield self.item
　　　　if self.more:
　　　　　　for item in iter(self.more):
　　　　　　　　yield item

我们定义了初始化两种不同节点的基本方法。唯一必要的参数为元素本身；两个子树和父节点引用都作为可选参数。

这些属性用来确保parent属性以强引用的方式出现，虽然实际上它是weakref属性。关于更多弱引用的信息，请查看第2章“与Python无缝集成——基本特殊方法”。在一个TreeNode父节点对象和它的孩子节点对象之间存在互相引用，这种循环引用让删除TreeNode对象变得很困难。可以用一个weakref打破这种循环引用。

接下来是find()方法，它会递归地在树中遍历子树，搜索目标元素。

iter()方法会按顺序遍历当前节点和它的所有子树。和往常一样，这是一个生成器函数，它从每一个子树集合的迭代器中生成要返回的值。尽管可以创建一个基于Tree类的独立迭代器，但是这样做没有任何好处，因为生成器函数可以完成我们需要的所有功能。

下面是这个类的第2部分，实现了向树中添加新节点。

def add( self, item ):
　　if self.item is None: # Root Special Case
　　　　if self.more:
　　　　　　self.more.add( item )
　　　　else:
　　　　　　self.more= TreeNode( item, parent=self )
　　elif self.item >= item:
　　　　if self.less:
　　　　　　self.less.add( item )
　　　　else:
　　　　　　self.less= TreeNode( item, parent=self )
　　elif self.item < item:
　　　　if self.more:
　　　　　　self.more.add( item )
　　　　else:
　　　　　　self.more= TreeNode( item, parent=self )

这个方法递归地搜索要插入节点的正确位置。这个方法的结构和find()方法类似。

最后，我们处理从树中删除节点（更复杂）。这里要特别注意将删除后丢失的节点与树重新链接起来。

def remove( self, item ):
　　# Recursive search for node
　　if self.item is None or item > self.item:
　　　　if self.more:
　　　　　　self.more.remove(item)
　　　　else:
　　　　　　raise KeyError
　　elif item < self.item:
　　　　if self.less:
　　　　　　self.less.remove(item)
　　　　else:
　　　　　　raise KeyError
　　else: # self.item == item
　　　　if self.less and self.more: # Two children are present
　　　　　　successor = self.more._least()
　　　　　　self.item = successor.item
　　　　　　successor.remove(successor.item)
　　　　elif self.less: # One child on less
　　　　　　self._replace(self.less)
　　　　elif self.more: # On child on more
　　　　　　self._replace(self.more)
　　　　else: # Zero children
　　　　　　self._replace(None)
def _least(self):
　　if self.less is None: return self
　　return self.less._least()
def _replace(self,new=None):
　　if self.parent:
　　　　if self == self.parent.less:
　　　　　　self.parent.less = new
　　　　else:
　　　　　　self.parent.more = new
　　if new is not None:
　　　　new.parent = self.parent

remove()方法有两个部分。第1部分是递归地查找目标节点。

一旦找到了这个节点，要考虑3种情况。

• 当删除一个没有孩子的节点时，我们可以简单地删除它然后将与父节点的引用改为None。
• 当删除一个有一个孩子的节点时，我们可以用这个孩子代替当前节点在父节点中的引用。
• 当有两个孩子时，我们需要调整树的结构。我们首先找到后继节点（在more子树中的最小节点）。可以用这个后继节点的值替换准备删除的节点。然后，可以删除之前那个重复的后继节点。

我们依赖于两个私有方法。_least方法会在一棵给定的树中查询出最小节点。_replace()方法检查父节点，以确定是否需要更新less或者more属性。

6.7.4　演示二叉树集合

我们创建了一个全新的集合类型。抽象基类的定义中自带了许多方法。这些继承而来的方法可能不是特别高效，但是它们已经定义好了，可以正常工作，所以我们没有重新实现它们。

>>> s1 = Tree( ["Item 1", "Another", "Middle"] )
>>> list(s1)
['Another', 'Item 1', 'Middle']
>>> len(s1)
3
>>> s2 = Tree( ["Another", "More", "Yet More"] )
>>>
>>> union= s1|s2
>>> list(union)
['Another', 'Another', 'Item 1', 'Middle', 'More', 'Yet More']
>>> len(union)
6
>>> union.remove('Another')
>>> list(union)
['Another', 'Item 1', 'Middle', 'More', 'Yet More']

示例向我们展示了集合的union运算符可以正常工作，虽然并没有特意为它提供实现。由于这本质上是一个包，因此可以允许元素重复。