算法之红黑树

JDK1.8引入了红黑树(HashMap,CurrentHashMap)

红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对数时间内完成查找的数据结构。这个时候，红黑树站了出来。 

阅读以下需要了解普通二叉树的插入以及删除操作。 

红黑树是在普通二叉树上，对没个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质 

红黑树需要满足的五条性质： 

性质一：节点是红色或者是黑色； 

在树里面的节点不是红色的就是黑色的，没有其他颜色，要不怎么叫红黑树呢，是吧。 

性质二：根节点是黑色； 

根节点总是黑色的。它不能为红。 

性质三：每个叶节点（NIL或空节点）是黑色； 

这个可能有点理解困难，可以看图： 

从根节点出发，到叶子节点每条路径上黑色节点数目相同。

性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）； 

这五条性质约束了红黑树，可以通过数学证明来证明，满足这五条性质的二叉树可以将查找删除维持在对数时间内。 

当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。