红黑树.md

红黑树介绍

先来看下算法导论对R-B Tree的介绍： 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下 二叉查找树的一般性质。

二叉查找树

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点（no duplicate nodes）

红黑树的5个性质

• 每个结点要么是红的要么是黑的。
• 根结点是黑的。
• 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
• 如果一个结点是红的，那么它的两个儿子都是黑的。
• 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

树的旋转知识

当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。

树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。

1. 左旋

如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。

相应的伪代码

	  LeftRoate(T, x)  
		y ← x.right                    //y是x的右孩子  
		x.right ← y.left                //y的左孩子成为x的右孩子  
		if y.left ≠ T.nil  
		    y.left.p ← x      
		y.p ← x.p                      //y成为x的父亲  
		if x.p = T.nil  
		    then T.root ← y  
		else if x = x.p.left  
		    then x.p.left ← y  
		else x.p.right ← y   
		y.left ← x                       //x作为y的左孩子  
		x.p ← y 

对应的js代码

var leftRotate  = function (Tree, node) {
	// y 为node的右节点
	var y = node.right;
	// y的左节点成为node的右节点
	node.right = y.left;

	if (y.left !== null) {
		y.left.parent = node;
	}
	// y代替node的位置
	y.parent = node.parent;

	// 若node为根接头点
	if (node.parent === null) {
		Tree.root = y;
	} else if (node == node.parent.left) {	// node 为左节点
		node.parent.left = y;
	} else {
		node.parent.right = y;
	}
	// node 成为y的左节点
	y.left = node;
	// y成为node的父节点 
	node.parent = y;
}

2. 右旋

树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。

红黑树的插入

如果要在二叉查找树中插入一个结点，首先要查找到结点要插入的位置，然后进行插入。假设插入的结点为z的话，插入的伪代码如下：

TREE-INSERT(T, z)  
	y ← NIL  
	x ← T.root  
	while x ≠ NIL  
	    do y ←  x  
	    if z.key < x.key  
	        then x ← x.left  
	    else x ← x.right  
	z.p ← y  
	if y == NIL  
	    then T.root ← z         
	else if z.key < y.key  
	    then y.left ← z  
	else y.right ← z  

红黑树的插入和插入修复

在我们了解了二叉查找树的插入，接下来，咱们便来具体了解下红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。

假设插入的结点为z，红黑树的插入伪代码具体如下所示：

RB-INSERT(T, z)  
	y ← nil  
	x ← T.root  
	while x ≠ T.nil  
	    do y ← x  
	    if z.key < x.key  
	        then x ← x.left  
	    else x ← x.right  
	z.p ← y  
	if y == nil[T]  
	    then T.root ← z  
	else if z.key < y.key  
	    then y.left ← z  
	else y.right ← z  
	z.left ← T.nil  
	z.right ← T.nil  
	z.color ← RED  
	RB-INSERT-FIXUP(T, z) 

把上面这段红黑树的插入代码，跟之前看到的二叉查找树的插入代码比较一下可以看出，RB-INSERT(T, z)前面的第1～13行代码基本上就是二叉查找树的插入代码，然后第14～16行代码把z的左孩子和右孩子都赋为叶结点nil，再把z结点着为红色，最后为保证红黑性质在插入操作后依然保持，调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色，并旋转。

换言之，如果插入的是根结点，由于原树是空树，此情况只会违反性质2，因此直接把此结点涂为黑色；如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时什么也不做。

但当遇到下述3种情况时又该如何调整呢？

• 插入修复情况1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
• 插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
• 插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子

答案就是根据红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP(T, z)函数所示的步骤进行操作，具体如下所示：

RB-INSERT-FIXUP(T, z)  
while z.p.color == RED  
    do if z.p == z.p.p.left  
        then y ← z.p.p.right  
        if y.color == RED  
            then z.p.color ← BLACK               ▹ Case 1  
            y.color ← BLACK                    ▹ Case 1  
            z.p.p.color ← RED                    ▹ Case 1  
            z ← z.p.p                            ▹ Case 1  
        else if z == z.p.right  
            then z ← z.p                          ▹ Case 2  
            LEFT-ROTATE(T, z)                   ▹ Case 2  
        z.p.color ← BLACK                        ▹ Case 3  
        z.p.p.color ← RED                         ▹ Case 3  
        RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3  
    else (same as then clause with "right" and "left" exchanged)  
T.root.color ← BLACK  

下面，咱们来分别处理上述3种插入修复情况。

• 插入修复情况1：当前结点的父结点是红色，祖父结点的另一个子结点（叔叔结点）是红色。

   while z.p.color == RED  
   do if z.p == z.p.p.left  
       then y ← z.p.p.right  
       if y.color == RED  
  

  此时父结点的父结点一定存在，否则插入前就已不是红黑树。与此同时，又分为父结点是祖父结点的左孩子还是右孩子，根据对称性，我们只要解开一个方向就可以了。这里只考虑父结点为祖父左孩子的情况，如下图所示。 对此，我们的解决策略是：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。即如下代码所示：

   then z.p.color ← BLACK               ▹ Case 1  
   y.color ← BLACK                    ▹ Case 1  
   z.p.p.color ← RED                    ▹ Case 1  
   z ← z.p.p                            ▹ Case 1    
  

  所以，变化后如下图所示：

• 插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子

  此时，解决对策是：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。即如下代码所示：

  	else if z == z.p.right  
   then z ← z.p                          ▹ Case 2  
   LEFT-ROTATE(T, z)                   ▹ Case 2  
  

所以红黑树由之前的：

变化成：

从而插入修复情况2转换成了插入修复情况3。

• 插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子

  解决对策是：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋，操作代码为：

   z.p.color ← BLACK                        ▹ Case 3  
   z.p.p.color ← RED                         ▹ Case 3  
   RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3 
  

最后，把根结点涂为黑色，整棵红黑树便重新恢复了平衡。所以红黑树由之前的： 变化成：

完整的js代码

	var RBTreeInsert = function (Tree, z) {
		// y始终指向x的父节点
		var y = null;
		// x指向当前树的根节点
		var x = Tree.root;
		while (x !== null) {
			y = x;
			if (z.key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
			// 为了找到合适的插入点，x探路跟踪路径，直到x成为null
		}
		// y 置为插入节点z的父节点
		z.parent = y;
	
		// 若y为空，则证明tree为空
		if (y === null) {	
			Tree.root = z;
		} else if (z.key < y.key) {
			y.left = z;
		} else {
			y.right = z;
		}
		z.left = null;
		z.right = null;
		z.color = 'red';
	
		RBTreeInsertFixUp(Tree, z);
	}
	
	var RBTreeInsertFixUp = function (Tree, z) {
		// 插入节点的父节点为red
		while(z.parent.color === 'red') {
			// 父节点为左节点
			if (z.parent = z.parent.parent.left) {
				// 叔叔节点
				var y = z.parent.parent.right;
				// case 1
				if (y.color === 'red') {	
					z.parent.color = 'black';
					y.color = 'black';
					z.parent.parent.color = 'red';
					z = z.parent.parent;
					continue;
				} else if (z = z.parent.right) {	// 当前点为右节点
					// case 2
					z = z.parent;
					leftRotate(Tree, z);
					continue;
					
				} else {
					// case 3
					z.parent.color = 'black';
					z.parent.parent.color = 'red';
					rightRotate(Tree, z.parent.parent);
					continue;
				}
			} else {
				var y = z.parent.parent.left;
				if (y.color === 'red') {
					// case 1
					z.parent.color = 'black';
					y.color = 'black';
					z.parent.parent.color = 'red';
					continue;
				} else if (z === z.parent.right) {
					// case 2
					z = z.parent;
					leftRotate(Tree, z);
					continue;
				} else {
					// case 3
					z.parent.color = 'back';
					z.parent.parent.color = 'red';
					rightRotate(Tree, z.parent.parent)
				}
			}
		}
		Tree.root.color = "black";
	}

红黑树插入情况

红黑树的所有插入情况有以下五种：

• 新节点N位于树的根上，没有父节点
• 新节点的父节点P是黑色
• 父节点P、叔叔节点U，都为红色
• 父节点P是红色，叔叔节点U是黑色或NIL (插入节点N是其父节点P的右孩子，而父节点P又是其父节点的左孩子)
• 父节点P是红色，而叔父节点U 是黑色或NIL (要插入的节点N 是其父节点的左孩子，而父节点P又是其父G的左孩子)

红黑树的删除

红黑树删除的节点的方法与常规二叉搜索树中删除节点的方法是一样的，如果被删除的节点不是有双非空子女，则直接删除这个节点，用它的唯一子节点顶替它的位置，如果它的子节点分是空节点，那就用空节点顶替它的位置，如果它的双子全为非空，我们就把它的直接后继节点内容复制到它的位置，之后以同样的方式删除它的后继节点，它的后继节点不可能是双子非空，因此此传递过程最多只进行一次。

二叉查找树的删除

继续讲解之前，补充说明下二叉树结点删除的几种情况，待删除的节点按照儿子的个数可以分为三种：

• 没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
• 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
• 有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删结点的位置。左儿子的最大元素其实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的结点。那就是最大的了。

二叉查找树的删除代码如下所示：

	REE-DELETE(T, z)  
	 1  if left[z] = NIL or right[z] = NIL  
	 2      then y ← z  
	 3      else y ← TREE-SUCCESSOR(z)  
	 4  if left[y] ≠ NIL  
	 5      then x ← left[y]  
	 6      else x ← right[y]  
	 7  if x ≠ NIL  
	 8      then p[x] ← p[y]  
	 9  if p[y] = NIL  
	10      then root[T] ← x  
	11      else if y = left[p[y]]  
	12              then left[p[y]] ← x  
	13              else right[p[y]] ← x  
	14  if y ≠ z  
	15      then key[z] ← key[y]  
	16           copy y's satellite data into z  
	17  return y