（持久动态集合）有时在算法的执行过程中，我们会发现在更新一个动态集合时，需要维护其过去的版本。我们称这样的集合为持久的（persistent）。实现持久集合的一种方法是每当该集合被修改时，就将其完整的复制下来，但是这种方法会降低一个程序的执行速度，而且占用过多的空间。有时候，我们可以做得更好些。
考虑一个有INSERT,DELETE和SEARCH操作的持久集合S，我们使用下图所示的二叉搜索树实现。对集合的每一个版本都维护一个不同的根。为了将关键字5插入到集合中，创建一个具有关键字5的新节点。该节点成为具有关键字7的新节点的左孩子，因为我们不能更改具有关键字7的已存在节点。类似的，具有关键字7的新节点成为具有关键字8的新节点的左孩子，后者的右孩子为具有关键字10的已存在节点。关键字为8的新节点有成为关键字4的新节点r'的右孩子，而r'的左孩子是关键字为3的已存在节点，这样，我们只是复制了树的一部分，新树共享了原树的一些节点，如下图右图所示。
假设树中每个节点都有属性key,left和right，但没有属性parent。
a.对于一棵一般的持久二叉搜索树，为插入一个关键字k或删除一个节点y,需要改变哪些节点。
b.请写出一个过程PERSISTENT-TREE-INSERT，使得在给定一棵持久树T和一个要插入的关键字k时，它返回将k插入到T后得到的新的持久树T'。
c.如果持久二叉搜索树T的高度为h，实现PERSISTENT-TREE-INSERT过程的时间和空间需求分别是多少？（空间需求与新分配的节点数成正比）
d.假设在每个节点中增加一个父节点属性。这种情况下，PERSISTENT-TREE-INSERT需要做一些额外的复制工作。证明：PERSISTENT-TREE-INSERT的时间需求和空间需求为)
，其中n位树中的节点个数。
e.说明如何利用红黑树来保证每次插入或删除的最坏情况运行时间和空间为O(lgn)。
