什么是紅黑樹(shù)？
紅黑樹(shù)的定義
- 每個(gè)節(jié)點(diǎn)或者是紅色的，或者是黑色的。
- 根節(jié)點(diǎn)是黑色的。
- 每一個(gè)葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）是黑色的。
- 如果一個(gè)節(jié)點(diǎn)是紅色的，那么他的孩子節(jié)點(diǎn)都是黑色的。
- 從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過(guò)的黑色節(jié)點(diǎn)是一樣的。
直接看到這些定義是非常難以理解的，紅黑樹(shù)為什么這樣定義？
在算法4這本書(shū)中對(duì)于紅黑樹(shù)的介紹直接繞過(guò)了紅黑樹(shù)的基本性質(zhì)，而是首先探索了另外一種平衡樹(shù)，這種平衡樹(shù)就是2-3樹(shù)，事實(shí)上紅黑樹(shù)與2-3樹(shù)是等價(jià)的，如果理解的紅黑樹(shù)與2-3樹(shù)之間的等價(jià)關(guān)系，其實(shí)紅黑樹(shù)并不難！
什么是2-3樹(shù)？
在講解紅黑樹(shù)之前，首先學(xué)習(xí)2-3樹(shù)，通過(guò)2-3樹(shù)來(lái)理解紅黑樹(shù)。
2-3樹(shù)滿足二分搜索樹(shù)的基本性質(zhì)，但其節(jié)點(diǎn)可以存放一個(gè)元素或二個(gè)元素，每個(gè)節(jié)點(diǎn)有兩個(gè)或者三個(gè)孩子，所以稱(chēng)為2-3樹(shù)。通常存放一個(gè)元素有兩個(gè)孩子的節(jié)點(diǎn)稱(chēng)為兩節(jié)點(diǎn)，一個(gè)元素有三個(gè)孩子的節(jié)點(diǎn)稱(chēng)為三節(jié)點(diǎn)。
如圖：
==注意：2-3樹(shù)是一顆絕對(duì)平衡的樹(shù)。==
查找元素
2-3樹(shù)的查找類(lèi)似二分搜索樹(shù)的查找，根據(jù)元素的大小來(lái)決定查找的方向是左孩子還是右孩子。要判斷一個(gè)元素是否存在，首先將待查詢的元素與根節(jié)點(diǎn)進(jìn)行比較，如果待查找的元素和其中任意一個(gè)元素相等，那就查找到了，否則根據(jù)比較的結(jié)果來(lái)選擇查找的方向。
如圖：
插入元素
==對(duì)于2-3樹(shù)來(lái)說(shuō)，添加節(jié)點(diǎn)永遠(yuǎn)不會(huì)添加到空的位置上==。那么添加到哪呢？
如圖：
例如添加一個(gè)節(jié)點(diǎn)37，依然按照二分搜索樹(shù)的性質(zhì)來(lái)看待，由于37小于42，應(yīng)該放于42的左子樹(shù)中，由于42的左子樹(shù)為空，那么此時(shí)新節(jié)點(diǎn)將會(huì)融合到添加的過(guò)程中所找到的最后一個(gè)葉子節(jié)點(diǎn)。
如圖：
由于42本來(lái)是個(gè)2節(jié)點(diǎn)，但是融合后，變成了一個(gè)3節(jié)點(diǎn)，并且依然是平衡的。
此時(shí)再添加一個(gè)節(jié)點(diǎn)12，由于12小于37，應(yīng)該放于37的左子樹(shù)中，由于37的左子樹(shù)為空，那么此時(shí)新節(jié)點(diǎn)將會(huì)融合到添加過(guò)程中所找到的最后一個(gè)葉子節(jié)點(diǎn)。
如圖：
雖然再添加過(guò)程中的最后一個(gè)葉子節(jié)點(diǎn)是一個(gè)3節(jié)點(diǎn)，但是依然進(jìn)行融合，暫時(shí)形成一個(gè)4節(jié)點(diǎn)。但是對(duì)于2-3樹(shù)來(lái)說(shuō)，它并沒(méi)有4節(jié)點(diǎn)，只有2節(jié)點(diǎn)或3節(jié)點(diǎn)。對(duì)于4節(jié)點(diǎn)可以直接分裂成子樹(shù)。
如圖：
上圖中，由4節(jié)點(diǎn)分裂成了由三個(gè)2節(jié)點(diǎn)組成一顆平衡的樹(shù)。
此時(shí)再添加一個(gè)節(jié)點(diǎn)18，由于18小于37，進(jìn)入37的左子樹(shù)中繼續(xù)比較，此時(shí)18大于12，應(yīng)該放于12的右子樹(shù)中，由于12的右子樹(shù)為空，那么此時(shí)新節(jié)點(diǎn)將會(huì)融合到添加過(guò)程中所找到的最后一個(gè)葉子節(jié)點(diǎn)。
如圖：
此時(shí)再添加一個(gè)節(jié)點(diǎn)6，由于6小于37，進(jìn)入37的左子樹(shù)中繼續(xù)比較，此時(shí)6小于12，應(yīng)該放于12的左子樹(shù)當(dāng)中，但是12的左子樹(shù)為空，那么此時(shí)新節(jié)點(diǎn)將會(huì)融合到添加過(guò)程中所找到的最后一個(gè)葉子節(jié)點(diǎn)。
如圖：
由于2-3中沒(méi)有4節(jié)點(diǎn)，對(duì)于節(jié)點(diǎn)可以直接分裂成子樹(shù)。
如圖：
注意，上圖中由于4節(jié)點(diǎn)分裂成3個(gè)2節(jié)點(diǎn)的子樹(shù)，造成整個(gè)樹(shù)并不是一顆絕對(duì)平衡的樹(shù)。對(duì)于2-3樹(shù)來(lái)說(shuō)，如果一個(gè)葉子節(jié)點(diǎn)本來(lái)是一個(gè)3節(jié)點(diǎn)了，添加了新節(jié)點(diǎn)變成了4節(jié)點(diǎn)的話，對(duì)于這個(gè)4節(jié)點(diǎn)，分裂為三個(gè)2節(jié)點(diǎn)，并且有一個(gè)根節(jié)點(diǎn)，對(duì)于根節(jié)點(diǎn)需要跟父親節(jié)點(diǎn)進(jìn)行融合，對(duì)于根節(jié)點(diǎn)和父親節(jié)點(diǎn)融合分為兩種情況：
-
父節(jié)點(diǎn)是一個(gè)2節(jié)點(diǎn)
如圖：
2-3樹(shù)—插入元素8.png -
父節(jié)點(diǎn)是一個(gè)3節(jié)點(diǎn)
如圖：
2-3樹(shù)—插入元素9.png2-3樹(shù)—插入元素10.png2-3樹(shù)—插入元素11.png
紅黑樹(shù)與2-3樹(shù)的等價(jià)性
2-3樹(shù)中的3節(jié)點(diǎn)的元素是并列關(guān)系，但兩個(gè)黑色的節(jié)點(diǎn)無(wú)法表示出并列的關(guān)系。那么如何在紅黑樹(shù)中標(biāo)識(shí)出并列的關(guān)系呢？
如圖：
如上圖中，可以將b節(jié)點(diǎn)設(shè)置為紅色，表示b、c節(jié)點(diǎn)在2-3樹(shù)中是并且的關(guān)系。也就是說(shuō)，一個(gè)紅色節(jié)點(diǎn)和它的父親節(jié)點(diǎn)在2-3樹(shù)中是一個(gè)3節(jié)點(diǎn)。
紅黑樹(shù)的實(shí)現(xiàn)
注意：在這里實(shí)現(xiàn)的紅黑樹(shù)以紅色節(jié)點(diǎn)向左傾斜為基礎(chǔ)的。
插入節(jié)點(diǎn)
在2-3樹(shù)中插入一個(gè)節(jié)點(diǎn)，始終都是與葉子節(jié)點(diǎn)進(jìn)行融合，那么在紅黑樹(shù)中紅色節(jié)點(diǎn)代表著與父親節(jié)點(diǎn)
并列的關(guān)系，所以在紅黑樹(shù)中添加一個(gè)節(jié)點(diǎn)始終都是紅色的。
上圖中，添加第一個(gè)節(jié)點(diǎn)42，由于添加一個(gè)節(jié)點(diǎn)始終是紅色的，所以要把根節(jié)點(diǎn)變?yōu)楹谏?/p>
此時(shí)，再添加一個(gè)節(jié)點(diǎn)37，根據(jù)二分搜索樹(shù)的性質(zhì)，由于37<42，所以將節(jié)點(diǎn)37添加到根節(jié)點(diǎn)的左孩子。
-
情況1
注意，如果新節(jié)點(diǎn)大于根節(jié)點(diǎn)，就會(huì)將新節(jié)點(diǎn)插入到根節(jié)點(diǎn)的右孩子位置，那么此時(shí)就不符合紅色節(jié)點(diǎn)向左傾斜的定義了，如何解決？對(duì)根節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)操作，并且根據(jù)紅色節(jié)點(diǎn)向左傾斜的定義，還需把37節(jié)點(diǎn)置位紅色，42節(jié)點(diǎn)置位黑色。注：這里對(duì)應(yīng)在2-3樹(shù)中相當(dāng)于把一個(gè)新的元素放于2節(jié)點(diǎn)中融合為3節(jié)點(diǎn)的操作。
紅黑樹(shù)—插入節(jié)點(diǎn)3.png -
情況2
此時(shí)再插入一個(gè)節(jié)點(diǎn)66，根據(jù)二分搜索樹(shù)的性質(zhì)，由于66大于42，放于42的右孩子中。
紅黑樹(shù)—插入節(jié)點(diǎn)4.png上圖中，在2-3樹(shù)中對(duì)應(yīng)一個(gè)臨時(shí)的4節(jié)點(diǎn)，在2-3樹(shù)對(duì)臨時(shí)的4節(jié)點(diǎn)所處理的方式是什么？
處理的方式是拆分成三個(gè)2節(jié)點(diǎn)所組成的一棵子樹(shù)。
那么在紅黑樹(shù)中三個(gè)2節(jié)點(diǎn)代表著什么意思？其實(shí)就是代表這三個(gè)節(jié)點(diǎn)都是黑色的節(jié)點(diǎn)，每一個(gè)黑色的節(jié)點(diǎn)，如果它的左側(cè)沒(méi)有紅色節(jié)點(diǎn)，它本身就代表一個(gè)單獨(dú)的二節(jié)點(diǎn)，所以在這種情況下，節(jié)點(diǎn)根本不需要選擇操作，只需要改變顏色即可，讓節(jié)點(diǎn)42的左右孩子分別改為黑色。
紅黑樹(shù)—插入節(jié)點(diǎn)5.png注：這個(gè)樣子相當(dāng)于2-3樹(shù)中由臨時(shí)4節(jié)點(diǎn)所組成三個(gè)2節(jié)點(diǎn)的子樹(shù)。
注意，在2-3樹(shù)中由臨時(shí)4節(jié)點(diǎn)所組成的三個(gè)2節(jié)點(diǎn)的子樹(shù)，有可能會(huì)造成整顆樹(shù)不是絕對(duì)平衡的，所以拆分的子樹(shù)的根節(jié)點(diǎn)會(huì)繼續(xù)向父親節(jié)點(diǎn)融合。這意味著，新的根節(jié)點(diǎn)在紅黑樹(shù)中變?yōu)榧t色節(jié)點(diǎn)。
紅黑樹(shù)—插入節(jié)點(diǎn)6.png注：原來(lái)的42節(jié)點(diǎn)為黑色，37節(jié)點(diǎn)和66節(jié)點(diǎn)為紅色，經(jīng)過(guò)一系列操作之后，其實(shí)所有節(jié)點(diǎn)的顏色正好相反過(guò)來(lái)了，這個(gè)過(guò)程稱(chēng)為顏色翻轉(zhuǎn)。
-
情況3
紅黑樹(shù)—插入節(jié)點(diǎn)7.png如上圖，添加節(jié)點(diǎn)12，根據(jù)二分搜索樹(shù)的性質(zhì)，添加到節(jié)點(diǎn)37的左孩子中。這樣的形狀也等同于2-3樹(shù)中的臨時(shí)4節(jié)點(diǎn)。
紅黑樹(shù)—插入節(jié)點(diǎn)8.png在2-3樹(shù)中需要把臨時(shí)4節(jié)點(diǎn)拆分成三個(gè)2節(jié)點(diǎn)，那么在紅黑樹(shù)中如何解決呢？
對(duì)這顆子樹(shù)的根節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)操作，旋轉(zhuǎn)后再對(duì)新的根節(jié)點(diǎn)變?yōu)樵瓉?lái)根節(jié)點(diǎn)的顏色。
紅黑樹(shù)—插入節(jié)點(diǎn)9.png通過(guò)這樣的處理之后，其實(shí)本質(zhì)上12、37、42這些節(jié)點(diǎn)還是應(yīng)該是一個(gè)臨時(shí)的4節(jié)點(diǎn)，所以最后再把原來(lái)的根節(jié)點(diǎn)變?yōu)榧t色節(jié)點(diǎn)，這樣就表示節(jié)點(diǎn)42與父親節(jié)點(diǎn)37是融合在一起的。
紅黑樹(shù)—插入節(jié)點(diǎn)10.png這樣就完成了整個(gè)右旋轉(zhuǎn)的過(guò)程。在這個(gè)過(guò)程中，根節(jié)點(diǎn)變?yōu)楣?jié)點(diǎn)37，并且臨時(shí)4節(jié)點(diǎn)的樣子變?yōu)楦?jié)點(diǎn)的左右孩子都為紅色節(jié)點(diǎn)，這種情況就是顏色翻轉(zhuǎn)，處理這種情況，把它變成對(duì)應(yīng)2-3樹(shù)中由三個(gè)2節(jié)點(diǎn)組成的子樹(shù)的方法，就是再運(yùn)行一下顏色翻轉(zhuǎn)的過(guò)程。
整體代碼
/**
* 描述：紅黑樹(shù)。
* <p>
* Create By ZhangBiao
* 2020/5/18
*/
public class RedBlackTree<K extends Comparable<K>, V> {
private Node root;
private int size;
private static final boolean RED = true;
private static final boolean BLACK = false;
public RedBlackTree() {
this.root = null;
this.size = 0;
}
/**
* 判斷節(jié)點(diǎn)node的顏色
*
* @param node
* @return
*/
private boolean isRed(Node node) {
if (node == null) {
return BLACK;
}
return node.color;
}
// node x
// / \ 左旋轉(zhuǎn) / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node) {
Node x = node.right;
//左旋轉(zhuǎn)的過(guò)程
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// node x
// / \ 右旋轉(zhuǎn) / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node) {
Node x = node.left;
//右旋轉(zhuǎn)過(guò)程
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
/**
* 顏色翻轉(zhuǎn)
*
* @param node
*/
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
/**
* 向紅黑樹(shù)中添加新的元素
*
* @param key
* @param value
*/
@Override
public void add(K key, V value) {
root = add(root, key, value);
//最終根節(jié)點(diǎn)為黑色節(jié)點(diǎn)
root.color = BLACK;
}
/**
* 向以node為根節(jié)點(diǎn)的紅黑樹(shù)中插入元素(key, value)（遞歸算法）并返回插入新節(jié)點(diǎn)后紅黑樹(shù)的根節(jié)點(diǎn)
*
* @param node
* @param key
* @param value
* @return
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
//默認(rèn)插入紅色節(jié)點(diǎn)
return new Node(key, value);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else {
node.value = value;
}
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
@Override
public V remove(K key) {
throw new IllegalArgumentException("No remove in RedBlackTree!");
}
@Override
public boolean contains(K key) {
return getNode(root, key) != null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " not exist!");
}
node.value = newValue;
}
@Override
public int getSize() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
/**
* 返回以node為根節(jié)點(diǎn)的二分搜索樹(shù)中key所在的節(jié)點(diǎn)
*
* @param node
* @param key
* @return
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.equals(node.key)) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else {
return getNode(node.right, key);
}
}
private class Node {
public K key;
public V value;
public Node left;
public Node right;
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.color = RED;
}
}
}
