利用Java實(shí)現(xiàn)紅黑樹(shù)
更新時(shí)間：2021年09月15日 09:44:18 作者：胡不慌
紅黑樹(shù)是眾多“平衡的”搜索樹(shù)模式中的一種，在最壞情況下，它相關(guān)操作的時(shí)間復(fù)雜度為O(log n)，接下倆小編將子啊下文詳細(xì)介紹Java是如何實(shí)現(xiàn)紅黑樹(shù)的
1、紅黑樹(shù)的屬性
紅黑樹(shù)是一種二分查找樹(shù)，與普通的二分查找樹(shù)不同的一點(diǎn)是，紅黑樹(shù)的每個(gè)節(jié)點(diǎn)都有一個(gè)顏色（color）屬性。該屬性的值要么是紅色，要么是黑色。
通過(guò)限制從根到葉子的任何簡(jiǎn)單路徑上的節(jié)點(diǎn)顏色，紅黑樹(shù)確保沒(méi)有比任何其他路徑長(zhǎng)兩倍的路徑，從而使樹(shù)近似平衡。
假設(shè)紅黑樹(shù)節(jié)點(diǎn)的屬性有鍵（key）、顏色（color）、左子節(jié)點(diǎn)（left）、右子節(jié)點(diǎn)（right），父節(jié)點(diǎn)（parent）。
一棵紅黑樹(shù)必須滿(mǎn)足下面有下面這些特性（ 紅黑樹(shù)特性 ）：
- 樹(shù)中的每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色；
- 根節(jié)點(diǎn)是黑色；
- 每個(gè)葉子節(jié)點(diǎn)（null）是黑色；
- 如果某節(jié)點(diǎn)是紅色的，它的兩個(gè)子節(jié)點(diǎn)都是黑色；
- 對(duì)于每個(gè)節(jié)點(diǎn)到后面任一葉子節(jié)點(diǎn)（null）的所有路徑，都有相同數(shù)量的黑色節(jié)點(diǎn)。
為了在紅黑樹(shù)代碼中處理邊界條件方便，我們用一個(gè)哨兵變量代替null。對(duì)于一個(gè)紅黑樹(shù)tree，哨兵變量RedBlackTree.NULL（下文代碼中）是一個(gè)和其它節(jié)點(diǎn)有同樣屬性的節(jié)點(diǎn)，它的顏色（color）屬性是黑色，其它屬性可以任意取值。
我們使用哨兵變量是因?yàn)槲覀兛梢园岩粋€(gè)節(jié)點(diǎn)node的子節(jié)點(diǎn)null當(dāng)成一個(gè)普通節(jié)點(diǎn)。
在這里，我們使用哨兵變量RedBlackTree.NULL代替樹(shù)中所有的null（所有的葉子節(jié)點(diǎn)及根節(jié)點(diǎn)的父節(jié)點(diǎn)）。
我們把從一個(gè)節(jié)點(diǎn)n（不包括）到任一葉子節(jié)點(diǎn)路徑上的黑色節(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為 黑色高度 ，用bh(n)表示。一棵紅黑樹(shù)的黑色高度是其根節(jié)點(diǎn)的黑色高度。
關(guān)于紅黑樹(shù)的搜索，求最小值，求最大值，求前驅(qū)，求后繼這些操作的代碼與二分查找樹(shù)的這些操作的代碼基本一致?？梢栽谟?code>java實(shí)現(xiàn)二分查找樹(shù)查看。
結(jié)合上文給出下面的代碼。
用一個(gè)枚舉類(lèi)Color表示顏色：
public enum Color {
Black("黑色"), Red("紅色");
private String color;
private Color(String color) {
this.color = color;
}
@Override
public String toString() {
return color;
}
}
類(lèi)Node表示節(jié)點(diǎn)：
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 + "]";
}
}
類(lèi)RedTreeNode表示紅黑樹(shù)：
public class RedBlackTree {
// 表示哨兵變量
public final static Node NULL = new Node(Color.Black);
public Node root;
public RedBlackTree() {
this.root = NULL;
}
}
2、旋轉(zhuǎn)
紅黑樹(shù)的插入和刪除操作，能改變紅黑樹(shù)的結(jié)構(gòu)，可能會(huì)使它不再有前面所說(shuō)的某些特性性。為了維持這些特性，我們需要改變樹(shù)中某些節(jié)點(diǎn)的顏色和位置。
我們可以通過(guò)旋轉(zhuǎn)改變節(jié)點(diǎn)的結(jié)構(gòu)。主要有 左旋轉(zhuǎn) 和 右旋轉(zhuǎn) 兩種方式。具體如下圖所示。
左旋轉(zhuǎn)：把一個(gè)節(jié)點(diǎn)n的右子節(jié)點(diǎn)right變?yōu)樗母腹?jié)點(diǎn)，n變?yōu)閞ight的左子節(jié)點(diǎn)，所以right不能為null。這時(shí)n的右指針空了出來(lái)，right的左子樹(shù)被n擠掉，所以right原來(lái)的左子樹(shù)稱(chēng)為n的右子樹(shù)。
右旋轉(zhuǎn)：把一個(gè)節(jié)點(diǎn)n的左子節(jié)點(diǎn)left變?yōu)樗母腹?jié)點(diǎn)，n變?yōu)閘eft的右子節(jié)點(diǎn)，所以left不能為null。這時(shí)n的左指針被空了出來(lái)，left的右子樹(shù)被n擠掉，所以left原來(lái)的右子樹(shù)被稱(chēng)為n的左子樹(shù)。
可在RedTreeNode類(lèi)中，加上如下實(shí)現(xiàn)代碼：
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、插入
紅黑樹(shù)的插入代碼與二分查找樹(shù)的插入代碼非常相似。只不過(guò)紅黑樹(shù)的插入操作會(huì)改變紅黑樹(shù)的結(jié)構(gòu)，使其不在有該有的特性。
在這里，新插入的節(jié)點(diǎn)默認(rèn)是紅色。
所以在插入節(jié)點(diǎn)之后，要有維護(hù)紅黑樹(shù)特性的代碼。
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;
// 維護(hù)紅黑樹(shù)屬性的方法
this.insertFixUp(node);
}
用上述方法插入一個(gè)新節(jié)點(diǎn)的時(shí)候，有兩類(lèi)情況會(huì)違反紅黑樹(shù)的特性。
- 當(dāng)樹(shù)中沒(méi)有節(jié)點(diǎn)時(shí)，此時(shí)插入的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)，而此節(jié)點(diǎn)的顏色為紅色。
- 當(dāng)新插入的節(jié)點(diǎn)成為一個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，此時(shí)存在一個(gè)紅色結(jié)點(diǎn)有紅色子節(jié)點(diǎn)的情況。
對(duì)于第一類(lèi)情況，可以直接把根結(jié)點(diǎn)設(shè)置為黑色；而針對(duì)第二類(lèi)情況，需要根據(jù)具體條件，做出相應(yīng)的解決方案。
具體代碼如下：
public void insertFixUp(Node node) {
// 當(dāng)node不是根結(jié)點(diǎn)，且node的父節(jié)點(diǎn)顏色為紅色
while (node.parent.color == Color.Red) {
// 先判斷node的父節(jié)點(diǎn)是左子節(jié)點(diǎn)，還是右子節(jié)點(diǎn)，這不同的情況，解決方案也會(huì)不同
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // 如果叔叔節(jié)點(diǎn)是紅色，則父父一定是黑色
// 通過(guò)把父父節(jié)點(diǎn)變成紅色，父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)變成黑色，然后在判斷父父節(jié)點(diǎn)的顏色是否合適
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);
}
}
}
// 如果之前樹(shù)中沒(méi)有節(jié)點(diǎn)，那么新加入的點(diǎn)就成了新結(jié)點(diǎn)，而新插入的結(jié)點(diǎn)都是紅色的，所以需要修改。
this.root.color = Color.Black;
}
下面的圖分別對(duì)應(yīng)第二類(lèi)情況中的六種及相應(yīng)處理結(jié)果。
情況1：
情況2：
情況3：
情況4：
情況5：
情況6：
4、刪除
紅黑樹(shù)中節(jié)點(diǎn)的刪除會(huì)使一個(gè)結(jié)點(diǎn)代替另外一個(gè)節(jié)點(diǎn)。所以先要實(shí)現(xiàn)這樣的代碼：
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;
}
紅黑樹(shù)的刪除節(jié)點(diǎn)代碼是基于二分查找樹(shù)的刪除節(jié)點(diǎn)代碼而寫(xiě)的。
刪除結(jié)點(diǎn)代碼：
public void delete(Node node) {
Node pointer1 = node;
// 用于記錄被刪除的顏色，如果是紅色，可以不用管，但如果是黑色，可能會(huì)破壞紅黑樹(shù)的屬性
Color pointerOriginColor = pointer1.color;
// 用于記錄問(wèn)題的出現(xiàn)點(diǎn)
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 {
// 如要?jiǎng)h除的字節(jié)有兩個(gè)子節(jié)點(diǎn)，則找到其直接后繼（右子樹(shù)最小值），直接后繼節(jié)點(diǎn)沒(méi)有非空左子節(jié)點(diǎn)。
pointer1 = node.right.minimum();
// 記錄直接后繼的顏色和其右子節(jié)點(diǎn)
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// 如果其直接后繼是node的右子節(jié)點(diǎn)，不用進(jìn)行處理
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// 否則，先把直接后繼從樹(shù)中提取出來(lái)，用來(lái)替換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);
}
}
當(dāng)被刪除節(jié)點(diǎn)的顏色是黑色時(shí)需要調(diào)用方法維護(hù)紅黑樹(shù)的特性。
主要有兩類(lèi)情況：
- 當(dāng)node是紅色時(shí)，直接變成黑色即可。
- 當(dāng)node是黑色時(shí)，需要調(diào)整紅黑樹(shù)結(jié)構(gòu)。，
private void deleteFixUp(Node node) {
// 如果node不是根節(jié)點(diǎn)，且是黑色
while (node != this.root && node.color == Color.Black) {
// 如果node是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
if (node == node.parent.left) {
// 記錄node的兄弟節(jié)點(diǎn)
Node pointer1 = node.parent.right;
// 如果他兄弟節(jié)點(diǎn)是紅色
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的兄弟節(jié)點(diǎn)
Node pointer1 = node.parent.left;
// 如果他兄弟節(jié)點(diǎn)是紅色
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;
}
對(duì)第二類(lèi)情況，有下面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;
}
/**
* 求在樹(shù)中節(jié)點(diǎn)的高度
*
* @return
*/
public int height() {
return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
}
/**
* 在以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)中，求最小節(jié)點(diǎn)
*
* @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;
}
/**
* 左旋轉(zhuǎn)
*
* @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;
}
/**
* 右旋轉(zhuǎn)
*
* @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) {
// 當(dāng)node不是根結(jié)點(diǎn)，且node的父節(jié)點(diǎn)顏色為紅色
while (node.parent.color == Color.Red) {
// 先判斷node的父節(jié)點(diǎn)是左子節(jié)點(diǎn)，還是右子節(jié)點(diǎn)，這不同的情況，解決方案也會(huì)不同
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // 如果叔叔節(jié)點(diǎn)是紅色，則父父一定是黑色
// 通過(guò)把父父節(jié)點(diǎn)變成紅色，父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)變成黑色，然后在判斷父父節(jié)點(diǎn)的顏色是否合適
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是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，且叔叔節(jié)點(diǎn)是黑色
// 對(duì)node的父節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)
node = node.parent;
this.leftRotate(node);
} else { // node如果叔叔節(jié)點(diǎn)是黑色，node是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，父父節(jié)點(diǎn)是黑色
// 把父節(jié)點(diǎn)變成黑色，父父節(jié)點(diǎn)變成紅色，對(duì)父父節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)
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);
}
}
}
// 如果之前樹(shù)中沒(méi)有節(jié)點(diǎn)，那么新加入的點(diǎn)就成了新結(jié)點(diǎn)，而新插入的結(jié)點(diǎn)都是紅色的，所以需要修改。
this.root.color = Color.Black;
}
/**
* n2替代n1
*
* @param n1
* @param n2
*/
private void transplant(Node n1, Node n2) {
if (n1.parent == RedBlackTree.NULL) { // 如果n1是根節(jié)點(diǎn)
this.root = n2;
} else if (n1.parent.left == n1) { // 如果n1是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
n1.parent.left = n2;
} else { // 如果n1是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
n1.parent.right = n2;
}
n2.parent = n1.parent;
}
/**
* 刪除節(jié)點(diǎn)node
*
* @param node
*/
public void delete(Node node) {
Node pointer1 = node;
// 用于記錄被刪除的顏色，如果是紅色，可以不用管，但如果是黑色，可能會(huì)破壞紅黑樹(shù)的屬性
Color pointerOriginColor = pointer1.color;
// 用于記錄問(wèn)題的出現(xiàn)點(diǎn)
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 {
// 如要?jiǎng)h除的字節(jié)有兩個(gè)子節(jié)點(diǎn)，則找到其直接后繼（右子樹(shù)最小值），直接后繼節(jié)點(diǎn)沒(méi)有非空左子節(jié)點(diǎn)。
pointer1 = node.right.minimum();
// 記錄直接后繼的顏色和其右子節(jié)點(diǎn)
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// 如果其直接后繼是node的右子節(jié)點(diǎn)，不用進(jìn)行處理
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// 否則，先把直接后繼從樹(shù)中提取出來(lái)，用來(lái)替換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不是根節(jié)點(diǎn)，且是黑色
while (node != this.root && node.color == Color.Black) {
// 如果node是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
if (node == node.parent.left) {
// 記錄node的兄弟節(jié)點(diǎn)
Node pointer1 = node.parent.right;
// 如果node兄弟節(jié)點(diǎn)是紅色
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的兄弟節(jié)點(diǎn)
Node pointer1 = node.parent.left;
// 如果他兄弟節(jié)點(diǎn)是紅色
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("樹(shù)的高度： " + redBlackTree.root.height());
System.out.println("左子樹(shù)的高度： " + redBlackTree.root.left.height());
System.out.println("右子樹(shù)的高度： " + redBlackTree.root.right.height());
System.out.println("層次遍歷");
redBlackTree.print();
// 要?jiǎng)h除節(jié)點(diǎn)
Node node = redBlackTree.search(4);
redBlackTree.delete(node);
System.out.println("樹(shù)的高度： " + redBlackTree.root.height());
System.out.println("左子樹(shù)的高度： " + redBlackTree.root.left.height());
System.out.println("右子樹(shù)的高度： " + redBlackTree.root.right.height());
System.out.println("層次遍歷");
redBlackTree.print();
}
}
到此這篇關(guān)于利用Java實(shí)現(xiàn)紅黑樹(shù)的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)紅黑樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java實(shí)戰(zhàn)小技巧之字符串與容器互轉(zhuǎn)詳解
Java.lang.String是Java的字符串類(lèi). Srting是一個(gè)不可變對(duì)象,下面這篇文章主要給大家介紹了關(guān)于java實(shí)戰(zhàn)小技巧之字符串與容器互轉(zhuǎn)的相關(guān)資料,需要的朋友可以參考下2021-08-08
Mac OS上安裝Tomcat服務(wù)器的簡(jiǎn)單步驟
這篇文章主要介紹了Mac OS上安裝Tomcat服務(wù)器的簡(jiǎn)單步驟,包括簡(jiǎn)單的啟動(dòng)命令和查看Tomcat信息的方法,需要的朋友可以參考下2015-11-11
java實(shí)現(xiàn)的xml格式化實(shí)現(xiàn)代碼
這篇文章主要介紹了java實(shí)現(xiàn)的xml格式化實(shí)現(xiàn)代碼,需要的朋友可以參考下2016-11-11
多模塊maven的deploy集成gitlab?ci自動(dòng)發(fā)版配置
這篇文章主要為大家介紹了多模塊maven項(xiàng)目deploy集成gitlab?ci自動(dòng)發(fā)版的配置流程步驟，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
這篇文章主要介紹了你知道JVM中GC?Root對(duì)象有哪些，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-01-01
Java實(shí)現(xiàn)將txt文件轉(zhuǎn)成xls文件的方法
今天小編就為大家分享一篇Java實(shí)現(xiàn)將txt文件轉(zhuǎn)成xls文件的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-10-10
SSM框架實(shí)現(xiàn)分頁(yè)和搜索分頁(yè)的示例代碼
本篇文章主要介紹了SSM框架實(shí)現(xiàn)分頁(yè)和搜索分頁(yè)的示例代碼，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-03-03
Spring中@ConditionalOnProperty注解的作用詳解
這篇文章主要介紹了Spring中@ConditionalOnProperty注解的作用詳解,@ConditionalOnProperty注解主要是用來(lái)判斷配置文件中的內(nèi)容來(lái)決定配置類(lèi)是否生效用的,如果條件不匹配,則配置類(lèi)不生效,需要的朋友可以參考下2024-01-01
Springboot?application.yml配置文件拆分方式
這篇文章主要介紹了Springboot?application.yml配置文件拆分方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-05-05
Spring boot Rabbitmq消息防丟失實(shí)踐
這篇文章主要介紹了Spring boot Rabbitmq消息防丟失實(shí)踐，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09