chapter07
复制本地路径 | 在线编辑
1. 平衡二叉搜索树
1.1 随机生成，一共多少种树，其平均高度为多少
1.2 随机组成，一共多少种树，其平均高度为多少
1.3 简述remove实现方式，使得该实现对于后面的红黑树等删除有较好的扩展性
1.4 若二叉搜索树支持多个相等数据并存，设计一个searchAll(e)，返回所有e节点
1.5 若二叉搜索树支持多个相等数据并存，改进search和insert，使得能够返回先进先出
2. AVL树
2.1 简述AVL插入和删除算法，要求给出图解
2.2 AVL树插入至多造成多少个节点失衡，给出例子
2.3 AVL树删除至多造成多少个节点失衡，给出证明
2.4 证明: 若将[0,2^h-1]个关键码插入AVL树中，必然可以得到高度为h的满树
3. Splay树
3.1 简述Splay的伸展算法，要求给出图解
3.2 证明: Splay的伸展算法复杂度为O(logn)
4. B树
4.1 证明: B树的外部节点始终比内部节点多1
4.2 证明: B树的高度范围是
4.3 说明B树的插入处理(1种)，删除处理(3种)
5. 红黑树
5.1 简述红黑树的插入处理(3种)
5.2 简述红黑树的删除处理(5种)
5.3 对于2012个节点，求: 最小黑高度，最大黑高度，最小高度，最大高度
5.4 红黑树分摊意义来看，重染色的节点不超过O(1)个
6. K-d树
6.1 证明: K-D树的运行时间为O(sqrt(n))
7. B树构造实例
7.1 构造: 对于一棵B树，插入一个节点，发生最坏情况，即进行O(log_m(n))次分裂
7.2 构造: 对于一棵B树，若高度为h，进行反复插入和删除，每一次都会进行h次分裂
8. 对于一棵B树，假设其为T
8.1 若初始高度为1，进行若干次插入操作后，高度增加为h,内部节点为n，求在此过程中T分裂的次数
8.2 说明平均多少次关键码的插入会造成一次分裂操作