目錄
- 整體結構思維導圖
- 什麼是2-3樹
- 2-3樹插入元素
- 2-3樹與紅黑樹關系
- 紅黑樹性質
- 紅黑樹添加元素
- 完整源碼
整體結構思維導圖
-------------------------------------------------------------------------------- 回到目錄
什麼是2-3樹
2-3樹：滿足二分搜尋樹的基本性質，節點可存放一個元素或兩個元素，是一棵絕對平衡的樹（任意子樹左右高度差為0）。
2-3樹插入元素
一個原則: 添加節點将永遠不會添加到一個空的位置(這和二叉搜尋樹不同)，隻會和最後找到的葉子節點做融合。
添加方法：
0、從根節點開始尋找到要插入的父親節點。
1、若節點小于父親節點，就融合到左邊，大的就融合到右邊。
2、若融合完後父親節點變成4節點（父親節點有3個元素，4個孩子），就把父親節點從中間元素分裂，否則完成目前節點的添加。
3、若分裂完後的父親節點的父親節點不是4節點，就重複1、2步驟。
分裂圖示：
初級圖示：
中級圖示：
進階圖示：
-------------------------------------------------------------------------------- 回到目錄
2-3樹與紅黑樹關系
2-3樹與紅黑樹是等價的，紅黑樹隻不過是在2-3樹的基礎上做一些人為規則的約定：
以下實作的紅黑樹是左傾紅黑樹。
關于顔色：
2節點都是黑色，3節點中小的元素紅色，大的元素黑色：（即紅色節點永遠左傾）
完整圖示：
上圖直覺的圖示：
-------------------------------------------------------------------------------- 回到目錄
紅黑樹性質
1-4點可對照上上圖的圖示了解，重點是第5點。
第5點: 其最主要的原因是2-3樹是絕對平衡的，其次是每個3節點都有一個黑色節點，是以不管怎麼走經過的黑色節點的數量是一樣多的。
是以紅黑樹是保持"黑平衡"的二叉樹，本質就是2-3樹是絕對平衡的。
紅黑樹嚴格意義上并不是平衡二叉樹，因為平衡因子有可能大于1，但因為“黑平衡”的存在，是以也可看成是平衡二叉樹。
紅黑樹添加元素
首先，新插入的節點永遠是紅色的。 空節點是黑色的。
添加步驟：
0、從根節點開始尋找到要插入的父親節點，若是插入第一個節點，則插入後變成黑色。
1.1、若父親節點沒有左孩子，則：
若節點小于父親節點，則插入到左孩子，保持紅色不變；
（插入後左黑，右黑）（保持不變）
若節點大于父親節點，則插入到右孩子後進行左旋轉，對孩子節點和父親節點進行變顔色，紅色變黑色，黑色變紅色。
（插入後左黑，右紅）（左旋轉）
1.2、若父親節點有左孩子，則：
1.2.1 若節點小于父親節點的左孩子，則插入到父親節點的左孩子的左孩子，（a）然後進行右旋轉，把父親節點和父親節點的左孩子進行變顔色，再把3個節點進行顔色翻轉。
（插入後左紅，左左紅）（右旋轉）（顔色翻轉）
1.2.2 若節點大于父親節點的左孩子，則插入到父親節點的左孩子的右孩子，然後進行左旋轉，再進行（a）步驟。
（插入後父親節點的左孩子左黑，右紅）（左旋轉）（右旋轉）（顔色翻轉）
1.2.3 若節點大于父親節點，則插入到右孩子，然後3個節點進行顔色翻轉。
（插入後左紅，右紅，自己黑）（顔色翻轉）
-------------------------------------------------------------------------------- 回到目錄
可以看下面添加元素的代碼加深添加過程的了解。
添加元素的代碼：
/** 向紅黑樹中添加新的元素(key, value) */
public void add(K key, V value) {//相當于JDK的put操作
root = add(root, key, value);
root.color = BLACK; /**子過程一: 保持最終根節點為黑色 --> 第二條性質 */
}
// 向以node為根的紅黑樹樹中插入元素(key, value)，遞歸算法,傳回插入新節點後紅黑樹樹的根
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
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 // key.compareTo(node.key) == 0
node.value = value;
/**注意三個if不是互斥的*/
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;
}
/**左旋轉
node x
/ \ --> / \
T1 x node T3
/ \ / \
T2 T3 T1 T2
*/
private Node leftRotate(Node node){
Node x = node.right;
Node T2 = x.left;
x.left = node;
node.right = T2;
//update color
x.color = node.color;
node.color = RED;
return x;
}
/**右旋轉
node x
/ \ / \
x T1 --> y node
/ \ / \ / \
y T2 T4 T3 T2 T1
/ \
T4 T3
*/
private Node rightRotate(Node node){
Node x = node.left;
Node T2 = x.right;
x.right = node;
node.left = T2;
//update color
x.color = node.color;
node.color = RED;
return x;
}
注意：顔色翻轉雖然也是變顔色，但它特指3個節點同時變顔色。
//三個節點的顔色反轉 根->RED 兩個孩子->BLACK
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
-------------------------------------------------------------------------------- 回到目錄
完整源碼
public class RBTree<K extends Comparable<K>, V> {
private final static boolean RED = true;
private final static boolean BLACK = false;
private class Node {
public K key;
public V value;
public Node left, right;
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
// 一開始添加的時候都是紅結點
color = RED; //為什麼一開始是紅色,因為在2-3結點中添加一個結點，永遠是和葉子結點進行融合，是以是3節點，是以設定成紅色
}
}
private Node root;
private int size;
public RBTree() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/** 判斷節點node的顔色 */
private boolean isRed(Node node){
if(node == null) return BLACK;
return node.color;
}
/**左旋轉
node x
/ \ --> / \
T1 x node T3
/ \ / \
T2 T3 T1 T2
*/
private Node leftRotate(Node node){
Node x = node.right;
Node T2 = x.left;
x.left = node;
node.right = T2;
//update color
x.color = node.color;
node.color = RED;
return x;
}
/**右旋轉
node x
/ \ / \
x T1 --> y node
/ \ / \ / \
y T2 T4 T3 T2 T1
/ \
T4 T3
*/
private Node rightRotate(Node node){
Node x = node.left;
Node T2 = x.right;
x.right = node;
node.left = T2;
//update color
x.color = node.color;
node.color = RED;
return x;
}
/**三個節點的顔色反轉 根->RED 兩個孩子->BLACK */
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
/** 向紅黑樹中添加新的元素(key, value) */
public void add(K key, V value) {//相當于JDK的put操作
root = add(root, key, value);
root.color = BLACK; /**子過程一: 保持最終根節點為黑色 --> 第二條性質 */
}
// 向以node為根的紅黑樹樹中插入元素(key, value)，遞歸算法,傳回插入新節點後紅黑樹樹的根
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
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 // key.compareTo(node.key) == 0
node.value = value;
/**維護鍊: 注意三個if不是互斥的 就是一個維護鍊的關系 */
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;
}
// 傳回以node為根節點的紅黑樹中，key所在的節點
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 // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
public boolean contains(K key) {
return getNode(root, key) != null;
}
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 傳回以node為根的紅黑樹的最小值所在的節點
private Node minimum(Node node) {
if (node.left == null)
return node;
return minimum(node.left);
}
// 删除掉以node為根的紅黑樹中的最小節點,傳回删除節點後新的紅黑樹的根
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
//沒有實作remove中的調整
public V remove(K key) {
throw new UnsupportedOperationException("No remove in RBTree!");
}
}
-------------------------------------------------------------------------------- 回到目錄
紅黑樹的更多相關
java.util 中的 TreeMap 和 TreeSet 是基于紅黑樹的。
紅黑樹的性能：
若對資料經常要發生删除或添加的話，用紅黑樹是最好的選擇；
若資料建立出來不變動隻查詢的話，用AVL樹會更好一點