一、二叉搜索树
- x是一颗有n个结点的二叉搜索树的根，遍历：Θ(n)
- 高度为h的二叉搜索树，查找、最大/最小关键字元素、前驱/后继：O(h)
- 高度为h的二叉搜索树，插入、删除：O(h)
- 一颗有n个不同关键字的随机构建二叉搜索树的期望高度：O(lgn)
二、红黑树
性质
- 每个结点是红色的，或者黑色的。
- 根节点是黑色的。
- 每个叶节点（NIL）是黑色的。
- 如果一个结点是红色的，则它的两个子结点都是黑色的。
- 对每个结点，从该结点到其后代所有叶结点的简单路径上，均包含相同数目的黑色结点。
以及…
- 每个结点5个属性：color、key、left、right、p。
- 黑高bh(x)，不含x。
- RBTree确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。
重要定理：
- 一颗有n个内部结点的RBTree，高度至多为：$2lg(n+1)$
旋转
- 时间复杂度：O(1)
插入
- 像普通二叉搜索树一样，从根开始沿树下降，把结点z插入树T内作为某个已知结点的孩子；
- 将Z着为红色；（只有红黑性质2、4可能受影响）
- 调用Insert-Fixup，沿树上升，对结点重新着色并旋转，保持红黑性质。
以及…
- 插入操作 时间：$O(lgn)$
- Fix-up所做的旋转不超过2次。
删除
- 删除操作 时间：$O(lgn)$
- fix-up所做的旋转不超过3次。
三、扩张数据结构
- 选择一种基础数据结构；
- 确定基础数据结构中要维护的附加信息；
- 检验基础数据结构中的基本修改操作能否维护附加信息；
- 设计一些新操作。
定理（红黑树的扩张）
- 设f 是n个结点的红黑树T的扩张的属性，且对任一结点x，f的值仅依赖于结点x、x.left、和x.right 的信息，还可能包括x.left.f 和x.right.f。
- 那么，可以在插入和删除操作期间对T的所有结点的f值进行维护，且不影响这两个操作O(f)的时间性能。
四、顺序统计树
- 扩张的红黑树
- 结点x增添属性：$x.size = x.left.size + x.right.size + 1$
- 元素的秩：在中序遍历时树时输出的位置
按照扩张数据结构的步骤：
- 选择基本数据结构红黑树；
- 添加了size属性；
- 保证插入和删除操作仍能在O(lgn)的时间内维护size属性；
- 添加新操作Os-Select 和Os-Rank。
查找具有给定秩的元素：
OS-Select(x,i)运行时间为：$O(lgn)$
确定一个元素的秩
OS-Rank(T,x)运行时间为：$O(lgn)$
对子树规模的维护
插入：
- 从根开始沿树下降，把新结点插入作为某个已有结点的孩子。—-为维护子树规模，对由根至叶子路径上遍历的每一个结点，加一个x.size属性；
- 沿树上升，做一些变色和旋转操作。至多两次旋转。—-对红黑树结构的改变仅有旋转引起。一次旋转使两个结点的size属性失效。
因此，顺序统计树，插入，$O(lgn)$
删除：
- 对搜索树进行操作。要么将y删除，要么将y在树中上移。—-为更新子树规模，遍历一条从y到根的简单路径，减少路径上每个点的size值；
- 至多三次旋转。
因此，顺序统计树，删除，$O(lgn)$
五、区间树
- 每个元素包含一个区间 x.int。 x的关键字为区间的低端点 x.int.low；
- 该树的中序遍历列出按低端点次序排列的各区间。
- 每个结点x 包含自身区间，还包含x.max，即以x为根的子树中所有区间的端点最大值。
按照扩张数据结构的步骤：
- 选择基本数据结构红黑树；
- 添加附加信息x.max；
- 验证插入和删除操作能否在O(lgn)内完成；
- 设计新操作Interval-Search(T，i)。
Interval-Search(T，i)
返回一个指向区间树T中元素x的指针，使x.int 与i 重叠。若此元素不存在，则返回T.nil。
时间：O(lgn)