10　平衡树

AVL 旋转、树高控制、红黑与 B 树

本节 12 题。先独立给出结论和理由，再对照解析；新增题与此前题目统一编号。涉及标签时，标签只表示记录身份。

第 01 题

问题 1

本教材空树高度 0、叶高度 1，平衡因子如何定义？

第 02 题

问题 2

AVL 允许的平衡因子有哪些？

第 03 题

问题 3

插入 [30,20,10] 的失衡类型和修复？

第 04 题

问题 4

插入 [10,20,30] 的修复？

第 05 题

问题 5

插入 [30,10,20] 的修复？

第 06 题

问题 6

插入 [10,30,20] 的修复？

第 07 题

问题 7

旋转是否改变中序键顺序？

第 08 题

问题 8

旋转后应先更新哪个节点高度？

第 09 题

问题 9

AVL 删除只需修复删除点一次就能保证全树平衡吗？

第 10 题

问题 10

红黑树是否要求每个节点两侧高度最多差 1？

第 11 题

问题 11

红黑树中红节点的孩子和根颜色应怎样（常规约定）？

第 12 题

问题 12

数据库的磁盘索引为什么常用 B/B+ 树而非简单二叉树？