2-3-4树

红黑树由2-3-4树演变而来。在开始红黑树之前我先介绍一下2-3-4树。2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以保证在O(lgn)的时间内完成查找、插入和删除操作。它主要满足以下性质：
1、2-3-4树所有的叶子结点都在同一层
2、结点只能是2结点或3结点或4结点

• 2结点：要么有2个子结点,要么没有子结点
• 3结点：要么有3个子结点,要么没有子结点
• 4结点：要么有4个子结点,要么没有子结点

2-3-4树如何转换成红黑树
2结点可以转化成黑结点
3结点有两种转变模式所以按不同方式的转化会得到不同的红黑树
但无论按哪种方式父结点都是黑色（上黑下红）
4结点可以转化成一个黑的父结点和两个红色子结点

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
红黑树具有以下特点：
1、每个结点要么是黑色的要么是红色的
2、根结点都是黑丝的
3、每个叶子结点都是黑色的（叶子结点为null）
4、每个红色结点的两个子节点都是黑色的（不存在两个连续的红结点）
5、从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点

红黑树添加结点思路分析

1、按二叉排序树的规则添加结点
2、红黑树的平衡调整：旋转+变色
当我们添加结点后有以下8中情况会导致红黑树失去平衡

注意：如果上图12结点是根结点还需要将12变回黑色

代码实现

public class Node{
    private Node parent; //父结点
    private Node left; //左子结点
    private Node right; //右子结点
    private boolean color; //颜色
    private int key;
    private String value;
    
    public Node(int key, String value, Node parent) {
        this.key = key;
        this.value = value;
        this.parent= parent;
    }
    /*中序遍历*/
    public void midDisplay(){
        if (this.left != null) {
            this.left.midDisplay();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midDisplay();
        }
    }
	getter and setter 方法
    @Override
    public String toString() {
        return "Node{" +
                "color=" + (color ? "黑" : "红") +
                ", key=" + key +
                ", value=" + value +
                ",左子结点key=" +(left==null ? "null" : left.key) +
                ",右子结点key=" +(right==null ? "null" : right.key) +
                '}';
    }
}

public class BRTree  {
    /*false表示红色 true表示黑色*/
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private Node root;

    /*中序遍历*/
    public void midShow(){
        if (this.root != null){
            this.root.midDisplay();
        }else{
            System.out.println("二叉树为空");
        }
    }
    /*左旋*/
    private void leftRotate(Node node){
        if (node != null) {
            Node right = node.getRight();
            node.setRight(right.getLeft());
            if (node.getLeft() != null) {
                right.getLeft().setParent(node);
            }
            right.setParent(node.getParent());
            if (node.getParent() == null){
                root = right;
            }else if (node.getParent().getLeft() == node){
                node.getParent().setLeft(right);
            }else{
                node.getParent().setRight(right);
            }
            right.setLeft(node);
            node.setParent(right);
        }
    }

    /*右旋*/
    private void rightRotate(Node node){
        if (node != null) {
            Node left = node.getLeft();
            node.setLeft(left.getRight());
            if (node.getRight() != null) {
                left.getRight().setParent(node);
            }
            left.setParent(node.getParent());
            if (node.getParent() == null){
                root = left;
            }else if (node.getParent().getLeft() == node){
                node.getParent().setLeft(left);
            }else{
                node.getParent().setRight(left);
            }
            left.setRight(node);
            node.setParent(left);
        }
    }

    /**
     * 新增结点
     *  1、普通的二叉排序树的结点插入
     *  2、红黑树的平衡：旋转+变色
     * @param key
     * @param value
     */
    public void put(int key,String value){
        Node temp = this.root;
        if (temp == null) {
            /*红黑树为空*/
            root = new Node(key,value,null);
            root.setColor(BLACK);
            return;
        }
        /*记录查找插入的位置*/
        int cmp = 0;
        /*记录父节点*/
        Node parent = null;
        /*找到插入结点的位置*/
        while(temp != null){
            parent = temp;
            cmp = key - temp.getKey();
            if (cmp < 0) {
                /*key值比当前结点的值小 从左子树继续寻找*/
                temp = temp.getLeft();
            }else if (cmp > 0){
                /*key值比当前结点的值大 从右子树继续寻找*/
                temp = temp.getRight();
            }else{
                temp.setValue(value);
                return;
            }
        }
        Node addNode = new Node(key,value,parent);
        if (cmp < 0){
            parent.setLeft(addNode);
        }else {
            parent.setRight(addNode);
        }
        /*调整红黑树*/
        adjustBRTree(addNode);
    }

    /*获取node结点的颜色*/
    private boolean colorOf(Node node){
        return node == null ? BLACK : node.isColor();
    }
    /*设置node结点的颜色*/
    private void setColor(Node node,boolean color){
        if (node != null){
            node.setColor(color);
        }
    }
    /*获取node结点的父节点*/
    private Node parentOf(Node node){
        return node ==null ? null : node.getParent();
    }
    /*获取node结点的左子结点*/
    private Node leftOf(Node node){
        return node == null ? null : node.getLeft();
    }
    /*获取node结点的右子结点*/
    private Node rightOf(Node node){
        return node == null ? null :node.getRight();
    }

    /**
     * node 添加的结点
     * @param node
     */
    private void adjustBRTree(Node node) {
        /*插入的结点都是红色结点*/
        setColor(node,RED);
        /*如果当前结点的父节点是红结点就需要调整红黑树*/
        while(node != null && node != root && parentOf(node).isColor() == RED) {
             /*parentOf(parentOf(node))为什么不会空指针？
                只有父结点是红节点才会进入循环 而红结点不可能是根结点
                所以当前结点一定有爷爷结点
             */
             if (parentOf(node) == parentOf(parentOf(node)).getLeft()){
                 /*当前结点的父节点是爷爷结点的左子结点*/
                 //叔叔结点
                 Node uncleNode = rightOf(parentOf(parentOf(node)));
                 if(colorOf(uncleNode) == RED){
                     /*叔叔结点存在*/
                     /*将父结点和叔叔结点的颜色设置成黑色*/
                     setColor(parentOf(node),BLACK);
                     setColor(uncleNode,BLACK);
                     /*将爷爷结点的颜色设置成红色*/
                     setColor(parentOf(parentOf(node)),RED);
                     node = parentOf(parentOf(node));
                 }else{
                     /*没有叔叔结点*/
                     if (node == rightOf(parentOf(node))){
                         /*如果插入的结点是父节点的右结点 那么需要双旋*/
                         /*根据父结点做左旋操作*/
                         leftRotate(parentOf(node));
                     }
                     setColor(parentOf(node),BLACK);
                     setColor(parentOf(parentOf(node)),RED);
                     rightRotate(parentOf(parentOf(node)));
                 }
             }else{
                 /*当前结点的父节点是爷爷结点的左子结点*/
                 Node uncleNode = leftOf(parentOf(parentOf(node)));
                 if(colorOf(uncleNode) == RED){
                     setColor(parentOf(node),BLACK);
                     setColor(uncleNode,BLACK);
                     /*将爷爷结点的颜色设置成红色*/
                     setColor(parentOf(parentOf(node)),RED);
                     node = parentOf(parentOf(node));
                 }else{
                     /*没有叔叔结点*/
                     if (node == leftOf(parentOf(node))){
                         /*根据父结点做右旋操作*/
                         rightRotate(parentOf(node));
                     }
                     setColor(parentOf(node),BLACK);
                     setColor(parentOf(parentOf(node)),RED);
                     leftRotate(parentOf(parentOf(node)));
                 }
             }
        }
        /*根结点都为黑色*/
        setColor(root,BLACK);
    }
}

测试类

public class BRTreeTest {
    public static void main(String[] args) {
        BRTree brTree = new BRTree();
        brTree.put(1,"张三");
        brTree.put(2,"李四");
        brTree.put(3,"王五");
        brTree.put(4,"赵六");
        brTree.put(5,"田七");
        brTree.put(6,"陈八");
        brTree.midShow();
    }
}

运行结果

Node{color=黑, key=1, value=张三,左子结点key=null,右子结点key=null}
Node{color=黑, key=2, value=李四,左子结点key=1,右子结点key=4}
Node{color=黑, key=3, value=王五,左子结点key=null,右子结点key=null}
Node{color=红, key=4, value=赵六,左子结点key=3,右子结点key=5}
Node{color=黑, key=5, value=田七,左子结点key=null,右子结点key=6}
Node{color=红, key=6, value=陈八,左子结点key=null,右子结点key=null}

Process finished with exit code 0

验证一下