红黑树

像二叉查找树之类的数据结构，都会存在最坏的情况，这就需要我们构造一种二叉树能够保证无论如何构造它，运行时间都是对数级别的。

二三查找树

所谓的二三查找树就是把二叉搜索树拓展为上图式样，2-结点含有1个键两条链接，3-结点含有2个键3条链接；左边代表小于，右边代表大于，中间代表中间值，将原先的2维拓展为3维，可以有效的缓解最坏情况出现的可能性,再配以妥善的插入算法，可以很高效的处理插入后的平衡问题；

插入操作：

先进行未命中的查找，如果结束于一个2-结点，则将二节点拓展成3-结点；

对于三节点需要分情况：

只有3-节点的树插入：

父节点为2-节点的3-节点中插入新键：

先进行4-节点拓展，然后将四节点换为2分解为2-3树，但中间值上移与之前的形成一个3-节点；

父节点为3-节点的3-节点插入：

将上述算法推广，构造4节点，上移，继续构成4-节点，上移，直到遇到一个2-节点，构成3-节点；

如果根节点本来就是3-树，插入后进行变化，变成2个2-3树：

2-3树的生成是从下往上的：
对于1-10的插入，二叉查找树高度为9，而2-3树高度为2；

命题：
在大小为N的2-3查找树中，查找和插入操作访问的节点必然不超过$lgN$个；

2-3查找树处理每个结点的时间都不会超过某个很小的常数，此外任何插入和查找的复杂度都只不过是对数级别，但是由于有两种节点，还有一种临时节点4-（可不计，因为会直接上移），因而管理数据结构较为复杂，因而使用红黑树来进行处理

红黑树

如上图所示，红黑树对2-3树的-3节点进行了转化，3-节点使用一条左斜的红色链接相连的2-节点构成，称为红链接，而黑链接就是普通的链接；这种表示法的优点是可以直接使用标准的二叉搜索树的get()方法；

other definition:

• 红链接均为左链接；
• 没有任何一个结点同时和两个红–相连；（顶多是3-结点）
• 该数是完美黑色平衡的，即任意空链接到根节点路径上的黑链接数量相同；

满足如上定义的红黑树和2-3树是一一对应的；

将红链接画平就构成了一棵2-3树，因而红黑树在保持了二叉搜索树的基础上，又增加了2-3树的性质定义，因而结合了二叉搜索树中简洁高效的查找方法以及2-3树中高效的插入算法；

颜色表示

红色异或黑色指的都是指向该节点的链接的颜色；

java

private static final boolean RED=ture;
private static final boolean BLACK=false;
private class Node{
    Key key;//键
    Val val;//关联的值
    Node left,right;
    int N;
    boolean color;
}
Node(Key key,Val val,int N,boolean color){
    this.key=key;
    this.val=val;
    this.N=N;
    this.color=color;
}

private boolean isRed(Node x){
    if(x==null)
    {
        return false;
    }
    return x.color==RED
}

旋转

在实现某些操作的时候会出现红色右链接或者连续两条红链接，就需要进行旋转的操作；

向单个2-结点中插入新键

只有一个单节点，插入的点如果小于此点则向右边插入，形成一个红色的点，如果大于此节点就要向右边插入在右边形成一个红链接，因此需要进行左旋转

向树底部的2-结点插入新键

如果他的父节点是一个2-结点，那么上面的方式仍然有用。但如果指向新节点的是父节点的左链接，那么父节点直接就成为了一个3-结点，需要一次左旋转；

向一棵二键树（即一个3-结点）中插入新键

• 新键大于原先的2个，直接插入右边，将两条新形成的红线还原；
• 新键小于原先的2个，形成了连续两个左红链，因此先右旋上一个红链，然后变为上题的模式，进行还原；
• 如果恰好位于中间值，会形成上一个左红，接一个右红，因此先左旋右红，然后右旋上一个左红，还原；

颜色转换

专门用flipColors()来转换一个结点的两个红色子节点的颜色。除了将子节点的颜色由红变黑之外，还要将父节点的颜色由黑变红；

根结点总是黑色的

红色的根结点说明根结点是一个3-节点的一部分。我们每次插入后都会将根结点设为黑色。当根结点由红变黑的时候树的黑链接高度都会增加1；

java

package 红黑树;

import bst二叉搜索树.BST;
import edu.princeton.cs.algs4.BlackFilter;

/**
 * @author lszzz
 * @create 2020/5/22
 */
public  class BRT<Key extends  Comparable<Key>,Val> {
	private static final boolean RED=true;
	private static final boolean BLACK=false;
	private Node root;
	private class Node {
		Key key;
		Val val;
		Node left, right;
		int N;
		boolean color;

		Node(Key key, Val val, int N, boolean color) {
			this.key=key;
			this.val=val;
			this.N=N;
			this.color=color;
		}
		private boolean isRed(Node x){
			if(x==null)
			{
				return false;
			}
			return x.color;
		}
	}

	private int size(Node x) {
		if (x == null) {
			return 0;
		}
		return x.N;
	}

	/**
	 * 左旋
	 * @param h
	 * @return
	 */
	private Node rotateLeft(Node 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=1+size(h.left)+size(h.right);
		return x;
	}
	/**
	 * 右旋
	 */
	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=1+size(h.left)+size(h.right);
		return x;
	}

	/**
	 * 颜色转换函数：转换一个结点的两个红色子节点，将子节点由红
	 * 变黑，父节点变红
	 */
	private void flipColors(Node h)
	{
		h.color=RED;
		h.left.color=BLACK;
		h.right.color= BLACK;
	}

	public void put(Key key,Val val)
	{
		root=put(root,key,val);
		root.color=BLACK;
	}
	private boolean isRed(Node h)
	{
		return h.color==RED;
	}

	private Node put(Node h,Key key,Val val)
	{
		if(h==null)
		{
			//父节点和红链接相连
			return new Node(key,val,1,RED);
		}
		int cmp=key.compareTo(h.key);
		if(cmp<0) h.left=put(h.left,key,val);
		else if(cmp>0) h.right=put(h.right,key,val);
		else h.val=val;
		
		if(isRed(h.right)&&!isRed(h.left)) 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;
	}

}

上述的插入操作还是基于之前的二三树对于插入操作，考虑到当前以及之后只有三种可能，1.对于右边为红，左边为黑，由于不符合二三树的实质，所以需要对中间点进行左旋；2.用于递归之后的处理：左边的左边还为红，需要中间右旋，变为3的情况；3.对于两边都为红，直接变黑，然后中间节点变红。

删除

实现删除操作仍然是基于2-3树的，上面的2-3树插入算法可以改写为插入时寻找的时候把途中所有的4-树都给进行变化，向上生长1.只需将flipColor代码上一到null判断之后即可；

删除最小键：对于2-3树来说如果删除的键位于2-树那么此节点就会变空，影响树的平衡性，所以需要进行变换，保证树中没有2-节点:

• 如果当前节点的左子节点不是二节点，完成；
• 如果当前节点的左子节点是2-节点但它的兄弟节点不是2-节点，将左子节点的兄弟节点移动一个键到左子节点中；
• 如果当前子节点的左子节点和亲兄弟节点都是2-节点，直接将左子节点父节点中的最小键和左子节点最近的兄弟接地那合并为一个4-节点，使父节点由一个3-节点变为一个2-节点

为什么需要红黑树？

（为什么有了平衡树还需要红黑树？）

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在$O(logn)$,但是由于每个节点的左子树和右子树之差至多为1要求过于严格，导致每次进行插入和删除操作的时候都要不断的进行左旋和右旋操作，使其符合一个平衡树的要求，导致性能大打折扣，因而有了红黑树，红黑树大概可以描述成一个对平衡要求不那么高的平衡二叉树。

单论查找效率的话平衡树快于红黑树，但是插入和删除操作红黑树的效率又要高于平衡树；红黑树一般应用于HashMap、TreeMap、Set等容器的底层实现；