红黑树
前言
从jdk8.0开始HashMap进行了一次革新，为了提高查找效率在哈希桶内元素超过8个时自动变为红黑树结构。
红黑树到底是为了解决什么问题存在的？它又是怎么出现的？我们首先要理解一颗二叉查找树。
二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
.
当然如果要说二叉查找树的话我们必须从符号表说起，可我们今天的目的是为了简述红黑树，所以二叉查找树的各种实现就当大家都已经懂得。那为什么会出现红黑树呢，我们发现一种情况当输入的键值对键值按升序或者降序插入的时候，会有下图的情况出现
红黑树.png
而这种情况也是最糟糕的情况假设我们要查找键为5的结点，那么花费的时间就是最长的了，我们发现其实查找时间其实跟树的高度应该是呈现一种正比的关系。
那么可能有些同学想到了平衡二叉查找树，也就是任何节点的两个子树的高度最大差别为一。但是我们发现一个问题，那就是每次插入或者删除需要平衡次数非常多。那么有什么什么折中的方案既能保证能正常二叉查找树的性质又能保证查找的效率。
红黑树
没错就是红黑树，不过为了理解红黑树我们需要做一些准备工作，首先我们要了解一下B-树中最简单的2-3树。
这是一颗很神奇的树，包含2-结点(1个键两个链接)和3-结点(2个键3个链接)。
我们只要记住几点就是一个新的键插入2-结点直接变3-结点，
而当要插入到3-结点时，那么变成4-结点，4-结点中间的键值上升到父结点直到父节点是一个2-结点
或者到了根节点还不是2-结点那么根节点直接分解使高度加一
可能觉得2-3树已经完美解决我们的问题了,但现实往往不尽人意，为什么呢？？
首先表示一颗2-3树光表示2-结点和3-结点和它们之间的转换就需要花费力气，而且我们可能需要要跟结点之内的键值进行比较，而它实际插入情况7种，代表着光判断起码写7个if，2-3树解决我们的问题，可是实际书写显得比较复杂
我们需要一种简单的数据结构来解决我们的问题对了就是红黑树，它其实就是2-3树的变形.它其中有两种链接一种是红链接一种是黑链接(指向的结点颜色就是链接颜色)，用这两种链接就能表示我们2-3树。如下图。
当然红黑树有以下几个特点:
1.红链接均为左链接。
2.没有任何一个结点和两条红链接相连。
3.而且它是完美黑色平衡的(叶子结点到根结点黑色链接数量都是相同的)。
但是现实是残酷的，我们在对红黑树做操作的时候是有可能出现红色右链接或者连续两条红色链接。我们这时候可以通过旋转或者上移中键进行操作而对其进行操作
public class RBBST<Key extends Comparable<Key>, Value> {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
private Node left;
private Node right;
private boolean color;
private Key key;
private Value val;
private int N;
public Node(boolean color, Key key, Value val, int N) {
this.color = color;
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node n) {
if(n==null) {
return 0;
}
return n.N;
}
private boolean isRed(Node n) {
if(n==null) return false;
return n.color == RED;
}
private Node rotateLeft(Node n) {
Node x = n.right;
n.right = x.left;
x.left = n;
x.color = n.color;
n.color = RED;
x.N = n.N;
n.N = size(n.left)+size(n.right)+1;
return x;
}
private Node rotateRight(Node n) {
Node x = n.left;
n.left = x.right;
x.right = n;
x.color = n.color;
n.color = RED;
x.N = n.N;
n.N = size(n.left)+size(n.right)+1;//变了 变成x了
return x;
}
private void change2Conn(Node n) {
n.left.color = BLACK;
n.right.color = BLACK;
n.color = RED;
//return n;还是原来的
}
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node n, Key key, Value val) {
if(n==null) {
return new Node(RED, key, val, 1);
}
int cmp = key.compareTo(n.key);
if(cmp<0) n.left = put(n.left, key, val);
else if(cmp>0) n.right = put(n.right, key, val);
else n.val = val; //find key
if(!isRed(n.left)&&isRed(n.right)) n = rotateLeft(n);
if(isRed(n.left)&&isRed(n.left.left)) n = rotateRight(n);
if(isRed(n.left)&&isRed(n.right)) change2Conn(n);
n.N = size(n.left) + size(n.right) + 1;
return n;
}
}
你以为到这里就完了吗，本着求知的态度我们继续讲一讲HashMap这个Java里面无比精妙的类
HashMap 红黑树实现
就看两段代码理解了HashMap的红黑树实现也就大致理解了
左旋转
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
略微一看很难懂,这完全与我们自己的实现不同呀,传两个结点进来这是干什么？
跳过我们看具体插入的实现
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
是否感觉略微的不适与晕眩，但是你耐着性子看下去发现逻辑竟是如此的简单。
root代表着在Node[]这个表中每一个位置上第一个结点,而x就是我们需要插入这个位置的结点当然如果两者的key.equals(root.key)其实返回false不然就覆盖了
当x的父亲结点为空时，很明显它就直接返回。为了帮助更好理解这段代码我们尝试阅读这么两个函数
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
上面这一段是当一个哈希桶元素数超过8且其中表的长度大于64的时候发生的对哈希桶进行树型化。我们看到一开始是对根结点进行赋值的，但是中间插入了
balanceInsertion()这个函数意味着root是为了满足红黑树而不断变化的，而其中的moveRootToFront()是当本身在哈希桶第一个位置的元素不是root时进行把root赋值到哈希桶的第一个位置的值大概意思就是本来是以链表的形式存的，然后不断循环遍历已经通过
treeifyBin()中的replacementTreeNode()从Node类型变为TreeNode类型的结点然后每次都循环都相当于对红黑树插入一个结点，当然插入后需要修复红黑树看到这里我们可能明白了
rotateleft()的作用了,跟普通红黑树的左旋差不多，就是把右子树的左子树挂在右子树的父亲结点的左子树的地方，而右子树又变成它父亲结点的父亲，成为它父亲结点的父亲结点的儿子。可是有一点笔者逻辑思维有点混乱的是它的red属性是怎么变换，好像并不是按照正常方式左旋变换,因为左旋方法里面除了当是根结点的时候会让其变为false，而没有任何地方作出改变了。
