紅黑樹（Red-Black Tree）试溯，一種特殊的二叉查找樹弓乙，紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色渊抄，可以是紅(Red)或黑(Black)；
紅黑樹主要是用它來(lái)存儲(chǔ)有序的數(shù)據(jù)巢块，它的時(shí)間復(fù)雜度是O(lgn)礁阁，效率非常高；
紅黑樹是一種近似平衡的二叉查找樹族奢，它能夠確保任何一個(gè)節(jié)點(diǎn)的左右子樹的高度差不會(huì)超過(guò)二者中較低那個(gè)的一倍姥闭；
例如Java集合中TreeMap，TreeSet越走，HashMap等棚品，以及Linux虛擬內(nèi)存的管理
紅黑樹的特性:
- 每個(gè)節(jié)點(diǎn)或者是黑色靠欢，或者是紅色；
- 根節(jié)點(diǎn)是黑色铜跑；
- 每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色门怪。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)]锅纺；
- 如果一個(gè)節(jié)點(diǎn)是紅色的掷空，則它的子節(jié)點(diǎn)必須是黑色的；
- 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)囤锉。
性質(zhì)3中指定紅黑樹的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)拣帽，而且并葉子節(jié)點(diǎn)都是黑色。但 Java 實(shí)現(xiàn)的紅黑樹將使用 null 來(lái)代表空節(jié)點(diǎn)嚼锄，因此遍歷紅黑樹時(shí)將看不到黑色的葉子節(jié)點(diǎn)，反而看到每個(gè)葉子節(jié)點(diǎn)都是紅色的蔽豺。
性質(zhì)4的意思是：從每個(gè)根到節(jié)點(diǎn)的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)区丑，但黑色節(jié)點(diǎn)是可以連續(xù)的。 因此若給定黑色節(jié)點(diǎn)的個(gè)數(shù) N修陡，最短路徑的情況是連續(xù)的 N 個(gè)黑色沧侥，樹的高度為 N - 1;最長(zhǎng)路徑的情況為節(jié)點(diǎn)紅黑相間，樹的高度為 2(N - 1) 魄鸦。
性質(zhì)5是成為紅黑樹最主要的條件宴杀，紅黑樹的插入、刪除操作都是為了遵守這個(gè)規(guī)定拾因。紅黑樹是相對(duì)是接近平衡的二叉樹旺罢。它以性質(zhì) 5 作為一種平衡方法，使自己的性能得到了提升绢记。特性5確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍扁达。
當(dāng)對(duì)紅黑樹進(jìn)行增刪操作時(shí)，以上約束條件可能被破壞蠢熄，需要通過(guò)調(diào)整使得查找樹重新滿足紅黑樹的約束條件跪解。調(diào)整可以分為兩類：一類是顏色調(diào)整，即改變某個(gè)節(jié)點(diǎn)的顏色签孔；另一類是結(jié)構(gòu)調(diào)整叉讥，集改變檢索樹的結(jié)構(gòu)關(guān)系。結(jié)構(gòu)調(diào)整過(guò)程包含兩個(gè)基本操作：左旋和右旋饥追。
一個(gè)不錯(cuò)的在線演示添加图仓、刪除紅黑樹：http://sandbox.runjs.cn/show/2nngvn8w
紅黑樹node定義：
class Entry<K extends Comparable<K>,V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public Entry(K key, boolean color, Entry<K,V> parent, Entry<K,V> left,Entry<K,V> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
紅黑樹插入：
圖解；來(lái)源自：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/5-TreeSet%20and%20TreeMap.md
add.png
/**
* put方法 insert到紅黑樹
*/
public V put(K key, V value) {
if(key == null) {
throw new NullPointerException("key不能為空判耕！");
}
int cmp;
Entry<K,V> parent;
Entry<K,V> t = root;
// 第一次插入
if (t == null) {
root = new Entry<>(key, value, null);
root.color = BLACK;
return null;
}
do {
parent = t;
cmp = key.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
// 找到key的value透绩，更新value并返回舊value
V oldValue = t.value;
t.value = value;
return oldValue;
}
} while (t != null);
// 插入新node
Entry<K,V> entry = new Entry(key, value, parent);
// 設(shè)置新增節(jié)點(diǎn)的顏色為紅色
entry.color = RED;
if (cmp < 0)
parent.left = entry;
else
parent.right = entry;
// 將它重新修正為一顆二叉查找樹
fixAfterInsertion(entry);
return null;
}
/*
* 對(duì)紅黑樹的節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)
* 左旋示意圖(對(duì)節(jié)點(diǎn)x進(jìn)行左旋)
* px px
* / /
* x y
* / \ --(左旋)-- / \
* lx y x ry
* / \ / \
* ly ry lx ly
*/
private void leftRotate(Entry<K, V> x) {
// 設(shè)置x的右孩子為y
Entry<K, V> y = x.right;
// 將 “y的左孩子” 設(shè)為 “x的右孩子”；
// 如果y的左孩子非空，將 “x” 設(shè)為 “y的左孩子的父親”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 將 “x的父親” 設(shè)為 “y的父親”
y.parent = x.parent;
if (x.parent == null) {
this.root = y; // 如果 “x的父親” 是空節(jié)點(diǎn)帚豪，則將y設(shè)為根節(jié)點(diǎn)
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父節(jié)點(diǎn)的左孩子碳竟，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”
else
x.parent.right = y; // 如果 x是它父節(jié)點(diǎn)的左孩子，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”
}
// 將 “x” 設(shè)為 “y的左孩子”
y.left = x;
// 將 “x的父節(jié)點(diǎn)” 設(shè)為 “y”
x.parent = y;
}
/*
* 對(duì)紅黑樹的節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)
* 右旋示意圖(對(duì)節(jié)點(diǎn)y進(jìn)行左旋)：
* py py
* / /
* y x
* / \ / \
* x ry lx y
* / \ / \
* lx rx rx ry
*/
private void rightRotate(Entry<K, V> y) {
// 設(shè)置x是當(dāng)前節(jié)點(diǎn)的左孩子狸臣。
Entry<K, V> x = y.left;
// 將 “x的右孩子” 設(shè)為 “y的左孩子”莹桅；
// 如果"x的右孩子"不為空的話，將 “y” 設(shè)為 “x的右孩子的父親”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 將 “y的父親” 設(shè)為 “x的父親”
x.parent = y.parent;
if (y.parent == null) {
this.root = x; // 如果 “y的父親” 是空節(jié)點(diǎn)烛亦，則將x設(shè)為根節(jié)點(diǎn)
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父節(jié)點(diǎn)的右孩子诈泼，則將x設(shè)為“y的父節(jié)點(diǎn)的右孩子”
else
y.parent.left = x; // (y是它父節(jié)點(diǎn)的左孩子) 將x設(shè)為“x的父節(jié)點(diǎn)的左孩子”
}
// 將 “y” 設(shè)為 “x的右孩子”
x.right = y;
// 將 “y的父節(jié)點(diǎn)” 設(shè)為 “x”
y.parent = x;
}
/**
* 紅黑樹插入修正函數(shù)
*
* 在向紅黑樹中插入節(jié)點(diǎn)之后(失去平衡)，再調(diào)用該函數(shù)煤禽；
* 目的是將它重新塑造成一顆紅黑樹铐达。
* @param entry 新插入的結(jié)點(diǎn)
*/
private void fixAfterInsertion(Entry<K, V> entry) {
Entry<K, V> parent,gparent;
// 若父節(jié)點(diǎn)存在，并且父節(jié)點(diǎn)的顏色是red
while( (parent = parentOf(entry))!= null && isRed(parent)) {
gparent = parentOf(parent); // 祖父節(jié)點(diǎn)
// 父節(jié)點(diǎn)是 祖父節(jié)點(diǎn)的左子樹
if(gparent.left == parent) {
Entry<K, V> uncle = gparent.right; // 叔節(jié)點(diǎn)
// 叔節(jié)點(diǎn) 存在且是紅色
if( (uncle!=null) && colorOf(uncle) == RED) {
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
entry = gparent;
continue;
}
// 叔叔是黑色檬果，且當(dāng)前節(jié)點(diǎn)是右孩子
if(parent.right == entry) {
Entry<K, V> tmp;
leftRotate(parent);
tmp = parent;
parent = entry;
entry = tmp;
}
// 叔叔是黑色瓮孙，且當(dāng)前節(jié)點(diǎn)是左孩子
parent.color = BLACK;
gparent.color = RED;
rightRotate(gparent);
} else {
// 父節(jié)點(diǎn)是 祖父節(jié)點(diǎn)的右子樹
Entry<K, V> uncle = gparent.left; // 叔節(jié)點(diǎn)
// 叔節(jié)點(diǎn) 存在且是紅色
if( (uncle!=null) && colorOf(uncle) == RED) {
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
entry = gparent;
continue;
}
// 叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子
if(parent.left == entry) {
Entry<K, V> tmp;
rightRotate(parent);
tmp = parent;
parent = entry;
entry = tmp;
}
// 叔叔是黑色选脊，且當(dāng)前節(jié)點(diǎn)是右孩子
parent.color = BLACK;
gparent.color = RED;
leftRotate(gparent);
}
}
// 將根節(jié)點(diǎn)設(shè)為黑色
root.color = BLACK;
}
測(cè)試添加：
public class Main {
public static void main(String[] args) {
RBTree<Integer, String> tree = new RBTree<Integer, String>();
int[] ins = new int[]{20,5,32,3,10,45,8,16,6};
for (int i : ins) {
tree.put(i, ""+ i);
}
tree.printZhong();
tree.printXian();
}
}
結(jié)果：
中序遍歷：[[3 : 3]+(false), [5 : 5]+(true), [6 : 6]+(true), [8 : 8]+(false), [10 : 10]+(false), [16 : 16]+(false), [20 : 20]+(true), [32 : 32]+(false), [45 : 45]+(true)]
先序遍歷：[[10 : 10]+(false), [5 : 5]+(true), [3 : 3]+(false), [8 : 8]+(false), [6 : 6]+(true), [20 : 20]+(true), [16 : 16]+(false), [32 : 32]+(false), [45 : 45]+(true)]
其中：false為黑杭抠；true為紅
紅黑樹.png
紅黑樹刪除操作：
刪除的節(jié)點(diǎn)的兩種情況：
1）刪除點(diǎn)p的左右子樹都為空，或者只有一棵子樹非空。
2）刪除點(diǎn)p的左右子樹都非空。
對(duì)于上述情況1饺汹，處理起來(lái)比較簡(jiǎn)單借尿，直接將node刪除（左右子樹都為空時(shí)），或者用非空子樹替代node（只有一棵子樹非空時(shí)）；對(duì)于情況2，可以用node的后繼s（樹中大于node的最小的那個(gè)元素）代替node，然后使用情況1刪除s（此時(shí)s一定滿足情況1）沮峡。
刪除原理示意圖：
TreeMap_fixAfterDeletion.png
刪除節(jié)點(diǎn)程序：
/**
* 刪除節(jié)點(diǎn)
*/
public void remove(K key) {
Entry<K, V> node;
if ((node = search(root, key)) != null)
remove(node);
}
private void remove(Entry<K, V> node) {
Entry<K, V> child, parent;
boolean color;
// 刪除的node不為空
if (node.left != null && node.right != null) {// 2. 刪除點(diǎn)p的左右子樹都非空。
Entry<K,V> s = successor(node);// 得到后繼
node.key = s.key;
node.value = s.value;
node = s; // 為了刪除后繼節(jié)點(diǎn)亿柑，不用遞歸邢疙，這么賦值的；
}
Entry<K,V> replacement = (node.left != null ? node.left : node.right);
if (replacement != null) { // 刪除點(diǎn)node只有一棵子樹非空望薄；
Entry<K, V> parentNode = parentOf(node);
if(parentNode == null) {
this.root = replacement;
}
if(parentNode.left == node) {
parentNode.left = replacement;
} else {
parentNode.right = replacement;
}
replacement.parent = parentNode;
node.left = node.right = node.parent = null; // 置為null疟游；
if (node.color == BLACK)
fixAfterDeletion(replacement);// 調(diào)整
} else if (node.parent == null) { // node沒有子節(jié)點(diǎn)，并且沒有父節(jié)點(diǎn)
this.root = null;
} else {
if (node.color == BLACK)
fixAfterDeletion(node);// 調(diào)整
if (node.parent != null) {
if (node == node.parent.left)
node.parent.left = null;
else if (node == node.parent.right)
node.parent.right = null;
node.parent = null;
}
}
}
/**
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除節(jié)點(diǎn)之后(紅黑樹失去平衡)痕支，再調(diào)用該函數(shù)颁虐；
* 目的是將它重新塑造成一顆紅黑樹。
* @param node 待修正的節(jié)點(diǎn)
*/
private void fixAfterDeletion(Entry<K,V> node) {
while (node != root && colorOf(node) == BLACK) {
// node為其父節(jié)點(diǎn)的左子樹
if (node == leftOf(parentOf(node))) {
Entry<K,V> bro = rightOf(parentOf(node));
// node的兄弟節(jié)點(diǎn)為紅
if (colorOf(bro) == RED) {
setColor(bro, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
bro = rightOf(parentOf(node));
}
// node的兄弟節(jié)點(diǎn)的兩個(gè)子樹為黑
if (colorOf(leftOf(bro)) == BLACK && colorOf(rightOf(bro)) == BLACK) {
setColor(bro, RED);
node = parentOf(node);
} else {
// node的兄弟節(jié)點(diǎn)的左子樹為紅卧须，右子樹為黑
if (colorOf(rightOf(bro)) == BLACK) {
setColor(leftOf(bro), BLACK);
setColor(bro, RED);
rightRotate(bro);
bro = rightOf(parentOf(node));
}
// node的兄弟節(jié)點(diǎn)的右子樹為紅另绩，左子樹隨意
setColor(bro, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(bro), BLACK);
leftRotate(parentOf(node));
node = root;
}
} else {
Entry<K,V> sib = leftOf(parentOf(node));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
sib = leftOf(parentOf(node));
}
if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
node = parentOf(node);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
leftRotate(sib);
sib = leftOf(parentOf(node));
}
setColor(sib, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(sib), BLACK);
rightRotate(parentOf(node));
node = root;
}
}
}
setColor(node, BLACK);
}
/**
* 尋找p的后繼（樹中大于p的key的最小的那個(gè)元素）
* @param p
* @return
*/
private Entry<K, V> successor( Entry<K, V> p) {
if(p == null) {
return null;
}
Entry<K, V> node = p.right;
if(node != null) {
while(node.left != null) {
node = node.left;
}
return node;
}
// 因?yàn)樵O(shè)定p左右子樹不為空儒陨，所以不會(huì)走到這一步
return null;
}
