红黑树构建Java代码

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;
    }
}