1 代码实现的内容
代码实现了从0构建一颗红黑树，可参考上文的例子
红黑树插入的四种情况分析 - 腾讯云开发者社区-腾讯云 (tencent.com)
2 代码
代码语言：javascript复制public class RBTree {
public static String REDCOLOR = "red";
public static String BLACKCOLOR = "black";
public static RBTreeNode rootNode;
public static void main(String[] args) {
int[] treeNodeValues = {11, 2, 14, 1, 7, 5, 8, 4, 15};
RBTreeNode[] treeNodeArr = new RBTreeNode[treeNodeValues.length];
for (int i = 0; i < treeNodeValues.length; i ) {
treeNodeArr[i] = new RBTreeNode(treeNodeValues[i], REDCOLOR);
}
rootNode = treeNodeArr[0];
rootNode.color = BLACKCOLOR;
//添加一个节点
if (treeNodeArr.length < 1) {
return;
}
for (int i = 1; i < treeNodeArr.length; i ) {
addNode(rootNode, treeNodeArr[i]);
if (treeNodeArr[i].father.color.equals(REDCOLOR)) {
adjustNode(treeNodeArr[i]);
}
}
System.out.println("test");
}
public static void addNode(RBTreeNode currentNode, RBTreeNode addedNode) {
if (addedNode.value >= currentNode.value) {
if (currentNode.right == null) {
currentNode.right = addedNode;
addedNode.father = currentNode;
} else {
addNode(currentNode.right, addedNode);
}
} else {
if (currentNode.left == null) {
currentNode.left = addedNode;
addedNode.father = currentNode;
} else {
addNode(currentNode.left, addedNode);
}
}
}
public static boolean isLeftNode(RBTreeNode judgedNode) {
if (judgedNode.father.left == judgedNode) {
return true;
} else {
return false;
}
}
//这里不做判断，只做一次应有的转换
public static void adjustNode(RBTreeNode currentNode) {
//首先判断该节点的父节点是否为红色。如果不是结束
if (currentNode.father.color != REDCOLOR) {
return;
}
//然后判断属于那种情况
boolean currentNodeIsLeft = isLeftNode(currentNode);
boolean fatherNodeIsLeft = isLeftNode(currentNode.father);
String condition = "";
//判断当前节点的树的形状
if (fatherNodeIsLeft) {
condition = "left";
if (currentNodeIsLeft) {
condition = "left";
} else {
condition = "right";
}
} else {
condition = "right";
if (currentNodeIsLeft) {
condition = "left";
} else {
condition = "right";
}
}
//首先判断如果叔父节点为红色
Boolean uncleNodeIsRedflag = false;
switch (condition) {
case "leftleft":
case "leftright":
if (currentNode.father.father.right.color.equals(REDCOLOR)) {
uncleNodeIsRedflag = true;
currentNode.father.color = BLACKCOLOR;
currentNode.father.father.right.color = BLACKCOLOR;
currentNode.father.father.color = REDCOLOR;
rootNode.color = BLACKCOLOR;
}
if (currentNode.father.father != rootNode) {
if (currentNode.father.father.father.color.equals(REDCOLOR)) {
adjustNode(currentNode.father.father);
}
}
break;
case "rightleft":
case "rightright":
if (currentNode.father.father.left.color.equals(REDCOLOR)) {
uncleNodeIsRedflag = true;
currentNode.father.color = BLACKCOLOR;
currentNode.father.father.left.color = BLACKCOLOR;
currentNode.father.father.color = REDCOLOR;
rootNode.color = BLACKCOLOR;
}
if (currentNode.father.father != rootNode) {
if (currentNode.father.father.father.color.equals(REDCOLOR)) {
adjustNode(currentNode.father.father);
}
}
break;
default:
throw new RuntimeException();
}
if (uncleNodeIsRedflag){
return;
}
//然后判断叔父节点为黑色的四种情况。
switch (condition) {
case "leftleft":
leftLeftAdjust(currentNode);
break;
case "leftright":
leftRightAdjust(currentNode);
break;
case "rightleft":
rightLeftAdjust(currentNode);
break;
case "rightright":
rightRightAdjust(currentNode);
break;
default:
throw new RuntimeException();
}
}
public static void leftLeftAdjust(RBTreeNode currentNode){
RBTreeNode preFatherNode = currentNode.father;
RBTreeNode preGrandFatherNode = currentNode.father.father;
RBTreeNode preGreadGrandFatherNode = currentNode.father.father.father;
RBTreeNode uncleNode = preGrandFatherNode.right;
if (uncleNode==null||!uncleNode.color.equals(REDCOLOR)) {
//如果是非根节点需要把转换的树的父节点挂接好
if (preGreadGrandFatherNode != null) {
//先处理祖父节点
preGreadGrandFatherNode.left = preFatherNode;
preFatherNode.father = preGrandFatherNode;
}
else {
preFatherNode.father=null;
rootNode = currentNode.father;
}
//然后处理前爷爷节点
preGrandFatherNode.father = preFatherNode;
preGrandFatherNode.left = preFatherNode.right;
preGrandFatherNode.color = REDCOLOR;
//然后处理父节点
preFatherNode.color = BLACKCOLOR;
preFatherNode.right=preGrandFatherNode;
System.out.println("test");
}
}
public static void leftRightAdjust(RBTreeNode currentNode){
RBTreeNode preFatherNode = currentNode.father;
RBTreeNode preGrandFatherNode = currentNode.father.father;
RBTreeNode preGreadGrandFatherNode = currentNode.father.father.father;
//首先旋转
preFatherNode = currentNode.father;
preGrandFatherNode = currentNode.father.father;
preGreadGrandFatherNode = currentNode.father.father.father;
preGrandFatherNode.left = currentNode;
preFatherNode.father = currentNode;
preFatherNode.right = currentNode.left;
currentNode.left.father = preFatherNode;
currentNode.father = preGrandFatherNode;
currentNode.left=preFatherNode;
//然后同leftleft
leftLeftAdjust(currentNode.left);
}
public static void rightRightAdjust(RBTreeNode currentNode) {
RBTreeNode preFatherNode = currentNode.father;
RBTreeNode preGrandFatherNode = currentNode.father.father;
RBTreeNode preGreadGrandFatherNode = currentNode.father.father.father;
RBTreeNode uncleNode = preGrandFatherNode.left;
if (uncleNode == null || !uncleNode.color.equals(REDCOLOR)) {
//如果是非根节点需要把转换的树的父节点挂接好
if (preGreadGrandFatherNode != null) {
//先处理祖父节点
preGreadGrandFatherNode.right = preFatherNode;
preFatherNode.father = preGrandFatherNode;
} else {
preFatherNode.father = null;
rootNode = currentNode.father;
}
//然后处理前爷爷节点
preGrandFatherNode.father = preFatherNode;
preGrandFatherNode.right = preFatherNode.left;
preGrandFatherNode.color = REDCOLOR;
//然后处理父节点
preFatherNode.color = BLACKCOLOR;
preFatherNode.left = preGrandFatherNode;
System.out.println("test");
}
}
public static void rightLeftAdjust(RBTreeNode currentNode){
RBTreeNode preFatherNode = currentNode.father;
RBTreeNode preGrandFatherNode = currentNode.father.father;
RBTreeNode preGreadGrandFatherNode = currentNode.father.father.father;
//首先旋转
preFatherNode = currentNode.father;
preGrandFatherNode = currentNode.father.father;
preGreadGrandFatherNode = currentNode.father.father.father;
preGrandFatherNode.right = currentNode;
preFatherNode.father = currentNode;
preFatherNode.left = currentNode.right;
currentNode.right.father = preFatherNode;
currentNode.father = preGrandFatherNode;
currentNode.right=preFatherNode;
//然后同leftleft
leftLeftAdjust(currentNode.right);
}
}
class RBTreeNode{
RBTreeNode father;
RBTreeNode right;
RBTreeNode left;
int value;
String color = "";
RBTreeNode(int value, String color){
father = null;
right = null;
left = null;
this.value = value;
this.color = color;
}
}
