• 红黑树是什么

1. 节点是红色或者黑色
2. 根结点是黑色
3. 每个叶子的节点都是黑色的空节点(NULL)
4. 每个红色节点的两个子节点都是黑色的
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
6. 红黑树的时间复杂度为: O(lgn)

• 红黑树的基本操作(一) 左旋和右旋

1. 左旋

对x进行左旋，即将x设为y的左孩子，y的左孩子变为x的右孩子，x的父亲设为y的父亲

2. 右旋

对y进行右旋，即将y设为x的右孩子，x的右孩子变为y的左孩子，y的父亲设为x的父亲

• 红黑树的基本操作(二) 添加

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

第二步：将插入的节点z着色为"红色"。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

根据被插入节点的父节点的情况，可以将"当节点z被着色为红色节点，并插入二叉树"划分为三种情况来处理。

① 情况说明：被插入的节点是根节点。

    处理方法：直接把此节点涂为黑色。

② 情况说明：被插入的节点的父节点是黑色。

    处理方法：什么也不需要做。节点被插入后，仍然是红黑树。

③ 情况说明：被插入的节点的父节点是红色。

    处理方法：依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。

Case1

当前节点的父节是红色，且当前节点的祖父节点的另一个子节点(叔叔节点也是红色)。

(01) 将“父节点”设为黑色。

(02) 将“叔叔节点”设为黑色。

(03) 将“祖父节点”设为“红色”。

(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。

Case2

当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子

(01) 将“父节点”作为“新的当前节点”。

(02) 以“新的当前节点”为支点进行左旋。

Case3

当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子

(01) 将“父节点”设为“黑色”。

(02) 将“祖父节点”设为“红色”。

(03) 以“祖父节点”为支点进行右旋。