树的旋转

树的旋转是一种特殊操作，保持中序遍历结果不变的情况下，改变树的结构。

上图中a所示二叉搜索树经过左旋变换为b所示的树。（右旋操作是左旋的逆变换）

函数定义
将非空二叉树记为三元组$T=(T_l,k,T_r)$，则：

$$rotateL(T)= \begin{cases} ((a,X,b),Y,c)&:T=(a,x,(b,c))\\ T&:其他 \end{cases}$$
$$rotateR(T)= \begin{cases} (a,c)&:T=((a,c)\\ T&:其他 \end{cases}$$

红黑树的定义

需要在二叉搜索树上增加一个额外的颜色信息，树中的节点可以涂成红色或黑色。
如果一棵二叉搜索树满足下面的全部5条性质，则成为红黑树：

1. 任一节点要么是红色，要么是黑色；
2. 根节点为黑色
3. 所有的叶子结点（NIL节点）为黑色
4. 如果一个节点为红色，则它的两个子节点都是黑色；
5. 对任一节点，从它出发到所有叶子结点的路径上包含相同数量的黑色节点。

关键特性：从根结点出发到达叶子节点的所有路径中，最长路径不会超过最短路径的两倍。

数据组织

红黑树的节点：

function Node(data,color,left,right) {
    this.data = data;
    this.color = color;
    this.left = left;
    this.right = right;
    this.show = show;
}
function show() {
    return this.data;
}

插入

1、插入操作会改变树的结构，因此二叉搜索树可能变得不平衡。因此，为了保持红黑树的特质，需要在插入操作后进行变换来修复平衡问题。
2、当插入一个key时，可以把新节点一律染成红色。只要它不是根节点，除了第4条，所有红黑树性质都可以满足，唯一的问题是可能引入两个相邻的红色节点。
3、共有4种情况会违反红黑树的第4条性质，它们都带有两个相邻的红色节点。但是，它们可以被修复为一个统一形式，如下图：

注意：这一变换会把红色向上“移动一层”。如果进行自底向上的递归修复，最后一步会把根节点染成红色。根据第2条性质，因此要把根节点再染回黑色。

算法函数描述
把节点的颜色记为C，它有两个值，黑色B和红色R。这一棵非空的红黑树可以表达为一个四元组 $T=(C,T_l,T_r)$。

$$balance(T)= \begin{cases} (R,(B,A,B),y,C,z,D))&:match(T)\\ T&:其他 \end{cases}$$
函数 $match(T)$用以判断树是否符合上图中4中需要修复的情况。定义如下：
$$match(T): T=\begin{cases} (B,(R,C),D) \lor\\ (B,B,Z)),A.x,D))) \lor\\ (B,D)) \end{cases}$$
定义好 $balance(T)$后，就可以修改二叉搜索树的插入函数，使其支持红黑树：
$$insesrt(T,k)=makeBlack(ins(T,k))$$
其中 $ins(T,k)$函数定义如下：
$$ins(T,k)= \begin{cases} (R,\phi,\phi)&:T=\phi\\ balance((ins(T_l,k),k',T_r))&:k<k'\\ balance((T_l,ins(T_r,k)))&:k<k' \end{cases}$$
如果待插入的树为空，则创建一个新的红色节点，节点的key就是待插入的k；
否则，记树的左右分支和key分别为 Tl,Tr和@H_403_1523@k′ $T_l,T_r和k'$，比较 @H_403_1523@k $k$和 @H_403_1523@k′ $k'$的大小，递归地将它插入子分支中，然后再用balance函数恢复平衡。
最后，使用 $makeBlack(T)$函数把根节点染成黑色：
$$makeBlack(T)=(B,T_r)$$

算法复杂度：这一插入算法的复杂度为$O(lgn)$。

删除

删除操作在删除一个黑色的节点时才会引发问题，因为这样会破坏红黑树的第 5 条性质，使得某一路径上的黑色节点数目少于其他的路径。
解决方案： 引入“双重黑色”的概念来恢复第 5 条性质。即节点被删除了，我们把它的黑色保存在它的父节点中。如果父节点是红色的，我们将其变为黑色；如果父节点已经是黑色的，它就会变成一个“双重黑色”的节点。