关于红黑树
hashmap中的处理有红黑树的参与，我了解了一下红黑树
红黑树 并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以 O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
接下来，用Java完成了添加和删除操作：
基础：
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* root root
* / /
* x p
* / \ --(左旋)-. /
* lx p x rp
* / \ /
* lp rp lx lp
*
*
*/
private <K,V extends Comparable<V>> void rightRotate(TreeNode<K,V> x, TreeNode<K,V> root){
TreeNode<K,V> p=x.right;
if(p.left!=null){
x.right=p.left;
}
if(p.left!=null){
p.left.parent=x;
}
if (x.parent == null) {
root=p;//x为根节点的时候
} else {
if (x.parent.left == x)
x.parent.left = p;
else
x.parent.right = p;
}
p.left=x;
x.parent=p;
}
右旋:
/*
- 对红黑树的节点(x)进行右旋转
- 右旋示意图(对节点x进行左旋)：
py py/ /x p/ \ --(右旋)-.>> / \p rx lp x/ \ / \lp rp rp rx
*/
private <K,V extends Comparable<V>> void leftRotate(TreeNode<K,V> x,TreeNode<K,V> root){
TreeNode<K,V> p=x.right;
if(p.right!=null){
x.left=p.right;
}
if(p.right!=null){
p.right.parent=x;
}
if (x.parent == null) {
root=p;//x为根节点的时候
} else {
if (x.parent.right == x)
x.parent.left = p;
else
x.parent.right = p;
}
p.left=x;
x.parent=p;
}
}
插入：
* 1.将红黑树当做一颗二叉树，将节点插入
* 2.将节点的颜色变为红色
* 3.接下来就是调整使其成为红黑树
*红黑树的特点：
*每个节点或者是黑色，或者是红色。
*根节点是黑色。
*每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
*如果一个节点是红色的，则它的子节点必须是黑色的。
* 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
* @param n
* @param root 根节点
* @param <K>
* @param <V>
*/
private <K,V extends Comparable<V>> void insert(TreeNode<K,V> n,TreeNode<K,V> root){
while (root != null) {
if (n.key.compareTo(root.key) < 0)
root =root.left;
else
root= root.right;
}
TreeNode<K, V> p=null;
if(root==null){
root=n;
}else {
p = root.parent;
}
n.parent=p;
n.red=true;
//加节点
if(n.key.compareTo(p.key)>0){
p.right=n;
}else {
p.left=n;
}
insertRedTree(n,root);
}
private <K, V extends Comparable<V>> void insertRedTree(TreeNode<K, V> n,TreeNode<K, V> root) {
TreeNode<K, V> parent=n.parent;
//是根节点直接将颜色变为黑色
if(n.parent==null){
n.red=false;
}
while((parent=n.parent)!=null&&parent.red){
TreeNode<K, V> gParent=n.parent.parent;
//当前节点的父节点与其兄弟节点都为红色的时候
if(gParent.left.red&&gParent.right.red||(gParent.left.red&&gParent.right!=null)||(gParent.right.red&&gParent.left!=null)){
gParent.right.red=false;
gParent.left.red=false;
gParent.red=true;
n=gParent;
continue;
}
//其兄弟节点是黑色，且当前节点是右孩子
if(n==parent.right){
n=parent;
parent=n.parent;
n.leftRotate(n,root);
}else{
//其兄弟节点是黑色，且当前节点是左孩子
parent.red=false;
gParent.red=true;
n.rightRotate(gParent,root);
}
}
root.red=false;
}
删除：
private <K, V extends Comparable<V>> void remove(TreeNode<K, V> n,TreeNode<K, V> root){
TreeNode<K, V> child, parent;
if(n.left!=null&&n.right!=null){
//被删除节点有两个儿子。
// 那么，先找出它的后继节点；
// 然后把“它的后继节点的内容”复制给“该节点的内容”；
// 之后，删除“它的后继节点”。
// 在这里，后继节点相当于替身，
// 在将后继节点的内容复制给"被删除节点"之后，
// 再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了.
TreeNode<K, V> replace = n;
// 获取后继节点
replace = replace.right;
while(replace.left!=null){
replace=replace.left;
}
/**
*
* O
* /
* x y
* /
* p rx
* / \ /
* lp rp a b
*
* x的后继结点是a
*/
if(n.parent==null){
root=replace;
}else {
if(n.parent.left==n){
n.parent.left=replace;
}else {
n.parent.right = replace;
}
}
child=replace.right;
parent=replace.parent;
boolean color=replace.red;
//将后继节点覆盖删除的值，将后继节点的right接到parent上
if(parent==n){
parent=replace;
}else{
if(child!=null){
child.parent=parent;
parent.left=child;
replace.right=n.right;
n.right.parent=replace;
}
}
//属性全部替代
replace.parent = n.parent;
replace.red = n.red;
replace.left = n.left;
n.left.parent = replace;
//如果原先颜色是黑色的
if(!color){
//维持红黑树的特性
removeRedTree(child, parent,root);
}
n=null;
return;
}
//被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
if (n.left !=null) {
child = n.left;
} else {
child = n.right;
}
parent = n.parent;
// 保存"取代节点"的颜色
boolean color = n.red;
if (child!=null)
child.parent = parent;
// "node节点"不是根节点
if (parent!=null) {
if (parent.left == n)
parent.left = child;
else
parent.right = child;
} else {
root = child;
}
if (color == false)
removeRedTree(child, parent,root);
n = null;
}
private <K, V extends Comparable<V>> void removeRedTree(TreeNode<K, V> n, TreeNode<K, V> parent, TreeNode<K, V> root) {
TreeNode<K,V> p;
while((n==null||n.red)&&n.parent!=null) {
if (parent.left == n)
p = parent.right;
else p=parent.left;
//x是“黑+黑”节点，x的兄弟节点是红色。
if (p.red) {
p.red=false;
parent.red=true;
p.leftRotate(parent,root);
p= parent.right;
}
// x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
if ((p.left==null || !p.left.red) &&
(p.right==null || !p.right.red)) {
p.red=true;
n = parent;
parent = n.parent;
}
else {
//x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
if (p.right==null || !(p.right.red)) {
p.left.red=false;
p.red=true;
p.rightRotate(p,root);
p = parent.right;
}
//x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
p.red=p.parent.red;
p.parent.red=false;
p.right.red=false;
p.leftRotate(parent,root);
n=root;
break;
}
}
}
此文参考了网上的实现
读源码，是我们了解大神领域的一大捷径
生命不息，奋斗不止
