二叉排序树：https://blog.csdn.net/u014106644/article/details/89549048

二叉排序树对于每个节点key值，左节点<根节点<右节点，随机情况下可以实现对数级别的增删操作时间复杂度，在构建一颗二叉排序树时，当输入序列为有序时，则构建二叉排序树退化成为线性表，二叉树的高度为N，即算法时间复杂度为O(N)级别。

红黑树可以实现增加，删除以及查找等在O(logN)时间内完成，不论输入情况如何变化。

关于红黑树的实现定义有递归实现以及非递归实现，本文主要参考《算法第四版》，使用递归方法，从平衡2-3树出发来理解红黑树。

红黑树的一种定义描述：

1.节点是红色或黑色

2.根节点一定是黑色

3.每个叶节点都是黑色的空节点(NIL节点)

4.每个红节点的两个子节点都是黑色的(从每个叶子到跟的所有路径上不能有两个连续的红节点)(即对于层来说除了NIL节点，红黑节点是交替的，第一层是黑节点那么其下一层肯定都是红节点，反之一样)

5.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

2-3查找树

二叉排序树的每个节点有两个子节点，当输入序列有序时，树的高度会急剧增加。

在此对于二叉排序树进行进一步定义2-3查找树：

2-3查找树的节点或为空，或者是

（1）2节点：该节点一个值两个连接，左节点<根节点<右节点

（2）3节点：该节点2个值三个连接，三个连接被2个值划分大小关系

具体如下所示：

                                               

对于2-3查找树查找，增加以及删除具有一系列操作，可以实现对数级别的时间复杂度，由于2-3查找树中具有2种类型的节点，不便于表示，因此对于2-3查找进行变形，得到红黑树。

变形规则：将3节点两个值中间添加一条红连接（假设其余连接为黑连接），将3节点划分为两个2节点以及一条红连接，具体如下所示：

     

2-3查找树转化为红黑树，其中原来的3节点转化为两个2节点以及一条红连接，其余2节点的为黑连接。

红黑树的一种定义：

1.二叉排序树

2.红连接为左连接

3.没有任何一个节点同时与两个红连接相连

4.完美黑色平衡，即任意空连接到根节点路径上黑色连接数量相同

红连接指向的节点为红色，即如果通过2-3查找树方式来定义红黑树，首先得到红连接，然后红连接指向的节点为红色。

红黑树的基本变换

由于红黑树需要维持性质，红连接为左连接，一个节点不能同时与两个红连接相连。红黑树是一颗二叉排序树，在二叉排序树的插入操作过程中，首先找到新插入节点的合适位置，将新插入节点置为红节点，即将新建节点利用红连接与父节点相连。

假定红黑树原来是有序平衡的，新插入的节点进来以后会破坏红黑树的平衡性，因此需要进行调整，具体需要的变换形式只有三种，左旋转，右旋转以及颜色变换，利用这三种变换方式，可以实现红黑树的平衡调整。

首先定义Node节点

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node{
		private Key key;
		private Value val;
		private Node left, right;
		private int N;
		private boolean color;
		
		public Node(Key key, Value val, int N, boolean color){
			this.key = key;
			this.val = val;
			this.N = N;
			this.color = color;
		}
	}

1.左旋转

旋转方向指的是红连接的旋转方向，例如左旋转指的是将h的右节点左旋转。

将x指向h的右节点

将h.right指向x.left

将x.left指向h

将x颜色设置为h颜色，将h设置为红色

                      

代码实现如下所示:

        //左旋转h的右连接
	private Node rotateLeft(Node h){
		//System.out.println("rotateleft before " + h);
		//修改连接
		Node x = h.right;
		h.right = x.left;
		x.left = h;
		//修改颜色
		x.color = h.color;
		h.color = RED;
		//修改数量
		x.N = h.N;
		h.N = size(h.left)+size(h.right)+1;
		//System.out.println("rotateleft after " + x);
		return x;
	}

2.右旋转

右旋转实现将h的左节点右旋转

将x指向h.left

将h.left指向x.right

将x.right指向h

将x颜色设为h颜色，将h颜色设为红节点

                

代码如下：

        //右旋转h的左连接
	private Node rotateRight(Node h){
		Node x = h.left;
		h.left = x.right;
		x.right = h;
		x.color = h.color;
		h.color = RED;
		x.N = h.N;
		h.N = size(h.left)+size(h.right)+1;
		return x;
	}

3.颜色变换

由于一个节点不能同时与2个红连接相连，当出现该情况时，需要进行颜色变换，将两个子节点变为黑色，父节点变为红色

                        

        private void flipColors(Node h){
		h.color = RED;
		h.left.color = BLACK;
		h.right.color = BLACK;
	}

利用以上三种变换可以实现新插入节点时调整红黑树的平衡性。以后分析新节点插入时的各种情况，论证三种变换可以实现新插入节点的平衡性调整。

红黑树的插入原理

红黑树是一颗二叉排序树，在二叉排序树的插入操作过程中，首先找到新插入节点的合适位置，将新插入节点置为红节点，即将新建节点利用红连接与父节点相连。在插入过程中，找到待插入位置后，新建一个红节点添加到红黑树中，然后利用三种变换调整红黑树，使其满足其基本性质：

2.红连接为左连接

3.没有任何一个节点同时与两个红连接相连

由待插入位置不同可以分为以下8种情况：

1.在单个2-节点插入新节点

即此时红黑树只有一个根节点，由于新节点与2节点值比较，可以分为左插入与右插入。在左边插入，红黑树平衡性没有被破坏；在右边插入，由于出现红连接为右连接，需要将红连接左旋转，进行左旋转变换即可维持红黑树性质。

       

2.向树底部2-节点插入新节点

即向红黑树的某个叶子结点中插入，且该节点对应原来2-3是一个2-节点，分为左边插入与右边插入，左边插入不需要变换，右边插入需要进行一次左旋转，即与第一种情况相同。

                  

向单个3-节点插入新节点，根据插入节点与3节点的两个值大小关系，有三种情况，插入值最小，插入值最大，插入值介于3节点值之间

3.向单个3节点插入新节点，且新节点最大

如下所示，将a,b看成2-3查找树中3节点，新插入节点c大于两者，即新插入节点位于b右子树，新建节点为红色，需要进行颜色变换

     

4.向单个3节点插入新节点，且新节点最小

向b,c中插入a,此时b与两红连接相连，对于c执行右旋转，对于b进行颜色变换，即可维持红黑树有序性

5.向单个3节点插入新节点，且新节点介于两者之间

向a,c中插入b,此时出现右连接，将a左旋转，此时b与两个红连接连接，将c右旋转，进行颜色变换，最终维持红黑树的平衡性。

   

6.向树底3节点插入新节点，且新节点最小

向sr三节点插入h,进行右旋转，颜色变换，左旋转，最终可以实现平衡。

7.向树底3节点插入新节点，且新节点最大

向sr3节点插入x,进行颜色变换，左旋转即可维持平衡

  

8.向树底3节点插入新节点，且新节点介于两者之间

向hr中插入N,左旋转，右旋转，颜色变换，左变换可以维持平衡。

由以上分析可知，在一颗有序平衡的红黑树中插入一个新节点大致有以下几种情况：

1.单个2节点

2.树底部2节点

3.单个3节点

4.树底部3节点

对于每种情况，由于插入值与节点值大小关系，又可以分为几种子情况，不论何种情况，都可以使用左旋转，右旋转，颜色变换来维持红黑树的平衡。其实观察上述各种过程变化，其基本思想是由于新插入节点置为红节点，产生红连接，需要将该红连接向上传递，从而实现维持平衡。

红连接的向上传递过程

由下图可以明确，其实状态为3节点，无论在3节点的拿个位置插入，最终通过基本变换都可以转换为右下角状态，当转换为右下角状态时，如果其父节点非空则继续将红连接向上传递，如果父节点为空，则将说明此时节点为根节点，将红连接改为黑连接即可。

   

当在一颗红黑树中，插入一个新节点时，首先找到一个叶子结点进行插入，将插入的节点置为红色，按照以下顺序进行变换即可保证平衡性，对于该叶子节点进行检查：

1.如果右节点为红色，左节点为黑色，执行左旋转

2.如果左节点为红色，左节点的左节点为红色，执行右旋转

3.如果左右节点都为红色，执行颜色变换

红黑树插入操作实现

结合二叉排序树的插入操作，最终红黑树的插入操作实现如下所示：

        public void put(Key key, Value val){
		root = put(root, key, val);
		root.color = BLACK;
	}
	
	private Node put(Node h, Key key, Value val) {
		if(h == null)
			return new Node(key, val, 1, RED);		
		int cmp = key.compareTo(h.key);
		if(cmp>0)
			h.right = put(h.right, key, val);
		else if(cmp<0)
			h.left = put(h.left, key, val);
		else
			h.val = val;
		if(!isRed(h.left)&&isRed(h.right))
			h = rotateLeft(h);
		if(isRed(h.left)&&isRed(h.left.left))
			h = rotateRight(h);
		if(isRed(h.left)&&isRed(h.right))
			flipColors(h);
		h.N = size(h.left) + size(h.right) + 1;
		return h;		
	}
	
	private boolean isRed(Node x){
		if(x == null) return false;
		return x.color;
	}

测试如下：

当输入有序序列时，二叉排序树与红黑树最终构造结果如下：

              RBT<String, String> rbt = new RBT<>();
		BST<String, String> bst = new BST<>();
		String[] str = new String[]{"A","C","E","H","L"};
		for(String s : str){
			rbt.put(s, s);
			bst.put(s, s);
		}
		rbt.printBinaryTree2();
		bst.printBinaryTree2();

如下图所示：红黑树的高度为3，而二叉排序树为5，即红黑树的性能要好。

               

学习红黑树，建议学习路径如下，可以参考算法第四版，讲解的太精彩了，下一步研究一下删除，以及图形化显示等问题。

二叉排序树------>2-3查找树-------->红黑树

代码地址：https://github.com/ChenWenKaiVN/TreeSWT/blob/master/src/com/tree/rbt/RBT.java