试证明,含n个节点的二叉树的最小高度为[log2n]——这也是由n个节点组成的完全二叉树高。
第1题
第2题
四叉树(quadtree)是2d-树的简化形式,其简化策略包括:
①直接沿区域的(水平或垂直)平分线切分,从而省略了中位点的计算;
②沿垂直方向切出的每一对节点(各自再沿水平方向切分)都经合并后归入其父节点;
③被合并的节点即便原先(因所含输入点不足两个)而未继续切分,在此也需要强行(沿水平方向)切分一次。
于是如图x8.8所示,每个叶节点各含0至1个输入点;每个内部节点则都统一地拥有四个孩子,分别对应于父节点所对应矩形区域经平均划分之后所得的四个象限,该树也由此得名。
a)与kd-树不同,四叉树可能包含大量的空(即不含任何输入点的)节点。更糟糕的是,此类节点的数目无法仅由输入规模n界定。对于任意的N>0,试构造一个仅含n=3个点的输入点集,使得在其对应的四叉树中,空节点的数目超过N个。
b)对于任一输入点集P,若将其中所有点对的最长、最小距离分别记作D和d,则λ=D/d称作P的散布度(spread),试证明,P所对应的四叉树高度为o(logλ)。
c)试基于四叉树结构设计相应的范围查询算法,并利用你的四叉树结构实现该算法。
d)针对范围查询这一应用,试分别从时间、空间效率的角度,将四叉树与2d-树做一比较。
第3题
第4题
设二叉树中所有非叶结点的左、右子树都不为空。试证明对此类二叉树满足:
(1)含有n个叶结点的二叉树中共有2n-1个结点。
(2),其中,n为叶结点个数,1.表示第i个叶结点所在的层次(设根结点所在的层次为1).
第5题
考查任意阶的B-树T。
a)若T的初始高度为1,而在经过连续的若干次插入操作之后,高度增加至h且共有n个内部节点,则在此过程中T总共分裂过多少次?
b)在如上过程中,每一关键码的插入,平均引发了多少次分裂操作?
c)若T的初始高度为h且含有n个内部节点,而在经过连续的若干次删除操作之后高度下降至1,则在此过程中T总共合并过多少次?
d)设T的初始高度为1,而且在随后经过若干次插入和删除操作——次序任意,且可能彼此相间。试证明:若在此期间总共做过S次分裂和M次合并,且最终共有n个内部节点,高度为h,则必有:S-M=n-h。
第8题
证明下列关系:
(1)设T是具有n个内结点的扩充二叉树,I是它的内路径长度,E是它的外路径长度。试利用归纳法证明E=1+2n,n≥1.
(2)利用(1)的结果,试说明:成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度U.之间的关系可用公式Sn=(1+1/n)Un-1,n≥1表示。
第9题