最近研究紅黑樹笋籽，簡單的實(shí)現(xiàn)了一個java的紅黑樹代碼椭员，親測沒有問題，相關(guān)實(shí)現(xiàn)的說明都在注釋中侍芝。
實(shí)現(xiàn)時遇到的坑：
實(shí)現(xiàn)的時候遇到的坑出現(xiàn)在紅黑樹的刪除階段埋同，網(wǎng)上各種資料都是說刪除的時候按照二叉查找樹進(jìn)行刪除就好了凶赁，結(jié)果這塊在進(jìn)行紅黑樹平衡的時候，待刪除的節(jié)點(diǎn)是誰致板，替換的節(jié)點(diǎn)是誰很容易搞混咏窿，下面代碼在寫刪除這塊代碼的時候特意標(biāo)明了待刪除節(jié)點(diǎn)和替換的節(jié)點(diǎn)是誰，便于在看原理的時候可以更好的理解萝挤。
/**
* Created by xiaosong on 2017/12/27.
* 紅黑樹的簡單實(shí)現(xiàn)
* 紅黑樹的特性:
* （1）每個節(jié)點(diǎn)或者是黑色怜珍，或者是紅色凤粗。
* （2）根節(jié)點(diǎn)是黑色。
* （3）每個葉子節(jié)點(diǎn)（NIL）是黑色揭璃。 [注意：這里葉子節(jié)點(diǎn)亭罪，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
* （4）如果一個節(jié)點(diǎn)是紅色的情组，則它的子節(jié)點(diǎn)必須是黑色的。
* （5）從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)肆氓。
*/
public class RBTree<T> {
public static class TreeNode<T> {
private T data;//數(shù)據(jù)值
private TreeNode<T> left;
private TreeNode<T> right;
private TreeNode<T> parent;
private Color color;
private int value;//數(shù)據(jù)的權(quán)重
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
enum Color {
BLACK, RED
}
private TreeNode<T> root;
/**
* 插入節(jié)點(diǎn)
* 首先將該節(jié)點(diǎn)以二叉平衡樹的方式插入到相應(yīng)位置谢揪，然后使其滿足紅黑樹的性質(zhì)
*
* @param node
*/
public void insert(TreeNode<T> node) {
if (root == null) {//樹中無元素捐凭，則將插入元素當(dāng)做根結(jié)點(diǎn)
root = node;
root.parent = null;
root.left = null;
root.right = null;
root.color = Color.BLACK;//根節(jié)點(diǎn)必是黑色
return;
}
//按二叉查找樹的方式將該節(jié)點(diǎn)插入
TreeNode<T> comNode = root;
while (comNode != null) {
if (comNode.value >= node.value) {
if (comNode.left == null) {
comNode.left = node;
break;
} else {
comNode = comNode.left;
}
} else {
if (comNode.right == null) {
comNode.right = node;
break;
} else {
comNode = comNode.right;
}
}
}
node.parent = comNode;
node.color = Color.RED;//當(dāng)前新插入且非根節(jié)點(diǎn)初始必為紅色
node.left = null;
node.right = null;
doAddBalance(node);//插入節(jié)點(diǎn)后茁肠，將紅黑樹進(jìn)行變換垦梆，使其繼續(xù)符合紅黑樹的性質(zhì)
}
/**
* 刪除節(jié)點(diǎn)
*
* @param node
*/
public void delete(TreeNode<T> node) {
delete(node.value);
}
public void delete(int value) {
//找到要刪除的節(jié)點(diǎn)
TreeNode<T> needDelete = null;
TreeNode<T> currentNode = root;
while (currentNode != null) {
if (currentNode.value == value) {
needDelete = currentNode;
break;
} else if (currentNode.value > value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
if (needDelete != null) {
doDelete(needDelete);
}
}
/**
* 添加時進(jìn)行的紅黑樹性質(zhì)匹配操作
*
* @param node
*/
private void doAddBalance(TreeNode<T> node) {
TreeNode<T> currentNode = node;
TreeNode<T> grandP;
TreeNode<T> uncle;
while (currentNode.parent != null && currentNode.parent.color == Color.RED) {//當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色或當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)
grandP = currentNode.parent.parent;
if (grandP.left == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的左孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
uncle = currentNode.parent.parent.right;//叔叔節(jié)點(diǎn)
if (uncle == null || uncle.color == Color.BLACK) {//叔叔節(jié)點(diǎn)是黑色
if (currentNode.parent.right == currentNode) {//當(dāng)前節(jié)點(diǎn)是右孩子
currentNode = currentNode.parent;//以當(dāng)前節(jié)點(diǎn)父親節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)
leftRotate(currentNode);//對新的當(dāng)前節(jié)點(diǎn)進(jìn)行左旋
} else if (currentNode.parent.left == currentNode) {//當(dāng)前節(jié)點(diǎn)是左孩子
currentNode.parent.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為黑色
grandP.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)設(shè)置為紅色
rightRotate(grandP);//對當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)進(jìn)行右旋
}
} else {//叔叔節(jié)點(diǎn)是紅色
// (01) 將“父節(jié)點(diǎn)”設(shè)為黑色托猩。
currentNode.parent.color = Color.BLACK;
// (02) 將“叔叔節(jié)點(diǎn)”設(shè)為黑色站刑。
uncle.color = Color.BLACK;
// (03) 如果祖父節(jié)點(diǎn)不是根節(jié)點(diǎn)，將“祖父節(jié)點(diǎn)”設(shè)為“紅色”摆尝。
if (grandP.parent != null) {
grandP.color = Color.RED;
}
// (04) 將“祖父節(jié)點(diǎn)”設(shè)為“當(dāng)前節(jié)點(diǎn)”(紅色節(jié)點(diǎn))因悲；
currentNode = grandP;
}
} else if (grandP.right == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
uncle = currentNode.parent.parent.left;//叔叔節(jié)點(diǎn)
if (uncle == null || uncle.color == Color.BLACK) {//叔叔節(jié)點(diǎn)是黑色
if (grandP.right == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
if (currentNode.parent.left == currentNode) {//當(dāng)前節(jié)點(diǎn)是左孩子
currentNode = currentNode.parent;//以當(dāng)前節(jié)點(diǎn)父親節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)
rightRotate(currentNode);//對新的當(dāng)前節(jié)點(diǎn)進(jìn)行右旋
} else if (currentNode.parent.right == currentNode) {//當(dāng)前節(jié)點(diǎn)是右孩子
currentNode.parent.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為黑色
grandP.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)設(shè)置為紅色
leftRotate(grandP);//對當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)進(jìn)行左旋
}
}
} else {//叔叔節(jié)點(diǎn)是紅色
//同上邊處理方式相同
currentNode.parent.color = Color.BLACK;
uncle.color = Color.BLACK;
if (grandP.parent != null) {
grandP.color = Color.RED;
}
currentNode = grandP;
}
}
}
}
/**
* 刪除時進(jìn)行的紅黑樹性質(zhì)匹配操作
*
* @param node
*/
public void doDeleteBalance(TreeNode<T> node) {
TreeNode<T> currentNode = node;
while (currentNode != null) {
if (currentNode.color == Color.RED) {//當(dāng)前節(jié)點(diǎn)為紅色晃琳，直接涂黑處理
currentNode.color = Color.BLACK;
return;
} else {//當(dāng)前節(jié)點(diǎn)為黑色卫旱，需要分情況處理
if (currentNode.parent == null) return;//根節(jié)點(diǎn)，不做處理
TreeNode<T> brother;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
brother = getBrother(currentNode);//獲取當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
if (node.parent.left == node) {//被刪節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
if (brother.color == Color.RED) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
currentNode.parent.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色
brother.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)置黑
leftRotate(currentNode.parent);//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)左旋
} else if (brother.color == Color.BLACK) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色
if ((brother.left == null || brother.left.color == Color.BLACK) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左右孩子都是黑色
brother.color = Color.RED;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)顏色變?yōu)榧t色
currentNode = currentNode.parent;//將父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
} else if (brother.right != null && brother.right.color == Color.RED) {//兄弟節(jié)點(diǎn)的右孩子是紅色
brother.color = currentNode.parent.color;//將兄弟節(jié)點(diǎn)顏色置為當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色
currentNode.parent.color = Color.BLACK;//當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)置黑
brother.right.color = Color.BLACK;//兄弟節(jié)點(diǎn)右孩子置黑
leftRotate(currentNode.parent);//以當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)為支點(diǎn)左旋
return;
} else if ((brother.left != null && brother.left.color == Color.RED) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左孩子是紅色，右孩子是黑色
brother.left.color = Color.BLACK;//將兄弟節(jié)點(diǎn)的左孩子變?yōu)楹谏? brother.color = Color.RED;//兄弟節(jié)點(diǎn)變?yōu)榧t色
rightRotate(brother);//將兄弟節(jié)點(diǎn)右旋
}
}
} else if (node.parent.right == node) {//被刪節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
if (brother.color == Color.RED) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
currentNode.parent.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色
brother.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)置黑
rightRotate(currentNode.parent);//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)右旋
} else if (brother.color == Color.BLACK) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色
if ((brother.left == null || brother.left.color == Color.BLACK) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左右孩子都是黑色
brother.color = Color.RED;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)顏色變?yōu)榧t色
currentNode = currentNode.parent;//將父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
} else if (brother.left != null && brother.left.color == Color.RED) {//兄弟節(jié)點(diǎn)的左孩子是紅色
brother.color = currentNode.parent.color;//將兄弟節(jié)點(diǎn)顏色置為當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色
currentNode.parent.color = Color.BLACK;//當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)置黑
brother.left.color = Color.BLACK;//兄弟節(jié)點(diǎn)左孩子置黑
rightRotate(currentNode.parent);//以當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)為支點(diǎn)右旋
return;
} else if ((brother.right != null && brother.right.color == Color.RED) && (brother.left == null || brother.left.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的右孩子是紅色涝桅，左孩子是黑色
brother.right.color = Color.BLACK;//將兄弟節(jié)點(diǎn)的右孩子變?yōu)楹谏? brother.color = Color.RED;//兄弟節(jié)點(diǎn)變?yōu)榧t色
leftRotate(brother);//將兄弟節(jié)點(diǎn)右旋
}
}
}
}
}
}
public TreeNode<T> getBrother(TreeNode<T> node) {//獲取當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
if (node.parent.left != node) {//重新設(shè)置X的兄弟節(jié)點(diǎn)
return node.parent.left;
} else {
return node.parent.right;
}
}
private void doDelete(TreeNode<T> node) {
TreeNode<T> currentNode;//要替換的節(jié)點(diǎn)
TreeNode<T> needDelete = node;//要刪除的節(jié)點(diǎn)
//先進(jìn)行二叉排序樹的刪除操作冯遂，找到要進(jìn)行替換的節(jié)點(diǎn)
if (node.left != null && node.right != null) {//待刪除節(jié)點(diǎn)左右子樹均在
TreeNode<T> succed = node.left;//尋找該節(jié)點(diǎn)的后繼節(jié)點(diǎn)（找左兒子的最右子樹）
while (succed.right != null) {
succed = succed.right;
}
node.value = succed.value;//將原刪除節(jié)點(diǎn)的值替換為其后繼節(jié)點(diǎn)的值谒获，將后繼節(jié)點(diǎn)作為待刪除節(jié)點(diǎn)
node.data = succed.data;
needDelete = succed;
}
currentNode = needDelete.left != null ? needDelete.left : needDelete.right;
if (currentNode != null) {
currentNode.parent = needDelete.parent;//刪除待刪除節(jié)點(diǎn)，并用其子節(jié)點(diǎn)代替
if (needDelete.left == currentNode) {
currentNode.parent.left = currentNode;
} else {
currentNode.parent.right = currentNode;
}
needDelete.left = needDelete.right = needDelete.parent = null;
if (needDelete.color == Color.BLACK) {
doDeleteBalance(node);
}
} else if (needDelete.parent == null) {//說明當(dāng)前是根節(jié)點(diǎn)
root = null;
} else {//說明待刪除節(jié)點(diǎn)是個葉子節(jié)點(diǎn)
currentNode = needDelete;//將自己作為替換節(jié)點(diǎn)寻定，同時自己也是待刪除節(jié)點(diǎn)
if (needDelete.color == Color.BLACK) {
doDeleteBalance(currentNode);
}
//平衡之后，將其刪除
if (currentNode.parent != null) {
if (currentNode.parent.left == currentNode) {
currentNode.parent.left = null;
} else if (currentNode.parent.right == currentNode) {
currentNode.parent.right = null;
}
currentNode.parent = null;
}
}
}
public boolean isLeaf(TreeNode<T> node) {
return node.left == null && node.right == null;
}
/**
* 左旋操作琅锻，傳入的參數(shù)為要左旋的節(jié)點(diǎn)
*/
private void leftRotate(TreeNode<T> des) {
TreeNode<T> x = des;
TreeNode<T> y = des.right;
TreeNode<T> b = y.left;
x.right = b;//將y的左孩子變?yōu)閤的右孩子
if (b != null) {
b.parent = x;
}
y.parent = x.parent;//將x的父親設(shè)置為y的父親
if (x.parent == null) {//根節(jié)點(diǎn)
root = y;
} else {//非根節(jié)點(diǎn)
if (x.parent.left == x) {//x是其父節(jié)點(diǎn)的左孩子
x.parent.left = y;
} else if (x.parent.right == x) {//x是其父節(jié)點(diǎn)的右孩子
x.parent.right = y;
}
}
x.parent = y;//將y設(shè)置成x的父親
y.left = x;//將x設(shè)置為y的左孩子
}
/**
* 右旋操作恼蓬，傳入的參數(shù)為要右旋的節(jié)點(diǎn)
*/
private void rightRotate(TreeNode<T> des) {
TreeNode<T> y = des;
TreeNode<T> x = des.left;
TreeNode<T> b = x.right;
y.left = b;//將x的右孩子變?yōu)閥的左孩子
if (b != null) {
b.parent = y;
}
//將y的父親設(shè)置為x的父親
x.parent = y.parent;
if (y.parent == null) {//根節(jié)點(diǎn)
root = x;
} else {//非根節(jié)點(diǎn)
if (y.parent.left == y) {//y是其父節(jié)點(diǎn)的左孩子
y.parent.left = x;
} else if (y.parent.right == y) {//y是其父節(jié)點(diǎn)的右孩子
y.parent.right = x;
}
}
y.parent = x;//將x設(shè)置成y的父親
x.right = y;//將y設(shè)置為x的右孩子
}
}
參考資料：
1.https://www.cnblogs.com/skywang12345/p/3245399.html
2.java TreeMap的源碼
