用Java實現紅黑樹
- 2021 年 9 月 15 日
- 筆記
- About Algorithm
紅黑樹是眾多「平衡的」搜索樹模式中的一種，在最壞情況下，它相關操作的時間複雜度為O(log n)。
1、紅黑樹的屬性
紅黑樹是一種二分查找樹，與普通的二分查找樹不同的一點是，紅黑樹的每個節點都有一個顏色（color）屬性。該屬性的值要麼是紅色，要麼是黑色。
通過限制從根到葉子的任何簡單路徑上的節點顏色，紅黑樹確保沒有比任何其他路徑長兩倍的路徑，從而使樹近似平衡。
假設紅黑樹節點的屬性有鍵（key）、顏色（color）、左子節點（left）、右子節點（right），父節點（parent）。
一棵紅黑樹必須滿足下面有下面這些特性（紅黑樹特性）：
- 樹中的每個節點要麼是紅色，要麼是黑色；
- 根節點是黑色；
- 每個葉子節點（null）是黑色；
- 如果某節點是紅色的，它的兩個子節點都是黑色；
- 對於每個節點到後面任一葉子節點（null）的所有路徑，都有相同數量的黑色節點。
為了在紅黑樹程式碼中處理邊界條件方便，我們用一個哨兵變數代替null。對於一個紅黑樹tree，哨兵變數RedBlackTree.NULL（下文程式碼中）是一個和其它節點有同樣屬性的節點，它的顏色（color）屬性是黑色，其它屬性可以任意取值。
我們使用哨兵變數是因為我們可以把一個節點node的子節點null當成一個普通節點。
在這裡，我們使用哨兵變數RedBlackTree.NULL代替樹中所有的null（所有的葉子節點及根節點的父節點）。
我們把從一個節點n（不包括）到任一葉子節點路徑上的黑色節點的個數稱為黑色高度，用bh(n)表示。一棵紅黑樹的黑色高度是其根節點的黑色高度。
關於紅黑樹的搜索，求最小值，求最大值，求前驅，求後繼這些操作的程式碼與二分查找樹的這些操作的程式碼基本一致。可以在用java實現二分查找樹查看。
結合上文給出下面的程式碼。
用一個枚舉類Color表示顏色：
public enum Color {
Black("黑色"), Red("紅色");
private String color;
private Color(String color) {
this.color = color;
}
@Override
public String toString() {
return color;
}
}
類Node表示節點：
public class Node {
public int key;
public Color color;
public Node left;
public Node right;
public Node parent;
public Node() {
}
public Node(Color color) {
this.color = color;
}
public Node(int key) {
this.key = key;
this.color = Color.Red;
}
public int height() {
return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
}
public Node minimum() {
Node pointer = this;
while (pointer.left != RedBlackTree.NULL)
pointer = pointer.left;
return pointer;
}
@Override
public String toString() {
String position = "null";
if (this.parent != RedBlackTree.NULL)
position = this.parent.left == this ? "left" : "right";
return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
}
}
類RedTreeNode表示紅黑樹：
public class RedBlackTree {
// 表示哨兵變數
public final static Node NULL = new Node(Color.Black);
public Node root;
public RedBlackTree() {
this.root = NULL;
}
}
2、旋轉
紅黑樹的插入和刪除操作，能改變紅黑樹的結構，可能會使它不再有前面所說的某些特性性。為了維持這些特性，我們需要改變樹中某些節點的顏色和位置。
我們可以通過旋轉改變節點的結構。主要有左旋轉和右旋轉兩種方式。具體如下圖所示。
左旋轉：把一個節點n的右子節點right變為它的父節點，n變為right的左子節點，所以right不能為null。這時n的右指針空了出來，right的左子樹被n擠掉，所以right原來的左子樹稱為n的右子樹。
右旋轉：把一個節點n的左子節點left變為它的父節點，n變為left的右子節點，所以left不能為null。這時n的左指針被空了出來，left的右子樹被n擠掉，所以left原來的右子樹被稱為n的左子樹。
可在RedTreeNode類中，加上如下實現程式碼：
public void leftRotate(Node node) {
Node rightNode = node.right;
node.right = rightNode.left;
if (rightNode.left != RedBlackTree.NULL)
rightNode.left.parent = node;
rightNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL)
this.root = rightNode;
else if (node.parent.left == node)
node.parent.left = rightNode;
else
node.parent.right = rightNode;
rightNode.left = node;
node.parent = rightNode;
}
public void rightRotate(Node node) {
Node leftNode = node.left;
node.left = leftNode.right;
if (leftNode.right != RedBlackTree.NULL)
leftNode.right.parent = node;
leftNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL) {
this.root = leftNode;
} else if (node.parent.left == node) {
node.parent.left = leftNode;
} else {
node.parent.right = leftNode;
}
leftNode.right = node;
node.parent = leftNode;
}
3、插入
紅黑樹的插入程式碼與二分查找樹的插入程式碼非常相似。只不過紅黑樹的插入操作會改變紅黑樹的結構，使其不在有該有的特性。
在這裡，新插入的節點默認是紅色。
所以在插入節點之後，要有維護紅黑樹特性的程式碼。
public void insert(Node node) {
Node parentPointer = RedBlackTree.NULL;
Node pointer = this.root;
while (this.root != RedBlackTree.NULL) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
}
node.parent = parentPointer;
if(parentPointer == RedBlackTree.NULL) {
this.root = node;
}else if(node.key < parentPointer.key) {
parentPointer.left = node;
}else {
parentPointer.right = node;
}
node.left = RedBlackTree.NULL;
node.right = RedBlackTree.NULL;
node.color = Color.Red;
// 維護紅黑樹屬性的方法
this.insertFixUp(node);
}
用上述方法插入一個新節點的時候，有兩類情況會違反紅黑樹的特性。
- 當樹中沒有節點時，此時插入的節點稱為根節點，而此節點的顏色為紅色。
- 當新插入的節點成為一個紅色節點的子節點時，此時存在一個紅色結點有紅色子節點的情況。
對於第一類情況，可以直接把根結點設置為黑色；而針對第二類情況，需要根據具體條件，做出相應的解決方案。
具體程式碼如下：
public void insertFixUp(Node node) {
// 當node不是根結點，且node的父節點顏色為紅色
while (node.parent.color == Color.Red) {
// 先判斷node的父節點是左子節點，還是右子節點，這不同的情況，解決方案也會不同
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // 如果叔叔節點是紅色，則父父一定是黑色
// 通過把父父節點變成紅色，父節點和兄弟節點變成黑色，然後在判斷父父節點的顏色是否合適
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.right) {
node = node.parent;
this.leftRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.rightRotate(node.parent.parent);
}
} else {
Node uncleNode = node.parent.parent.left;
if (uncleNode.color == Color.Red) {
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.left) {
node = node.parent;
this.rightRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.leftRotate(node.parent.parent);
}
}
}
// 如果之前樹中沒有節點，那麼新加入的點就成了新結點，而新插入的結點都是紅色的，所以需要修改。
this.root.color = Color.Black;
}
下面的圖分別對應第二類情況中的六種及相應處理結果。
情況1：
情況2：
情況3：
情況4：
情況5：
情況6：
4、刪除
紅黑樹中節點的刪除會使一個結點代替另外一個節點。所以先要實現這樣的程式碼：
public void transplant(Node n1, Node n2) {
if(n1.parent == RedBlackTree.NULL){
this.root = n2;
}else if(n1.parent.left == n1) {
n1.parent.left = n2;
}else {
n1.parent.right = n2;
}
n2.parent = n1.parent;
}
紅黑樹的刪除節點程式碼是基於二分查找樹的刪除節點程式碼而寫的。
刪除結點程式碼：
public void delete(Node node) {
Node pointer1 = node;
// 用於記錄被刪除的顏色，如果是紅色，可以不用管，但如果是黑色，可能會破壞紅黑樹的屬性
Color pointerOriginColor = pointer1.color;
// 用於記錄問題的出現點
Node pointer2;
if (node.left == RedBlackTree.NULL) {
pointer2 = node.right;
this.transplant(node, node.right);
} else if (node.right == RedBlackTree.NULL) {
pointer2 = node.left;
this.transplant(node, node.left);
} else {
// 如要刪除的位元組有兩個子節點，則找到其直接後繼（右子樹最小值），直接後繼節點沒有非空左子節點。
pointer1 = node.right.minimum();
// 記錄直接後繼的顏色和其右子節點
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// 如果其直接後繼是node的右子節點，不用進行處理
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// 否則，先把直接後繼從樹中提取出來，用來替換node
this.transplant(pointer1, pointer1.right);
pointer1.right = node.right;
pointer1.right.parent = pointer1;
}
// 用node的直接後繼替換node，繼承node的顏色
this.transplant(node, pointer1);
pointer1.left = node.left;
pointer1.left.parent = pointer1;
pointer1.color = node.color;
}
if (pointerOriginColor == Color.Black) {
this.deleteFixUp(pointer2);
}
}
當被刪除節點的顏色是黑色時需要調用方法維護紅黑樹的特性。
主要有兩類情況：
- 當node是紅色時，直接變成黑色即可。
- 當node是黑色時，需要調整紅黑樹結構。，
private void deleteFixUp(Node node) {
// 如果node不是根節點，且是黑色
while (node != this.root && node.color == Color.Black) {
// 如果node是其父節點的左子節點
if (node == node.parent.left) {
// 記錄node的兄弟節點
Node pointer1 = node.parent.right;
// 如果他兄弟節點是紅色
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
leftRotate(node.parent);
pointer1 = node.parent.right;
}
if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.right.color == Color.Black) {
pointer1.left.color = Color.Black;
pointer1.color = Color.Red;
rightRotate(pointer1);
pointer1 = node.parent.right;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.right.color = Color.Black;
leftRotate(node.parent);
node = this.root;
}
} else {
// 記錄node的兄弟節點
Node pointer1 = node.parent.left;
// 如果他兄弟節點是紅色
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
rightRotate(node.parent);
pointer1 = node.parent.left;
}
if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.left.color == Color.Black) {
pointer1.right.color = Color.Black;
pointer1.color = Color.Red;
leftRotate(pointer1);
pointer1 = node.parent.left;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.left.color = Color.Black;
rightRotate(node.parent);
node = this.root;
}
}
}
node.color = Color.Black;
}
對第二類情況，有下面8種：
情況1：
情況2：
情況3：
情況4：
情況5：
情況6：
情況7：
情況8：
5、所有程式碼
public enum Color {
Black("黑色"), Red("紅色");
private String color;
private Color(String color) {
this.color = color;
}
@Override
public String toString() {
return color;
}
}
public class Node {
public int key;
public Color color;
public Node left;
public Node right;
public Node parent;
public Node() {
}
public Node(Color color) {
this.color = color;
}
public Node(int key) {
this.key = key;
this.color = Color.Red;
}
/**
* 求在樹中節點的高度
*
* @return
*/
public int height() {
return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
}
/**
* 在以該節點為根節點的樹中，求最小節點
*
* @return
*/
public Node minimum() {
Node pointer = this;
while (pointer.left != RedBlackTree.NULL)
pointer = pointer.left;
return pointer;
}
@Override
public String toString() {
String position = "null";
if (this.parent != RedBlackTree.NULL)
position = this.parent.left == this ? "left" : "right";
return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
}
}
import java.util.LinkedList;
import java.util.Queue;
public class RedBlackTree {
public final static Node NULL = new Node(Color.Black);
public Node root;
public RedBlackTree() {
this.root = NULL;
}
/**
* 左旋轉
*
* @param node
*/
public void leftRotate(Node node) {
Node rightNode = node.right;
node.right = rightNode.left;
if (rightNode.left != RedBlackTree.NULL)
rightNode.left.parent = node;
rightNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL)
this.root = rightNode;
else if (node.parent.left == node)
node.parent.left = rightNode;
else
node.parent.right = rightNode;
rightNode.left = node;
node.parent = rightNode;
}
/**
* 右旋轉
*
* @param node
*/
public void rightRotate(Node node) {
Node leftNode = node.left;
node.left = leftNode.right;
if (leftNode.right != RedBlackTree.NULL)
leftNode.right.parent = node;
leftNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL) {
this.root = leftNode;
} else if (node.parent.left == node) {
node.parent.left = leftNode;
} else {
node.parent.right = leftNode;
}
leftNode.right = node;
node.parent = leftNode;
}
public void insert(Node node) {
Node parentPointer = RedBlackTree.NULL;
Node pointer = this.root;
while (pointer != RedBlackTree.NULL) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
}
node.parent = parentPointer;
if (parentPointer == RedBlackTree.NULL) {
this.root = node;
} else if (node.key < parentPointer.key) {
parentPointer.left = node;
} else {
parentPointer.right = node;
}
node.left = RedBlackTree.NULL;
node.right = RedBlackTree.NULL;
node.color = Color.Red;
this.insertFixUp(node);
}
private void insertFixUp(Node node) {
// 當node不是根結點，且node的父節點顏色為紅色
while (node.parent.color == Color.Red) {
// 先判斷node的父節點是左子節點，還是右子節點，這不同的情況，解決方案也會不同
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // 如果叔叔節點是紅色，則父父一定是黑色
// 通過把父父節點變成紅色，父節點和兄弟節點變成黑色，然後在判斷父父節點的顏色是否合適
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.right) { // node是其父節點的右子節點，且叔叔節點是黑色
// 對node的父節點進行左旋轉
node = node.parent;
this.leftRotate(node);
} else { // node如果叔叔節點是黑色，node是其父節點的左子節點，父父節點是黑色
// 把父節點變成黑色，父父節點變成紅色，對父父節點進行右旋轉
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.rightRotate(node.parent.parent);
}
} else {
Node uncleNode = node.parent.parent.left;
if (uncleNode.color == Color.Red) {
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.left) {
node = node.parent;
this.rightRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.leftRotate(node.parent.parent);
}
}
}
// 如果之前樹中沒有節點，那麼新加入的點就成了新結點，而新插入的結點都是紅色的，所以需要修改。
this.root.color = Color.Black;
}
/**
* n2替代n1
*
* @param n1
* @param n2
*/
private void transplant(Node n1, Node n2) {
if (n1.parent == RedBlackTree.NULL) { // 如果n1是根節點
this.root = n2;
} else if (n1.parent.left == n1) { // 如果n1是其父節點的左子節點
n1.parent.left = n2;
} else { // 如果n1是其父節點的右子節點
n1.parent.right = n2;
}
n2.parent = n1.parent;
}
/**
* 刪除節點node
*
* @param node
*/
public void delete(Node node) {
Node pointer1 = node;
// 用於記錄被刪除的顏色，如果是紅色，可以不用管，但如果是黑色，可能會破壞紅黑樹的屬性
Color pointerOriginColor = pointer1.color;
// 用於記錄問題的出現點
Node pointer2;
if (node.left == RedBlackTree.NULL) {
pointer2 = node.right;
this.transplant(node, node.right);
} else if (node.right == RedBlackTree.NULL) {
pointer2 = node.left;
this.transplant(node, node.left);
} else {
// 如要刪除的位元組有兩個子節點，則找到其直接後繼（右子樹最小值），直接後繼節點沒有非空左子節點。
pointer1 = node.right.minimum();
// 記錄直接後繼的顏色和其右子節點
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// 如果其直接後繼是node的右子節點，不用進行處理
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// 否則，先把直接後繼從樹中提取出來，用來替換node
this.transplant(pointer1, pointer1.right);
pointer1.right = node.right;
pointer1.right.parent = pointer1;
}
// 用node的直接後繼替換node，繼承node的顏色
this.transplant(node, pointer1);
pointer1.left = node.left;
pointer1.left.parent = pointer1;
pointer1.color = node.color;
}
if (pointerOriginColor == Color.Black) {
this.deleteFixUp(pointer2);
}
}
/**
* The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4
*
* @param node
*/
private void deleteFixUp(Node node) {
// 如果node不是根節點，且是黑色
while (node != this.root && node.color == Color.Black) {
// 如果node是其父節點的左子節點
if (node == node.parent.left) {
// 記錄node的兄弟節點
Node pointer1 = node.parent.right;
// 如果node兄弟節點是紅色
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
leftRotate(node.parent);
pointer1 = node.parent.right;
}
if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.right.color == Color.Black) {
pointer1.left.color = Color.Black;
pointer1.color = Color.Red;
rightRotate(pointer1);
pointer1 = node.parent.right;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.right.color = Color.Black;
leftRotate(node.parent);
node = this.root;
}
} else {
// 記錄node的兄弟節點
Node pointer1 = node.parent.left;
// 如果他兄弟節點是紅色
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
rightRotate(node.parent);
pointer1 = node.parent.left;
}
if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.left.color == Color.Black) {
pointer1.right.color = Color.Black;
pointer1.color = Color.Red;
leftRotate(pointer1);
pointer1 = node.parent.left;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.left.color = Color.Black;
rightRotate(node.parent);
node = this.root;
}
}
}
node.color = Color.Black;
}
private void innerWalk(Node node) {
if (node != NULL) {
innerWalk(node.left);
System.out.println(node);
innerWalk(node.right);
}
}
/**
* 中序遍歷
*/
public void innerWalk() {
this.innerWalk(this.root);
}
/**
* 層次遍歷
*/
public void print() {
Queue<Node> queue = new LinkedList<>();
queue.add(this.root);
while (!queue.isEmpty()) {
Node temp = queue.poll();
System.out.println(temp);
if (temp.left != NULL)
queue.add(temp.left);
if (temp.right != NULL)
queue.add(temp.right);
}
}
// 查找
public Node search(int key) {
Node pointer = this.root;
while (pointer != NULL && pointer.key != key) {
pointer = pointer.key < key ? pointer.right : pointer.left;
}
return pointer;
}
}
6、演示
演示程式碼：
public class Test01 {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
RedBlackTree redBlackTree = new RedBlackTree();
for (int i = 0; i < arr.length; i++) {
redBlackTree.insert(new Node(arr[i]));
}
System.out.println("樹的高度： " + redBlackTree.root.height());
System.out.println("左子樹的高度： " + redBlackTree.root.left.height());
System.out.println("右子樹的高度： " + redBlackTree.root.right.height());
System.out.println("層次遍歷");
redBlackTree.print();
// 要刪除節點
Node node = redBlackTree.search(4);
redBlackTree.delete(node);
System.out.println("樹的高度： " + redBlackTree.root.height());
System.out.println("左子樹的高度： " + redBlackTree.root.left.height());
System.out.println("右子樹的高度： " + redBlackTree.root.right.height());
System.out.println("層次遍歷");
redBlackTree.print();
}
}
結果：
樹的高度： 4
左子樹的高度： 2
右子樹的高度： 3
層次遍歷
[key: 4, color: 黑色, parent: 0, position: null]
[key: 2, color: 紅色, parent: 4, position: left]
[key: 6, color: 紅色, parent: 4, position: right]
[key: 1, color: 黑色, parent: 2, position: left]
[key: 3, color: 黑色, parent: 2, position: right]
[key: 5, color: 黑色, parent: 6, position: left]
[key: 7, color: 黑色, parent: 6, position: right]
[key: 8, color: 紅色, parent: 7, position: right]
樹的高度： 3
左子樹的高度： 2
右子樹的高度： 2
層次遍歷
[key: 5, color: 黑色, parent: 0, position: null]
[key: 2, color: 紅色, parent: 5, position: left]
[key: 7, color: 紅色, parent: 5, position: right]
[key: 1, color: 黑色, parent: 2, position: left]
[key: 3, color: 黑色, parent: 2, position: right]
[key: 6, color: 黑色, parent: 7, position: left]
[key: 8, color: 黑色, parent: 7, position: right]
7、參考
《演算法導論》（第3版） 英文版
