---

1 二叉搜索树

名称 概念
前趋 比当前节点小的最大节点
后继 比当前节点大的最小节点
祖先 该节点的父节点及以上

定理：

  • 如果x是一个含有n个结点的子树的根，那么调用INORDER-TREE-WALK(中序遍历)需要时间$\theta(n)$

  • 在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH,MINIMUM,MAXMUN,SUCCESSOR(后继),PREDECESSOR（前趋）需要时间O(h)

  • 在一棵高度为h的二叉搜索树上，实现动态集合INSERT（插入）和DELETE（删除）操作需要时间O(h)

2 红黑树

红黑树四条性质：（红黑树中可以没有黑色，但有红色必须满足其性质）
1.每个结点为红色或黑色。
2.根节点和叶结点都是黑色的。
3.每个红色节点的叶结点都是黑色的。
4.从一个节点X到X的子孙叶结点，所有到子孙叶结点的路径，都有相等的黑结点数。
5.红色结点的儿子必定是黑的。

一棵有n个内结点的红黑树高度至多为$2\lg（_{}{n+1}）$

结点的秩是树中小于或等于该结点的结点数量。

从某个结点x出发（不含该结点），到达叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高，记为bh(x)。

旋转操作：
旋转操作图示

插入或删除后的修复操作（满足所有红黑树性质）：
修复操作图示

3 顺序统计树

对于一颗含有n个结点的顺序统计树，插入，删除操作，包括维护size域，都需要O(lg(n))时间。

4 区间树

区间三分法
1.完全位于左子树的区间。已知区间的右端点小于当前结点区间的左端点。
2.与当前结点区间重叠的区间。已知区间与当前结点区间有交集。
3.完全位于右子树的区间。已知区间的左端点大于当前结点区间的右端点。