平衡树之红黑树思想及实现
前言
之前我们学习过二叉查找树，发现它的查询效率比单纯的链表和数组的查询效率要高很多，大部分情况下，确实是这样的，但不幸的是，在最坏情况下，二叉查找树的性能还是很糟糕。
例如我们依次往二叉查找树中插入9,8,7,6,5,4,3,2,1这9个数据，那么最终构造出来的树是长得下面这个样子：
我们会发现，如果我们要查找1这个元素，查找的效率依旧会很低。效率低的原因在于这个树并不平衡，全部是向左边分支，如果我们有一种方法，能够不受插入数据的影响，让生成的树都像完全二叉树那样，那么即使在最坏情况下，查找的效率依旧会很好。
本文讲解平衡树中2-3查找树的思想，并依据2-3查找树的思想，实现红黑树。
一、2-3查找树
1. 什么是2-3查找树？
为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切的说，我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链)，而现在我们引入3-结点，它含有两个键和三条链。2-结点和3-结点中的每条链都对应着其中保存的键所分割产生的一个区间。
基于以上思想，一颗2-3查找树，要么为空，要么满足以下2个条件：
- 2-结点：
含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。 - 3-结点：
含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
2. 2-3查找树的查找思想
将二叉查找树的查找算法一般化，我们就能够直接得到2-3树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较，如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找。如果这个是空链接，查找未命中。
3. 2-3查找树的插入思想
- 向2-结点中插入新键
往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-结点，那么很容易，我们只需要将新的元素放到这个2-结点里面使其变成一个3-结点即可。 - 向一棵只含有一个3-结点的树中插入新键
假设2-3树只包含一个3-结点，这个结点有两个键，没有空间来插入第三个键了，最自然的方式是我们假设这个结点能存放三个元素，暂时使其变成一个4-结点，同时他包含四条链接。然后，我们将这个4-结点的中间元素提升，左边的键作为其左子结点，右边的键作为其右子结点。插入完成，变为平衡2-3查找树，树的高度从0变为1。 - 向一个父结点为2-结点的3-结点中插入新键
和上面的情况一样一样，我们也可以将新的元素插入到3-结点中，使其成为一个临时的4-结点，然后，将该结点中的中间元素提升到父结点即2-结点中，使其父结点成为一个3-结点，然后将左右结点分别挂在这个3-结点的恰当位置。 - 向一个父结点为3-结点的3-结点中插入新键
当我们插入的结点是3-结点的时候，我们将该结点拆分，中间元素提升至父结点，但是此时父结点是一个3-结点，插入之后，父结点变成了4-结点，然后继续将中间元素提升至其父结点，直至遇到一个父结点是2-结点，然后将其变为3-结点，不需要继续进行拆分。 - 分解根结点
当插入结点到根结点的路径上全部是3-结点的时候，最终我们的根结点会变成一个临时的4-结点，此时，就需要将根结点拆分为两个2-结点，树的高度加1。
4. 2-3查找树的性质
通过对2-3树插入操作的分析，我们发现在插入的时候，2-3树需要做一些局部的变换来保持2-3树的平衡。一棵完全平衡的2-3树具有以下性质：
- 任意空链接到根结点的路径长度都是相等的。
- 4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。
- 2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。
二、红黑树
1. 什么是红黑树？
-
2-3查找树确实保证了最坏情况下的时间复杂度，但是2-3查找树实现较复杂，为了继续使用标准二叉查找树的查找方法，我们可以对标准二叉查找树稍加修改，使其满足2-3查找树的思想，将标准的二叉查找树达到平衡，而红黑树就是如此实现。
-
红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：
红链接：将两个2-结点连接起来构成一个3-结点；
黑链接：则是2-3树中的普通链接。
确切的说，我们将3-结点表示为由由一条左斜的红色链接相连的两个2-结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。 -
由以上分析可得红黑树的如下定义：
-
红黑树是含有红黑链接并满足下列条件的二叉查找树：
1.红链接均为左链接；
2.没有任何一个结点同时和两条红链接相连；
3.该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；
下面是红黑树与2-3树的对应关系：
2. 红黑树的实现思想
1. 红黑树的平衡化思想
红黑树有两个条件，第一红链接必须是左链接，第二，一个节点只能和一个红链接相连；但是，每次插入一个结点都可能破坏这两个条件，导致树的不平衡。因此，为了使得一个结点插入后，仍然满足红黑树的条件，需要对插入一个结点后，使得不满足红黑树条件的结点进行调整，使其满足红黑树条件。
1.1左旋：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
- 左旋思路
假设当前结点为h，它的右子结点为x；
1.让x的左子结点变为h的右子结点：h.right=x.left;
2.让h成为x的左子结点：x.left=h;
3.让h的color属性变为x的color属性值：x.color=h.color;
4.让h的color属性变为RED：h.color=true;
1.2右旋：当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋
- 右旋思路
假设当前结点为h，它的左子结点为x；
1.让x的右子结点成为h的左子结点：h.left = x.right;
2.让h成为x的右子结点：x.right=h;
3.让x的color变为h的color属性值：x.color = h.color;
4.让h的color为RED；
1.3颜色反转
当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。
1.4约定红黑树的根节点颜色为黑色
在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色，由于根结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。
2. 红黑树的插入思想
- 向单个2-结点中插入新键
1.如果新键小于当前结点的键，我们只需要新增一个红色结点即可，新的红黑树和单个3-结点完全等价。
2.如果新键大于当前结点的键，那么新增的红色结点将会产生一条红色的右链接，此时我们需要通过左旋，把红色右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红色链接。 - 向一棵双键树(即一个3-结点)中插入新键
1.新键大于原树中的两个键
2.新键小于原树中的两个键
3.新键介于原数中两个键之间
3. 红黑树的代码实现
红黑树相比标准查找二叉树的实现基本一致，就是结点中多了一个标记指向该结点链接的颜色，然后插入实现的时候，多加上进行平衡化的三种操作而已。
- API设计
- 代码实现
package sun.tree;
// 红黑树 数据结构
// （红黑树就是普通二叉查找树的改进，只是为节点增加了颜色属性使得其具有2-3树的特征。
// 相比普通二叉查找树，红黑树的插入方法，在最后多了平衡树的调整操作，其它均与普通二叉查找树的实现一致）
public class RedBlackTree<Key extends Comparable<Key>,Value> {
private Node root; //记录根结点
private int N;//记录树中元素的个数
private static final boolean RED = true;//红色链接标识，不可修改变量，主要是为true起个别名，方便代码阅读
private static final boolean BLACK =false;//黑色链接标识，不可修改变量，主要是为false起个别名，方便代码阅读
//获取树中元素的个数
public int size()
{
return N;
}
//判断当前结点的父指向链接是否为红色
private boolean isRed(Node x)
{
if (x==null)
return BLACK;
return x.color==RED;
}
//左旋调整
private Node rotateLeft(Node curr)
{
//1.获取当前节点的右子结点，并赋值给为curr_right
Node curr_right = curr.right;
//2.将curr_right的左子结点成为curr的右子结点
curr.right=curr_right.left;
//3.将curr成为curr_right的左子结点
curr_right.left=curr;
//4.将curr的颜色值成为curr_right的颜色值
curr_right.color=curr.color;
//5.将curr的颜色值成为红色
curr.color=RED;
return curr_right;
}
//右旋调整
private Node rotateRight(Node curr)
{
//1.获取当前节点的左子结点，并赋值给为curr_left
Node curr_left = curr.left;
//2.将curr_left的右子结点成为curr的左子结点
curr.left=curr_left.right;
//3.将curr成为curr_left的右子结点
curr_left.right=curr;
//4.将curr的颜色属性成为curr_left的颜色属性
curr_left.color=curr.color;
//5.将curr的颜色属性赋值为红色
curr.color=RED;
return curr_left;
}
//颜色反转,相当于完成拆分4-结点
private void flipColors(Node curr)
{
//1.当前结点链接颜色变为红色
curr.color=RED;
//2.当前结点的左右子结点的链接颜色变为黑色
curr.left.color=BLACK;
curr.right.color=BLACK;
}
//在整个树上完成插入操作
public void put(Key key, Value val)
{
root = put(root, key, val);
//由于插入后的平衡操作，可能导致根结点的颜色为红色，但是根结点的颜色要求一直为黑色
root.color=BLACK;
}
//在指定树中，完成插入操作,并返回添加元素后新的树
private Node put(Node curr, Key key, Value val)
{
//如果当前结点为空，将插入结点的颜色赋为红色即可,完成真正插入动作。
if (curr==null)
{
//元素个数+1
N++;
return new Node(key,val,RED,null,null);
}
//比较当前结点与待插入结点的大小，递归完成插入
int cmp = key.compareTo(curr.key);
if (cmp<0)
{
curr.left=put(curr.left,key,val);
}
else if (cmp>0)
{
curr.right=put(curr.right,key,val);
}
else
{
curr.value=val;
}
//调整红黑树，使插入结点后，保证树的平衡性
//左旋操作:如果当前节点的左结点颜色为黑色，右结点颜色为红色，则执行该操作
if (!isRed(curr.left) && isRed(curr.right))
{
curr = rotateLeft(curr);
}
//右旋操作：如果当前结点的左结点颜色为红色，左结点的左结点仍为红色，则执行该操作
if (isRed(curr.left) && isRed(curr.left.left))
{
curr = rotateRight(curr);
}
//颜色反转操作：如果当前结点的左结点为红色，右结点为红色，则执行该操作
if (isRed(curr.left) && isRed(curr.right))
{
flipColors(curr);
}
return curr;
}
//根据key，从树中找出对应的值
public Value get(Key key)
{
return get(root,key);
}
//从指定的树x中，找出key对应的值
private Value get(Node x, Key key)
{
if (x==null)
return null;
int cmp = key.compareTo(x.key);
if (cmp<0)
{
return get(x.left,key);
}
else if (cmp>0)
{
return get(x.right,key);
}
else
{
return x.value;
}
}
private class Node
{
Key key;
Value value;
boolean color;//父结点指向该结点的链接颜色，如果color为true,则表示红色，否则表示黑色
Node left;
Node right;
public Node(Key key,Value value,boolean color,Node left,Node right)
{
this.key=key;
this.value=value;
this.color=color;
this.left=left;
this.right=right;
}
}
}