Java红黑树

首先创建树结构

class Node {
    final boolean RED = true;
    final boolean BLACK = false;
    int key;
    boolean color;
    Node left, right, parent;

    public Node(int key) {
        this.key = key;
        this.color = RED;
    }

    @Override
    public String toString() {
        String str = "[";
        if (this.color == RED) {
            str += "红色";
        } else {
            str += "黑色";
        }
        return str + "," + this.key + "]";
    }
}

创建红黑树类

public class RBTree {
    final boolean RED = true;
    final boolean BLACK = false;
    Node root = null;
    
}

插入方法

      public void insertNode(int key){
        Node node = new Node(key);
        if(root == null){    //判断根节点是否为空，如果为空，当前节点即为根节点，并把颜色赋成黑色
            root = node;
            root.color = BLACK;
        }else{            //不是根节点，寻找可以当做父节点的节点
            Node cur = root;
            Node parent = null;
            do {
                parent = cur;
                if(parent.key >= key){
                    cur = cur.left;
                }else{
                    cur = cur.right;
                }
            }while (cur != null);  //找到父节点之后，判断是在左边还是右边
            node.parent = parent;
            if(parent.key >= key){
                parent.left = node;
            }else{
                parent.right = node;
            }
        }
        balanceSelf(node); //每次插入要进行自平衡
    }

在插入的时候，要进行自平衡，那么就要涉及到几个原子操作：左旋/右旋，变色


左旋

图中的左旋，我们注意到，只有3个地方变了(不要纠结颜色，原子操作互不干扰)
①X的父亲变成了Z的父亲
②Z的左子树从A变成了X
③X的右子树变成了A
左旋方法就很简单了

  public void rotateToLeft(Node node) {//把node看成X
        Node x = node;
        Node z = x.right;
        if (z.left != null) {
            // 如果z的左子树不为空
            z.left.parent = x;

        }
        x.right = z.left;
        if (x.parent == null) {//如果是根节点
            root = z;
        } else if (x.parent.left == x) {//如果x是x父亲的左子树
            x.parent.left = z;
        } else {
            x.parent.right = z;
        }
        z.parent = x.parent;
        //建立z和x之间的父子关系
        x.parent = z;
        z.left = x;
    }

右旋和左旋相左就是


右旋

右旋

     public void rotateToRight(Node node) {
        Node x = node;
        Node y = node.left;
        if (y.right != null) {
            y.right.parent = x;
        }
        x.left = y.right;
        if (x.parent == null) {
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = x;
        }
        y.parent = x.parent;
        x.parent = y;
        y.right = x;
    }

能左旋右旋变色，就可以进行自平衡了

  private void balanceSelf(Node node) {
        Node parent,grandParent;
        //父存在并红色，因为刚插入的数据是红色，所以形成了红 红，要进行自平衡
        while((parent = node.parent)!= null && parent.color == RED){
            grandParent = parent.parent;
            //判断父是祖父的左子树还是右子树，目的是为了找出叔叔节点
            if(parent == grandParent.left){
                Node uncle = grandParent.right;

                //case 1 : 叔叔存在并红色
                if(null != uncle && uncle.color == RED){
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又当成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，当前节点是右孩子
                if(parent.right == node){
                    rotateToLeft(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，当前是左孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToRight(grandParent);

            }else{
                Node uncle = grandParent.left;

                //case 1 : 叔叔存在并红色
                if(null != uncle && uncle.color == RED){
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又当成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，当前节点是左孩子
                if(parent.left == node){
                    rotateToRight(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，当前是右孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToLeft(grandParent);

            }
        }
        root.color = BLACK; // 根节点黑色
    }

删除------
全代码

public class RBTree {
    final boolean RED = true;
    final boolean BLACK = false;
    Node root = null;

    public void insertNode(int key) {
        Node node = new Node(key);
        if (root == null) {    //判断根节点是否为空，如果为空，当前节点即为根节点，并把颜色赋成黑色
            root = node;
            root.color = BLACK;
        } else {            //不是根节点，寻找可以当做父节点的节点
            Node cur = root;
            Node parent = null;
            do {
                parent = cur;
                if (parent.key >= key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            } while (cur != null);  //找到父节点之后，判断是在左边还是右边
            node.parent = parent;
            if (parent.key >= key) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
        balanceSelf(node);
    }

    public void rotateToLeft(Node node) {//把node看成X
        Node x = node;
        Node z = x.right;
        if (z.left != null) {
            // 如果z的左子树不为空
            z.left.parent = x;

        }
        x.right = z.left;
        if (x.parent == null) {//如果是根节点
            root = z;
        } else if (x.parent.left == x) {//如果x是x父亲的左子树
            x.parent.left = z;
        } else {
            x.parent.right = z;
        }
        z.parent = x.parent;
        //建立z和x之间的父子关系
        x.parent = z;
        z.left = x;
    }

    public void rotateToRight(Node node) {
        Node x = node;
        Node y = node.left;
        if (y.right != null) {
            y.right.parent = x;
        }
        x.left = y.right;
        if (x.parent == null) {
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = x;
        }
        y.parent = x.parent;
        x.parent = y;
        y.right = x;
    }


    private void balanceSelf(Node node) {
        Node parent, grandParent;
        //父存在并红色，因为刚插入的数据是红色，所以形成了红 红，要进行自平衡
        while ((parent = node.parent) != null && parent.color == RED) {
            grandParent = parent.parent;
            //判断父是祖父的左子树还是右子树，目的是为了找出叔叔节点
            if (parent == grandParent.left) {
                Node uncle = grandParent.right;

                //case 1 : 叔叔存在并红色
                if (null != uncle && uncle.color == RED) {
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又当成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，当前节点是右孩子
                if (parent.right == node) {
                    rotateToLeft(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，当前是左孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToRight(grandParent);

            } else {
                Node uncle = grandParent.left;

                //case 1 : 叔叔存在并红色
                if (null != uncle && uncle.color == RED) {
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又当成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，当前节点是左孩子
                if (parent.left == node) {
                    rotateToRight(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，当前是右孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToLeft(grandParent);

            }
        }
        root.color = BLACK; // 根节点黑色
    }

    public void inOrder() {
        this.inOrder(root);
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node);
        inOrder(node.right);
    }
}


class Node {
    final boolean RED = true;
    final boolean BLACK = false;
    int key;
    boolean color;
    Node left, right, parent;

    public Node(int key) {
        this.key = key;
        this.color = RED;
    }

    @Override
    public String toString() {
        String str = "[";
        if (this.color == RED) {
            str += "红色";
        } else {
            str += "黑色";
        }
        return str + "," + this.key + "]";
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。