动态操作中主要的是插入和删除一个结点。

相对于删除操作来讲，插入一个结点还是比较简单。

插入分成两步：

​ ①首先按二叉查找树查找一个结点(保证二叉查找树的性质)

​ ②对遭到破坏的红黑树的特性进行恢复fixup

调整原则：

①不能让树的高度变得越来越高

②尽可能让处理的情况越少越好

• rb-delete中的tree-delete和二叉查找树的tree-delete的一点不同：前者的叶子结点是nil结点。

Z指向被删结点，y指向实际被删结点。

情况1和2：z没有孩子或者只有1个孩子， z和y指向同一个结点；

情况3：z有2个孩子，y指向z 的中序后继

删除操作中：

删除z, x补上去，x是拼接结点。

• 黑高度不一致是通过旋转来解决的。

• 只要走到case4,调整就结束了。

• 真正需要处理的是case2 case4

• 只有case2 才会循环处理

• while循环的次数不会超过树的高度

+++

红黑树的例子-引出数据结构扩张的方法

1. 什么序统计
2. 该用什么结构，如果是数组的话，预处理(排序)O(nlgn),其他O(1)，但是增加删除是O(n)
3. 如果是基本的二叉树，最坏情况跟数组差不多
4. 红黑树可以达到对数级别的操作，但是序统计如何解决？
   1. 扩充一个表示顺序的域：静态的时候，找第几小，找最大，都是O(n);动态时维护这个序要O(n),这样不行；但是告诉我们通过扩充域能解决问题，那么应该扩充什么样的域？
   2. 序统计树
      1. 增加SIZE域
      2. （静态）求x的序值操作OS-ran(T,x) , O(lgn)
      3. 插入一个结点的size域调整:
         • 一系列祖先+1，不超过树高；
         • 旋转操作中2个结点的size域调整(旋转次数不超过2次)
      4. 删除1个结点size域的调整（旋转次数不超过3次）

加序值是一种全局的方式，加size域是一种局部的方式，所以前者不行。

=>> 引出数据结构扩张的方法

红黑树应用的第二个例子-区间树

仍然是查找问题，不同于前面的，前面的是针对单个关键字的查找问题，区间树是针对一个范围的查找问题，是比较常见的。比如过去5年硕士研究生的招生人数。