1.红黑树（Red-Black Tree）
红黑树是具有如下性质的二叉排序树
（1）每个结点或是黑色的，或是红色的
（2）根结点和外部结点均是黑色的
（3）不存在两个相邻的红结点，即红结点的父结点和孩子结点都是黑色的
（4）对任一结点，从该结点到任一叶子结点的简单路径上，所含黑色结点的数目相同
注：在红黑树中的叶子结点和外部结点（NULL结点、失败结点）是等价概念，是逻辑结点，实际上并不存在
struct RBnode{
Element key;// 关键字的值
RBnode* parent;// 父结点指针
RBnode* lChild;// 左孩子指针
RBnode* rChild;// 右孩子指针
Element color;// 结点颜色
}
2.二叉排序树、平衡二叉树、红黑树三者的比较
| 二叉排序树 | 平衡二叉树 | 红黑树 | |
|---|---|---|---|
| 查找操作时间复杂度 | O ( n ) O(n) O(n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) |
| 插入操作时间复杂度 | O ( n ) O(n) O(n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) |
| 删除操作时间复杂度 | O ( n ) O(n) O(n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) | O ( l o g 2 n ) O(log_{2^n}) O(log2n) |
平衡二叉树：其插入、删除操作容易破坏其平衡的特性，需要频繁调整树的形态。适用于以查找操作为主，很少进行插入/删除操作的场景
红黑树：插入/删除操作很多时候不会破坏红黑树的特性，无需调整树的形态。即使需要调整，一般可以在常数级的时间内完成。适用于频繁进行插入/删除操作的场景，实用性更强
3.红黑树结点的黑高
从某结点出发（不包含该结点）到任一外部结点的路径上黑结点的总数
4.红黑树的性质
（1）从根结点到叶结点的最长路径不大于最短路径的两倍
（2）有n个内部结点的红黑树高度为 h < l o g 2 ( n + 1 ) h<log_{2}(n+1) h<log2(n+1)
（3）根结点黑高为h的红黑树，内部结点数至少（满二叉树的情况）有 2 h − 1 2^h-1 2h−1个
5.红黑树的插入
（1）根据二叉排序树的插入规则插入新结点。新结点若是根结点则染为黑色，否则染为红色
（2）判断插入新结点后的树是否满足红黑树的定义，若满足则完成插入操作，反之进行步骤（3）
（3）判断新结点叔结点的颜色。叔结点若是黑色进行步骤（4），反之进行步骤（5）
（4）根据新结点相对于爷结点的位置判断旋转类型并进行旋转（LL、RR、LR、RL），然后对结点进行变色（LL、RR：父、爷结点进行变色，LR、RL：新结点、爷结点进行变色）
（5）对叔、父、爷结点进行变色并将爷结点当做新插入的结点，重复步骤（1）-（5）
