试证明，在高度为h的AVL树中，任一叶节点的深度均不小于[h/2]。

试证明，按递增次序将2^h+1-1个关键码插入初始为空的AVL树中，必然得到高度为h的满树。

在一棵高度为h的AVL树中，离根最远的叶结点在第(①)层，离根最近的叶结点在第(②)层.

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

任给高度分别为g和h的两棵AVL树S和T，且S中的节点均不大于T中的节点。试设计一个算法，在O（max（g，h))时间内将它们合并为一棵AVL树。

a)试证明，在从堆顶通往任一叶节点的沿途上，各节点对应的关键码必然单调变化;b)试给出一个算法，对于秩为r的任一节点，在O（1)时间内确定其在任何高度h上祖先的秩;c)试改进percolateUp算法（代码10.7)，将其中执行的关键码比较减少至O（loglogn)次;d)经过以上改进，percolateUp算法总体的渐进复杂度是否有所优化？

证明：高度为h的2-3树(3阶B树)的叶结点的数在2h-1与3h-1之间。

将关键码1，2，3，…，2*一1依次插入到一棵初始为空的AVL树中，试证明占果树是完全平衡的.

试证明：a)按照二叉搜索树的基本算法在AVL树中引入一个节点后，失衡的节点可能多达Ω（logn)个;b)按照二叉搜索树的基本算法从AVL树中摘除一个节点后，失衡的节点至多1个。

设m≥3为奇数。试对任意的h＞0，构造一棵高度为h的m节B-树，使得若反复地对该树交替地执行插入、删除操作，则每次插入或删除操作都会引发h次分裂或合并。

试证明，对于任意大的正整数n，都存在一棵规模为n的AVL树，从中删除某一特定节点之后，的确需要做Ω（logn)次旋转，方能使全树恢复平衡。