1、什么是紅黑樹？
在上一章的學習，我們知道了2-3-4樹，其實2-3-4樹和紅黑樹之前是可以相互轉換的，紅黑樹是一種自平衡的二叉搜索樹，是二叉搜索樹的拓展，紅黑樹只有兩種節點，一種是紅色的，一種是黑色的，
紅黑樹不像AVL樹那樣嚴格，而是近似平衡，
所以一棵紅黑樹至少包含如下資訊：
- left：左子節點
- right：右子節點
- data：資料存盤在紅黑樹節點中
- color：節點顏色，紅色或者黑色
static class RBNode<K extends Comparable<K> , V> {
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K k;
private V v;
public RBNode( K key, V value,RBNode parent) {
this.parent = parent;
this.k = key;
this.v = value;
}
}
2、紅黑樹的特征
紅黑樹有如下特征，其目的是為了保證平衡
- 1、紅黑樹的根節點總是黑色的
- 2、樹的節點總是紅色或者黑色
- 3、每個葉子都是黑色的，如果一個節點不包含左右子節點，我們則將其子節點視為黑色的
- 4、如果一個節點是紅色的，則其兩個子節點都是黑色的
- 5、從根節點到葉子節點的每條路徑都有相同數量的黑色節點
3、紅黑樹旋轉操作
紅黑樹能自平衡，它靠的是什么？三種操作：左旋、右旋和變色
| 操作 | 描述 |
|---|---|
| 左旋 | 以某個節點作為旋轉結點，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變， |
| 右旋 | 以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變， |
| 變色 | 結點的顏色由紅變黑或由黑變紅， |
3.1、左旋操作
左旋：以某個節點作為旋轉點，其右子節點變為旋轉節點的父節點，右子節點的左子節點變為旋轉節點的右子節點，左子節點保持不變，
網上很多地方都有這種gif圖片，原文不知道來自哪里，暫且借來做說明：
java實作紅黑樹左旋邏輯：
左旋演算法分步進行：
- 1、將pr節點的左子節點更新為p的右子節點，pr有左子節點時，將p賦給pr左子節點rl的父節點
- 2、 p有父節點r時，將p的父節點賦給pr的父節點，同時更新r的左子節點或者右子節點為pr
- 3、將pr的左子節點設為p，將p的父節點設為pr
/**
* 左旋示意圖：圍繞p進行左旋
* r r
* / /
* p pr
* / \ / \
* pl pr => p rr
* / \ / \
* rl rr pl rl
* 左旋演算法分步進行：
* 1. 將pr節點的左子節點更新為p的右子節點，pr有左子節點時，將p賦給pr左子節點rl的父節點
* 2. p有父節點r時，將p的父節點賦給pr的父節點，同時更新r的左子節點或者右子節點為pr
* 3. 將pr的左子節點設為p，將p的父節點設為pr
* @param
*/
private void leftRotate(RBNode p) {
if(p != null) {
// 1. 將pr節點的左子節點更新為p的右子節點，pr有左子節點時，將p賦給pr左子節點rl的父節點
// 獲取pr節點，也即為p的右節點
RBNode pr = p.right;
// 將pr節點的左子節點更新為p的右子節點
p.right = pr.left;
//pr有左子節點時，將p賦給pr左子節點rl的父節點
if (pr.left != null) {
pr.left.parent = p;
}
// 2. p有父節點r時，將p的父節點賦給pr的父節點，同時更新r的左子節點或者右子節點為pr
// 不管p是否存在父節點，我們都設定p的父節點也為 pr的父節點
pr.parent = p.parent;
if (p.parent == null) {
// 直接設定root節點為pr
this.root = pr;
} else {
// 有r根節點的情況
if (p == p.parent.left) {
// 原來的p節點為r的左節點的情況
p.parent.left = pr;
} else {
// 原來的p節點為r的右節點的情況
p.parent.right = pr;
}
}
// 3. 將pr的左子節點設為p，將p的父節點設為pr
pr.left = p;
p.parent = pr;
}
}
3.2、右旋操作
右旋：以某個節點作為旋轉點，其左子節點變為旋轉節點的父節點，左子節點的右子節點變為旋轉節點的左子節點，右子節點保持不變
右旋演算法分步進行：
- 1、 將pl節點的右子節點更新為p的左子節點，pl有右子節點時，將p賦給pl右子節點rr的父節點
- 2、p有父節點r時，將p的父節點賦給pl的父節點，同時更新r的左子節點或者右子節點為pl
- 3、將pl的右子節點設為p，將p的父節點設為pl
java實作紅黑樹右旋：
/**
* 右旋示意圖：圍繞p進行右旋
* r r
* / /
* p pl
* / \ / \
* pl pr => rl p
* / \ / \
* rl rr rr pr
* 右旋演算法分步進行：
* 1. 將pl節點的右子節點更新為p的左子節點，pl有右子節點時，將p賦給pl右子節點rr的父節點
* 2. p有父節點r時，將p的父節點賦給pl的父節點，同時更新r的左子節點或者右子節點為pl
* 3. 將pl的右子節點設為p，將p的父節點設為pl
* @param
*/
public void rightRotate(RBNode p) {
if(p != null) {
// 1. 將pl節點的右子節點更新為p的左子節點，pl有右子節點時，將p賦給pl右子節點rr的父節點
// 獲取pl節點，也即為p的左節點
RBNode pl = p.left;
// 將pl節點的右子節點更新為p的左子節點
p.left = pl.right;
//pl有右子節點時，將p賦給pl右子節點rl的父節點
if (pl.right != null) {
pl.right.parent = p;
}
// 2. p有父節點r時，將p的父節點賦給pl的父節點，同時更新r的左子節點或者右子節點為pl
pl.parent = p.parent;
if (p.parent == null) {
// 直接設定root節點為pr
this.root = pl;
} else {
// 有r根節點的情況
if (p == p.parent.right) {
// 原來的p節點為r的右節點的情況
p.parent.right = pl;
} else {
// 原來的p節點為r的左節點的情況
p.parent.right = pl;
}
}
// 3. 將pl的右子節點設為p，將p的父節點設為pl
pl.right = p;
p.parent = pl;
}
}
4、紅黑樹新增節點
紅黑樹是一棵二叉搜索樹，所以新增邏輯也可以類似的，如下代碼，這個邏輯就是和二叉搜索樹的新增節點是一樣的，就是一個節點一個節點做比較大小，然后找到一個節點作為新節點的父節點，然后再判斷是要做左子節點，還是右子節點就可以
/**
* 新增紅黑樹節點操作 . <br>
* @Date 2021/08/12 16:31
* @Param [key, value]
* @return void
*/
public void put(K key, V value) {
RBNode<K,V> parent = null ;
RBNode<K,V> t = root;
// 找不到root節點，將新節點作為root節點
if (t == null) {
root = new RBNode<>(key, value, parent);
return;
}
// 找到節點作為新增節點的父節點
while (t != null) {
parent = t;
int cmp = key.compareTo(t.k);
if (cmp < 0) {
t = t.left;
} else {
t = t.right;
}
}
// 創建新節點，判斷新節點是作為parent節點的左節點還是右節點
RBNode<K,V> node = new RBNode<K, V>(key , value , parent);
int comp = node.k.compareTo(parent.k);
if (comp < 0) {
parent.left = node;
} else {
parent.right = node;
}
// 關鍵，新增節點之后，紅黑樹的調整
fixAfterInsertion(node);
}
紅黑樹的新增，前面邏輯是和二叉搜索樹一樣的，不同的是新增節點后，為了保證平衡，需要做旋轉和變色操作，具體邏輯看一下fixAfterInsertion(node);，這個邏輯比較關鍵，這里做一下比較詳細的描述，這里分情況分析
-
場景1： 紅黑樹是Empty的，這是最簡單的場景，直接將新節點作為根節點就行，不過紅黑樹有個特性，根節點都是黑色的，所以將新節點涂黑就行
-
場景2：新增節點的父節點是黑節點，由于新增的節點都是紅色的節點，所以這種情況不會影響平衡，直接新增就行
-
場景3：新增結點的父結點為紅結點且為祖父節點的左子節點
-
場景3.1：新節點的叔叔節點是紅色的
這種情況，如圖005是新增節點，其叔叔節點是009是紅色的，這種情況，需要做下變色，祖父節點008變為紅色，父親節點006變為黑色，叔叔節點009也變為黑色，這樣整棵紅黑色就可以平衡
-
場景3.2：叔叔節點是黑色，且新增節點作為右子節點
這種情況要做的是將新節點008指向父節點003，同時做左旋
-
場景3.3：叔叔節點是黑色，且新增節點作為左子節點
這種情況，需要將父節點008變黑色，祖父節點011變為紅色，同時圍繞祖父節點011做右旋
-
-
場景4：新增結點的父結點為紅結點，且為祖父節點的右子節點
這種場景也有3種情況，不過和場景3是相反的，這種不做詳細描述
/**
* 新增節點之后，紅黑樹的調整操作 <br>
* @Date 2021/08/12 17:36
* @Param [node]
* @return void
*/
private void fixAfterInsertion( RBNode<K,V> node) {
node.color = RED;
// 父節點是紅色的，才需要調整，黑色節點直接新增就行
while (node != null && node != root && node.parent.color == RED) {
// 父節點是祖父節點的左節點
if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
// 找到叔叔節點
RBNode<K,V> y = rightOf(parentOf(parentOf(node)));
// case1 : 叔叔節點也是紅色
if (y != null && colorOf(y) == RED) {
setColor(parentOf(node) , BLACK);
setColor(y , BLACK);
setColor(parentOf(parentOf(node)) , RED);
node = parentOf(parentOf(node));
}
else {
// case2 ： 叔叔節點是黑色，且新增節點是右子節點
if (node == rightOf(parentOf(node))) {
// 將父節點和新增節點調換
node = parentOf(node);
// 從父節點處做左旋
leftRotate(node);
}
// case 3 : 叔叔節點是黑色，且新增節點是左子節點
setColor(parentOf(node) , BLACK);
setColor(parentOf(parentOf(node)) , RED);
rightRotate(parentOf(parentOf(node)));
}
}
else {
// 找到叔叔節點
RBNode<K,V> y = leftOf(parentOf(parentOf(node)));
// case1 : 叔叔節點也是紅色
if (y != null && colorOf(y) == RED) {
setColor(parentOf(node) , BLACK);
setColor(y , BLACK);
setColor(parentOf(parentOf(node)) , RED);
node = parentOf(parentOf(node));
}
else {
// case2 ： 叔叔節點是黑色，且新增節點是左子節點
if (node == leftOf(parentOf(node))) {
node = parentOf(node);
rightRotate(node);
}
// case 3 : 叔叔節點是黑色，且新增節點是右子節點
setColor(parentOf(node) , BLACK);
setColor(parentOf(parentOf(node)) , RED);
leftRotate(parentOf(parentOf(node)));
}
}
}
// root節點肯定是黑色
root.color = BLACK;
}
測驗代碼：
使用在線網站進行驗證：
5、紅黑樹移除節點
前期準備，找到對應節點：
/**
* 根據key移除節點 <br>
* @Date 2021/08/13 10:28
* @Param [key]
* @return V
*/
public V remove(K key){
// 1. 根據需要洗掉的key 找到對應的Node節點
RBNode node = getNode(key);
if(node == null){
// 不存在
return null;
}
V oldValue = (V) node.v;
// 具體洗掉節點的方法
deleteEntry(node);
return oldValue;
}
/**
* 根據key找到對應node <br>
* @Date 2021/08/13 10:29
* @Param [key]
* @return com.example.datastructure.rbtree.RBTree.RBNode
*/
private RBNode getNode(K key) {
RBNode node = this.root;
while(node != null){
int cmp = key.compareTo((K) node.k);
if(cmp < 0){
node = node.left;
}else if(cmp > 0){
node = node.right;
}else{
// 表示找到了對應的節點
return node;
}
}
return null;
}
紅黑色的洗掉操作和二叉樹前半部分是一樣的，
有三種情況：
- 1：洗掉葉子節點，直接洗掉
- 2：洗掉有一個子節點的情況，找到替換節點
- 3：如果洗掉的節點右兩個子節點，此時需要找到前驅節點或者后繼節點
/**
* 洗掉節點操作. <br>
* 有三種情況：
* 1：洗掉葉子節點，直接洗掉
* 2：洗掉有一個子節點的情況，找到替換節點
* 3：如果洗掉的節點右兩個子節點，此時需要找到前驅節點或者后繼節點
* @Date 2021/08/12 17:35
* @Param [node]
* @return void
*/
public void deleteEntry(RBNode<K,V> node) {
// 3、node節點有兩個子節點的情況，找到前驅節點，復制前驅節點的元素給node節點，同時改變指標
if (node.left != null && node.right != null) {
RBNode<K,V> s = predecessor(node);
node.k = s.k;
node.v = s.v;
node = s;
}
// 2、洗掉有一個子節點的情況找到替換節點
RBNode<K,V> replacement = node.left != null? node.left : node.right;
if (replacement != null) {
// 改變指標
replacement.parent = node.parent;
if (node.parent == null ){
// node是root節點
root = replacement;
}
else if (node == node.parent.left){
// 替換為左節點
node.parent.left = replacement;
}
else {
// 替換為右節點
node.parent.right = replacement;
}
// 指標都指向null，等待GC
node.left = node.right = node.parent = null;
// 紅黑樹平衡
if (node.color == BLACK) {
fixAfterDeletion(replacement);
}
}
else if (node.parent == null) {
// 說明要洗掉的是root節點
root = null;
}
else {
// 1、node節點是葉子節點
// 先調整
if (node.color == BLACK) {
fixAfterDeletion(node);
}
// 再洗掉
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;
}
}
}
查找后繼節點，后繼節點就是先定位到右節點，然后一直往左查找，找到最小值
/**
* 查找后繼節點，后繼節點就是先定位到右節點，然后一直往左查找，找到最小值<br>
* @Author mazq
* @Date 2021/08/12 17:17
* @Param [node]
* @return com.example.datastructure.rbtree.RBTree.RBNode<K,V>
*/
private RBNode<K , V> successor(RBNode<K , V> node) {
if (node == null) {
return null;
} else if (node.right != null) {
// 取到右節點
RBNode<K , V> p = node.right;
// 往左查找，找到最小值
while(p.left != null) {
p = p.left;
}
return p;
} else {
// 比較少見的情況，該節點沒有右子節點，往上遍歷
RBNode<K ,V> p = node.parent;
RBNode<K , V> ch = node;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
前驅節點，定位到左節點，一直找右找，找到最大值
/**
* 查找前驅節點 <br>
* @Author mazq
* @Date 2021/08/12 17:17
* @Param [node]
* @return com.example.datastructure.rbtree.RBTree.RBNode<K,V>
*/
private RBNode<K , V> predecessor(RBNode<K , V> node) {
if (node == null) {
return null;
} else if (node.left != null) {
// 找到左節點
RBNode<K , V> p = node.left;
// 往右查找，找到最大值
while(p.right != null) {
p = p.right;
}
return p;
} else {
// 比較少見的情況，該節點沒有左子節點，往上遍歷
RBNode<K ,V> p = node.parent;
RBNode<K , V> ch = node;
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
前面的邏輯是和二叉搜索樹一樣的，不同的是洗掉節點之后，紅黑色還要做調整，保證紅黑樹的平衡
這里是一個比較復雜的程序，同樣分情況進行分析：如果node節點是紅色節點，直接涂黑就可以，下面分析node節點是黑色節點且不為root節點的情況，先看一下node節點是左子節點情況，右子節點的情況類似，是相反的，就不詳細描述
- 場景1：node的兄弟節點是紅色的
移除節點是006，這種情況兄弟節點是009，紅色的節點，要保持紅黑樹的平衡，父節點007變為紅色，兄弟節點009變為黑色，然后做左旋
- 場景2：node的兄弟節點是黑色的，且兩個子節點也都是黑色的
這種情況就比較復雜了，需要往上遞回調整 - 場景3：node的兄弟節點是黑色的，且左子節點是紅色，右子節點是黑色
- 場景4：node的兄弟節點是黑色的，且右子節點是紅色，左子節點任意顏色
/**
* 洗掉節點之后，紅黑樹的調整操作 <br>
* @Date 2021/08/12 17:36
* @Param [node]
* @return void
*/
private void fixAfterDeletion (RBNode<K,V> node) {
while (node != root && colorOf(node) == BLACK) {
// 是左子節點的情況
if (node == leftOf(parentOf(node))) {
// 找到兄弟節點
RBNode<K,V> sib = rightOf(parentOf(node));
// case1: node的兄弟節點是紅色的
if (colorOf(sib) == RED) {
setColor(sib , BLACK);
setColor(parentOf(node) , RED);
leftRotate(parentOf(node));
// 找到真正的兄弟節點
sib = rightOf(parentOf(node));
}
// case2: node的兄弟節點是黑色的，且兩個子節點也都是黑色的
if (colorOf(leftOf(node)) == BLACK && colorOf(rightOf(node)) == BLACK) {
// 情況比較復雜
setColor(sib , RED);
// 往上遞回
node = parentOf(node);
}
else {
//case3: node的兄弟節點是黑色的，且左子節點是紅色，右子節點是黑色
if (colorOf(rightOf(sib)) == BLACK) {
// 這種情況需要變色，同時右旋
setColor(sib , RED);
setColor(leftOf(sib) , BLACK);
rightRotate(sib);
// 重新調整兄弟節點
sib = rightOf(parentOf(node));
}
//case4: node的兄弟節點是黑色的，且右子節點是紅色，左子節點任意顏色
setColor(sib , colorOf(parentOf(node)));
setColor(parentOf(node) , BLACK);
setColor(rightOf(sib) , BLACK);
leftRotate(parentOf(node));
// 跳出回圈
node = root;
}
}
else { // 與上面邏輯對稱
// 找到兄弟節點
RBNode<K,V> sib = leftOf(parentOf(node));
// Case 1: node的兄弟是紅色的
if (colorOf(sib) == RED) {
setColor(sib , BLACK);
setColor(parentOf(node) , RED);
rightRotate(parentOf(node));
// 找到真正的兄弟節點
sib = leftOf(parentOf(node));
}
// Case 2: node的兄弟是黑色，且的倆個子節點都是黑色的
if (colorOf(rightOf(node)) == BLACK && colorOf(leftOf(node)) == BLACK) {
// 情況比較復雜
setColor(sib , RED);
// 往上遞回
node = parentOf(node);
}
else {
// Case 3: node的兄弟是黑色的，并且左子節點是紅色，右子節點為黑色
if (colorOf(leftOf(sib)) == BLACK) {
setColor(sib , RED);
setColor(rightOf(sib) , BLACK);
leftRotate(sib);
// 重新調整叔叔節點的位置
sib = leftOf(parentOf(node));
}
// Case 4: node的兄弟是黑色的；并且左子節點是紅色的，右子節點任意顏色
setColor(sib , colorOf(parentOf(node)));
setColor(parentOf(node) , BLACK);
setColor(leftOf(sib) , BLACK);
rightRotate(parentOf(node));
// 跳出回圈
node = root;
}
}
}
// 替代節點是紅色節點，直接涂黑
setColor(node , BLACK);
}
6、Java實作紅黑樹
前面已經比較詳細的分析了紅黑樹的旋轉和新增洗掉節點操作，下面給出自己內部測驗過的代碼，java實作紅黑樹，當然不能保證沒有一些bug
package com.example.datastructure.rbtree;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.io.Serializable;
@Data
public class RBTree<K extends Comparable<K> , V> implements Serializable {
private final static boolean RED = false;
private final static boolean BLACK = true;
private RBNode root;
@Data
@AllArgsConstructor
@NoArgsConstructor
static class RBNode<K extends Comparable<K> , V> {
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K k;
private V v;
public RBNode( K key, V value,RBNode parent) {
this.parent = parent;
this.k = key;
this.v = value;
}
}
/**
* 左旋示意圖：圍繞p進行左旋
* r r
* / /
* p pr
* / \ / \
* pl pr => p rr
* / \ / \
* rl rr pl rl
* 左旋演算法分步進行：
* 1. 將pr節點的左子節點更新為p的右子節點，pr有左子節點時，將p賦給pr左子節點rl的父節點
* 2. p有父節點r時，將p的父節點賦給pr的父節點，同時更新r的左子節點或者右子節點為pr
* 3. 將pr的左子節點設為p，將p的父節點設為pr
* @param
*/
public void leftRotate(RBNode p) {
if(p != null) {
// 1. 將pr節點的左子節點更新為p的右子節點，pr有左子節點時，將p賦給pr左子節點rl的父節點
// 獲取pr節點，也即為p的右節點
RBNode pr = p.right;
// 將pr節點的左子節點更新為p的右子節點
p.right = pr.left;
//pr有左子節點時，將p賦給pr左子節點rl的父節點
if (pr.left != null) {
pr.left.parent = p;
}
// 2. p有父節點r時，將p的父節點賦給pr的父節點，同時更新r的左子節點或者右子節點為pr
// 不管p是否存在父節點，我們都設定p的父節點也為 pr的父節點
pr.parent = p.parent;
if (p.parent == null) {
// 直接設定root節點為pr
this.root = pr;
} else {
// 有r根節點的情況
if (p == p.parent.left) {
// 原來的p節點為r的左節點的情況
p.parent.left = pr;
} else {
// 原來的p節點為r的右節點的情況
p.parent.right = pr;
}
}
// 3. 將pr的左子節點設為p，將p的父節點設為pr
pr.left = p;
p.parent = pr;
}
}
/**
* 右旋示意圖：圍繞p進行右旋
* r r
* / /
* p pl
* / \ / \
* pl pr => rl p
* / \ / \
* rl rr rr pr
* 右旋演算法分步進行：
* 1. 將pl節點的右子節點更新為p的左子節點，pl有右子節點時，將p賦給pl右子節點rr的父節點
* 2. p有父節點r時，將p的父節點賦給pl的父節點，同時更新r的左子節點或者右子節點為pl
* 3. 將pl的右子節點設為p，將p的父節點設為pl
* @param
*/
public void rightRotate(RBNode p) {
if(p != null) {
// 1. 將pl節點的右子節點更新為p的左子節點，pl有右子節點時，將p賦給pl右子節點rr的父節點
// 獲取pl節點，也即為p的左節點
RBNode pl = p.left;
// 將pl節點的右子節點更新為p的左子節點
p.left = pl.right;
//pl有右子節點時，將p賦給pl右子節點rl的父節點
if (pl.right != null) {
pl.right.parent = p;
}
// 2. p有父節點r時，將p的父節點賦給pl的父節點，同時更新r的左子節點或者右子節點為pl
pl.parent = p.parent;
if (p.parent == null) {
// 直接設定root節點為pr
this.root = pl;
} else {
// 有r根節點的情況
if (p == p.parent.right) {
// 原來的p節點為r的右節點的情況
p.parent.right = pl;
} else {
// 原來的p節點為r的左節點的情況
p.parent.right = pl;
}
}
// 3. 將pl的右子節點設為p，將p的父節點設為pl
pl.right = p;
p.parent = pl;
}
}
/**
* 新增紅黑樹節點操作 . <br>
* @Date 2021/08/12 16:31
* @Param [key, value]
* @return void
*/
public void put(K key, V value) {
RBNode<K,V> parent = null ;
RBNode<K,V> t = root;
// 找不到root節點，將新節點作為root節點
if (t == null) {
root = new RBNode<>(key, value, parent);
return;
}
// 找到節點作為新增節點的父節點
while (t != null) {
parent = t;
int cmp = key.compareTo(t.k);
if (cmp < 0) {
t = t.left;
} else {
t = t.right;
}
}
// 創建新節點，判斷新節點是作為parent節點的左節點還是右節點
RBNode<K,V> node = new RBNode<K, V>(key , value , parent);
int comp = node.k.compareTo(parent.k);
if (comp < 0) {
parent.left = node;
} else {
parent.right = node;
}
// 關鍵，新增節點之后，紅黑樹的調整
fixAfterInsertion(node);
}
/**
* 新增節點之后，紅黑樹的調整操作 <br>
* @Date 2021/08/12 17:36
* @Param [node]
* @return void
*/
private void fixAfterInsertion( RBNode<K,V> node) {
node.color = RED;
// 父節點是紅色的，才需要調整，黑色節點直接新增就行
while (node != null && node != root && node.parent.color == RED) {
// 父節點是祖父節點的左節點
if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
// 找到叔叔節點
RBNode<K,V> y = rightOf(parentOf(parentOf(node)));
// case1 : 叔叔節點也是紅色
if (y != null && colorOf(y) == RED) {
setColor(parentOf(node) , BLACK);
setColor(y , BLACK);
setColor(parentOf(parentOf(node)) , RED);
node = parentOf(parentOf(node));
}
else {
// case2 ： 叔叔節點是黑色，且新增節點是右子節點
if (node == rightOf(parentOf(node))) {
// 將父節點和新增節點調換
node = parentOf(node);
// 從父節點處做左旋
leftRotate(node);
}
// case 3 : 叔叔節點是黑色，且新增節點是左子節點
setColor(parentOf(node) , BLACK);
setColor(parentOf(parentOf(node)) , RED);
rightRotate(parentOf(parentOf(node)));
}
}
else {
// 找到叔叔節點
RBNode<K,V> y = leftOf(parentOf(parentOf(node)));
// case1 : 叔叔節點也是紅色
if (y != null && colorOf(y) == RED) {
setColor(parentOf(node) , BLACK);
setColor(y , BLACK);
setColor(parentOf(parentOf(node)) , RED);
node = parentOf(parentOf(node));
}
else {
// case2 ： 叔叔節點是黑色，且新增節點是左子節點
if (node == leftOf(parentOf(node))) {
node = parentOf(node);
rightRotate(node);
}
// case 3 : 叔叔節點是黑色，且新增節點是右子節點
setColor(parentOf(node) , BLACK);
setColor(parentOf(parentOf(node)) , RED);
leftRotate(parentOf(parentOf(node)));
}
}
}
// root節點肯定是黑色
root.color = BLACK;
}
/**
* 根據key移除節點 <br>
* @Date 2021/08/13 10:28
* @Param [key]
* @return V
*/
public V remove(K key){
// 1. 根據需要洗掉的key 找到對應的Node節點
RBNode node = getNode(key);
if(node == null){
// 不存在
return null;
}
V oldValue = (V) node.v;
// 具體洗掉節點的方法
deleteEntry(node);
return oldValue;
}
/**
* 根據key找到對應node <br>
* @Date 2021/08/13 10:29
* @Param [key]
* @return com.example.datastructure.rbtree.RBTree.RBNode
*/
private RBNode getNode(K key) {
RBNode node = this.root;
while(node != null){
int cmp = key.compareTo((K) node.k);
if(cmp < 0){
node = node.left;
}else if(cmp > 0){
node = node.right;
}else{
// 表示找到了對應的節點
return node;
}
}
return null;
}
/**
* 洗掉節點操作. <br>
* 有三種情況：
* 1：洗掉葉子節點，直接洗掉
* 2：洗掉有一個子節點的情況，找到替換節點
* 3：如果洗掉的節點右兩個子節點，此時需要找到前驅節點或者后繼節點
* @Date 2021/08/12 17:35
* @Param [node]
* @return void
*/
public void deleteEntry(RBNode<K,V> node) {
// 3、node節點有兩個子節點的情況，找到前驅節點，復制前驅節點的元素給node節點，同時改變指標
if (node.left != null && node.right != null) {
RBNode<K,V> s = predecessor(node);
node.k = s.k;
node.v = s.v;
node = s;
}
// 2、洗掉有一個子節點的情況找到替換節點
RBNode<K,V> replacement = node.left != null? node.left : node.right;
if (replacement != null) {
// 改變指標
replacement.parent = node.parent;
if (node.parent == null ){
// node是root節點
root = replacement;
}
else if (node == node.parent.left){
// 替換為左節點
node.parent.left = replacement;
}
else {
// 替換為右節點
node.parent.right = replacement;
}
// 指標都指向null，等待GC
node.left = node.right = node.parent = null;
// 紅黑樹平衡
if (node.color == BLACK) {
fixAfterDeletion(replacement);
}
}
else if (node.parent == null) {
// 說明要洗掉的是root節點
root = null;
}
else {
// 1、node節點是葉子節點
// 先調整
if (node.color == BLACK) {
fixAfterDeletion(node);
}
// 再洗掉
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;
}
}
}
/**
* 洗掉節點之后，紅黑樹的調整操作 <br>
* @Date 2021/08/12 17:36
* @Param [node]
* @return void
*/
private void fixAfterDeletion (RBNode<K,V> node) {
while (node != root && colorOf(node) == BLACK) {
// 是左子節點的情況
if (node == leftOf(parentOf(node))) {
// 找到兄弟節點
RBNode<K,V> sib = rightOf(parentOf(node));
// case1: node的兄弟節點是紅色的
if (colorOf(sib) == RED) {
setColor(sib , BLACK);
setColor(parentOf(node) , RED);
leftRotate(parentOf(node));
// 找到真正的兄弟節點
sib = rightOf(parentOf(node));
}
// case2: node的兄弟節點是黑色的，且兩個子節點也都是黑色的
if (colorOf(leftOf(node)) == BLACK && colorOf(rightOf(node)) == BLACK) {
// 情況比較復雜
setColor(sib , RED);
// 往上遞回
node = parentOf(node);
}
else {
//case3: node的兄弟節點是黑色的，且左子節點是紅色，右子節點是黑色
if (colorOf(rightOf(sib)) == BLACK) {
// 這種情況需要變色，同時右旋
setColor(sib , RED);
setColor(leftOf(sib) , BLACK);
rightRotate(sib);
// 重新調整兄弟節點
sib = rightOf(parentOf(node));
}
//case4: node的兄弟節點是黑色的，且右子節點是紅色，左子節點任意顏色
setColor(sib , colorOf(parentOf(node)));
setColor(parentOf(node) , BLACK);
setColor(rightOf(sib) , BLACK);
leftRotate(parentOf(node));
// 跳出回圈
node = root;
}
}
else { // 與上面邏輯對稱
// 找到兄弟節點
RBNode<K,V> sib = leftOf(parentOf(node));
// Case 1: node的兄弟是紅色的
if (colorOf(sib) == RED) {
setColor(sib , BLACK);
setColor(parentOf(node) , RED);
rightRotate(parentOf(node));
// 找到真正的兄弟節點
sib = leftOf(parentOf(node));
}
// Case 2: node的兄弟是黑色，且的倆個子節點都是黑色的
if (colorOf(rightOf(node)) == BLACK && colorOf(leftOf(node)) == BLACK) {
// 情況比較復雜
setColor(sib , RED);
// 往上遞回
node = parentOf(node);
}
else {
// Case 3: node的兄弟是黑色的，并且左子節點是紅色，右子節點為黑色
if (colorOf(leftOf(sib)) == BLACK) {
setColor(sib , RED);
setColor(rightOf(sib) , BLACK);
leftRotate(sib);
// 重新調整叔叔節點的位置
sib = leftOf(parentOf(node));
}
// Case 4: node的兄弟是黑色的；并且左子節點是紅色的，右子節點任意顏色
setColor(sib , colorOf(parentOf(node)));
setColor(parentOf(node) , BLACK);
setColor(leftOf(sib) , BLACK);
rightRotate(parentOf(node));
// 跳出回圈
node = root;
}
}
}
// 替代節點是紅色節點，直接然后
setColor(node , BLACK);
}
/**
* 查找后繼節點<br>
* @Author mazq
* @Date 2021/08/12 17:17
* @Param [node]
* @return com.example.datastructure.rbtree.RBTree.RBNode<K,V>
*/
private RBNode<K , V> successor(RBNode<K , V> node) {
if (node == null) {
return null;
} else if (node.right != null) {
// 取到右節點
RBNode<K , V> p = node.right;
// 往左查找，找到最小值
while(p.left != null) {
p = p.left;
}
return p;
} else {
// 比較少見的情況，該節點沒有右子節點，往上遍歷
RBNode<K ,V> p = node.parent;
RBNode<K , V> ch = node;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* 查找前驅節點 <br>
* @Author mazq
* @Date 2021/08/12 17:17
* @Param [node]
* @return com.example.datastructure.rbtree.RBTree.RBNode<K,V>
*/
private RBNode<K , V> predecessor(RBNode<K , V> node) {
if (node == null) {
return null;
} else if (node.left != null) {
// 找到左節點
RBNode<K , V> p = node.left;
// 往右查找，找到最大值
while(p.right != null) {
p = p.right;
}
return p;
} else {
// 比較少見的情況，該節點沒有左子節點，往上遍歷
RBNode<K ,V> p = node.parent;
RBNode<K , V> ch = node;
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
private boolean colorOf(RBNode<K , V> node) {
return node == null ? BLACK : node.color;
}
private RBNode<K , V> parentOf(RBNode<K , V> node) {
return node != null ? node.parent : null;
}
private RBNode<K , V> leftOf(RBNode<K , V> node) {
return node != null ? node.left : null;
}
private RBNode<K , V> rightOf(RBNode<K , V> node) {
return node != null ? node.right : null;
}
private void setColor(RBNode<K , V> node , boolean color) {
if (node != null) {
node.color = color;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/294985.html
標籤：其他