高级数据结构与算法分析

红黑树

定义与性质

一棵合法的 红黑树 是遵循以下五条性质的二叉搜索树：
（1）节点要么为红色要么为黑色
（2）NIL 节点为黑色节点
（3）红色节点的子节点必然为黑色节点
（4）从根节点到所有 NIL 节点的简单路径上的 黑色节点 数量 相同
（5）根节点为黑色节点

一棵包含 $n$ 个 内部节点 的红黑树的 最大高度 为 $2\ln{(n+1)}$

插入操作

B+树

定义与性质

一棵阶为 $m$ 的 B+树 具有以下性质：
（1）根节点 要么是一个叶子节点，要么有 $2$ 至 $m$ 个子节点
（2）所有的 非叶子节点（除了根节点）都有 $\lceil\frac{m}{2}\rceil$ 至 $m$ 个子节点
（3）所有的 叶子节点 具有 相同的高度
假设所有的 非根节点 都有 $\lceil\frac{m}{2}\rceil$ 至 $m$ 个儿子

所有的数据都保存在 叶子节点 中
每一个 内部节点 包含 $m$ 个指针指向子节点