【思考】
12-1 具有相同关键字的二叉查找树
a) 当用TREE-INSERT将n个具有相同关键字的数据项插入到一棵初始为空的二叉查找树中时，该算法的渐进性能如何？
差不多O(n^2)
b) 在结点x处设一个布尔标志b[x]，并根据b[x]的不同值，置x为left[x]或right[x]。每当插入一个与x具有相同关键字的结点时，b[x]取反！
O(nlogn)
c) 在结点x处设置一个列表，其中所有结点都具有与x相同的关键字，并将z插入到该列表中。
O(n^2)
d) 随机地将x置为left[x]或right[x]。
最坏O(n^2)，平均O(nlogn)。
12-2 基数树
基数树，或称Patricia trie/tree，或 crit bit tree，是一种基于trie（字典树）的特殊的数据结构。一般用来储存字符串集。
将01串按性质插入基数数中，对树进行遍历，得到的串即为按字典序排列的。
12-3 随机构造的二叉查找树中的平均节点深度
证明在一棵随机构造的二叉查找树中，n个节点的平均深度为O(lgn)。
12-4 不同的二叉树数目
设bn表示包含n个结点的不同的二叉树的数目。在本问题里，要给出关于bn的公式和一个渐进估计。
a) 证明：b0=1，且对n>=1，有：
当n==1时，b1=b0*b0=1。包含1个结点的不同二叉树的数目为1。
假设当n==i-1时，成立。
当n==i时，除去根节点，共有i-1个结点要分配到左右两个子树中，假设左子树拥有结点k，则右子树拥有结点i-1-k个，则有方案bk*b(i-1-k)种。
因此bi=∑bk*b(i-1-k)，假设成立。
因此bn=∑bk*b(n-1-k)。
b) 设B(x)为生成函数
证明B(x)=xB(x)^2+1，因而表达式B(x)的一种方式是
在点x=a处f(x)的泰勒展式为
其中f(k)(x)是在点x处f的k阶导数。
c) 通过在x=0处使用sqrt(1-4x)的泰勒展式，证明
d) 证明：
