树的旋转

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

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

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

红黑树的定义

需要在二叉搜索树上增加一个额外的颜色信息，树中的节点可以涂成红色或黑色。
如果一棵二叉搜索树满足下面的全部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,Tl,k,Tr) 。

函数 match(T) 用以判断树是否符合上图中4中需要修复的情况。定义如下：

定义好 balance(T) 后，就可以修改二叉搜索树的插入函数，使其支持红黑树：

其中 ins(T,k) 函数定义如下：

如果待插入的树为空，则创建一个新的红色节点，节点的key就是待插入的k；
否则，记树的左右分支和key分别为 Tl,Tr和k′ ，比较 k 和 k′ 的大小，递归地将它插入子分支中，然后再用balance函数恢复平衡。
最后，使用 makeBlack(T) 函数把根节点染成黑色：

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

删除

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