任给高度为h的一棵AVL树A，以及一个关键码e。试设计一个算法，在O（h)时间内将A分裂为一对AVL树S和T，且S中的节点均小于e，而T中的节点均不小于e。

考查任何一棵高度为h的二叉树T，设其中深度为k的叶节点有n_k个，0≤k≤h。

a)试证明：

b)以上不等式取等号的充要条件是什么？

问题描述:给定一棵有向树T,树T中每个顶点u都有一个权w(u),树的每条边(u,v)也都有一个非负边长d(u,v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).

每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构所需付出的服务转移费用为w(u).d(u,v).树根处已设置了服务机构,现在要在树T中增设k处服务机构,使得整棵树T的服务转移费用最小.

算法设计:对于给定的有向树T,计算在树T中增设k处服务机构的最小服务转移费用.数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数,k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.在接下来的n行中,每行有表示有向树T的一条有向边的3个整数.第i+1行的3个整数w_i、v_i、d_i,分别表示编号为i的顶点的权为w_i,相应的有向边为(i,v_i),其边长为di.

结果输出:将计算的最小服务转移费用输出到文件output.txt.

算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.

数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.

接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.

结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"

考查任意阶的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。

为提高空间利用率，可将内部节点的分支数下限从[m/2]提高至[2m/3]。于是，一旦节点v发生上溢且无法通过旋转完成修复，即可将v与其(已经饱和的某一)兄弟合并，再将合并节点等分为三个节点，采用这一策略之后，即得到了B-树的一个变种，称作B'-树(B'-tree)。

当然，实际上不必真地先合二为一，再一分为三。可通过更为快捷的方式，达到同样的效果：从来自原先两个节点及其父节点的共计m+(m-1)+1=2m个关键码中，取出两个上交给父节点，其余2m-2个则尽可能均衡地分摊给三个新节点。

a)按照上述思路，实现B'-树的关键码插入算法;

b)与B-树相比，B'-树的关键码删除算法又有何不同？

设S表示某人拥有的所有的树的集合，M，N，T，PS，且M是珍贵的树的集合，N是果树的集合，T是去年刚栽的树的集合，P是在果园中的树的集合，下面是3个前提条件和2条结论。

前提：(1)所有的珍贵的树都是去年裁的。

(2)所有的果树都在果园里。

(3)果园里没有去年栽的树。

结论：(1)所有的果树都是去年栽的。

(2)没有一棵珍贵的树是果树。

则前提(1)，(2)，(3)和结论(1)的集合表达式分别为，根据前提条件，两个结论中正确的是。