1. 红黑树首先是一颗二叉查找树。

2. 二叉树删除结点的原则：

   ①删除操作应简单②删除不应使得树的高度增加③要处理的情况少（③属于红黑树）

3. 二叉树删除过程中的3个指针

   1. z:被删除结点
   2. y:被删除结点Z的中序后继,也叫实际被删结点。此种情况下Z的左右孩子都存在
   3. x:y的孩子，也叫拼接指针

4. 二叉查找树的很多操作的时间复杂度跟树的高度有关

5. 二叉查找树的高度可能为N,退化为单链表

6. 二叉查找树的应用：查找类问题

7. 平衡二叉树：外排序中的B+树

8. 平衡二叉查找树：二叉树

红黑树

1. 定义+ 性质 + 黑高的定义

2. 证明一个定理

3. 静态操作（不修改树的结构，查找，求前驱和后继）时间复杂度证明为O(logn)

4. 动态操作的时间复杂度能不能维持在LogN界内

5. 插入和删除都有1个共同的操作：旋转

   1. 左旋
   2. 右旋

6. rb-insert-fixup操作只要走到case3算法就结束了。

7. rb-insert-fixup的while循环只在case1,每次网上走2层；一旦走到case2,case2就转到case3

8. 实际上rb-insert-fixup可以归结为2种情况，一种是Uncle是红色，一种是uncle是黑色

9. 对于rb-insert-fixup中的else子句中的case3 是 原来的case2,要进行一次旋转，课中《例题》。

一个例子