10 平衡树
AVL 旋转、树高控制、红黑与 B 树
对应本节 12 道题。点击题目展开答案和理由，保留此前生成的详细解析。
第 01 题 问题 1
本教材空树高度 0、叶高度 1，平衡因子如何定义？
参考答案
左子树高度减右子树高度。
解析
这是本套约定；其他资料可能反号，必须一致。
第 02 题 问题 2
AVL 允许的平衡因子有哪些？
参考答案
−1、0、1。
解析
每个节点都应满足，不是只要求根满足。
第 03 题 问题 3
插入 [30,20,10] 的失衡类型和修复？
参考答案
LL 型，对 30 右旋。
解析
20 成为子树根，10、30 分居两侧。
第 04 题 问题 4
插入 [10,20,30] 的修复？
参考答案
RR 型，对 10 左旋。
解析
20 成为子树根，保持中序顺序。
第 05 题 问题 5
插入 [30,10,20] 的修复？
参考答案
LR 型：先对左孩子 10 左旋，再对 30 右旋。
解析
不能用单次右旋解决折线结构。
第 06 题 问题 6
插入 [10,30,20] 的修复？
参考答案
RL 型：先对右孩子 30 右旋，再对 10 左旋。
解析
双旋把中间键 20 提到子树根。
第 07 题 问题 7
旋转是否改变中序键顺序？
参考答案
不会，正确旋转保留 BST 顺序。
解析
只改变局部链接与高度，不重新定义键的大小。
第 08 题 问题 8
旋转后应先更新哪个节点高度？
参考答案
先更新降下去的旧根，再更新新的子树根。
解析
新根高度依赖其孩子的新高度。
第 09 题 问题 9
AVL 删除只需修复删除点一次就能保证全树平衡吗？
参考答案
不一定。
解析
删除后的高度变化可能向上传播，需要沿祖先路径检查。
第 10 题 问题 10
红黑树是否要求每个节点两侧高度最多差 1？
参考答案
不要求，那是 AVL 的局部约束。
解析
红黑树用颜色、红节点约束与黑高约束控制总体树高。
第 11 题 问题 11
红黑树中红节点的孩子和根颜色应怎样（常规约定）？
参考答案
红节点孩子必须黑；根为黑。
解析
NIL 叶视为黑，各根到 NIL 路径黑节点数相同。
第 12 题 问题 12
数据库的磁盘索引为什么常用 B/B+ 树而非简单二叉树？
参考答案
较高分支度把多个键放入页，降低树高与页读写次数。
解析
关注块 I/O 与局部性；AVL/红黑树偏向内存二叉搜索结构。