红黑树

特性

红黑树核心法则

1. 每个节点要么是红色，要么是黑色
2. 根节点【NULL】必须是黑色
3. 节点是红色不能连续（如果节点是红色 ，孩子必须是黑色）
4. 从任意节点出发到其 NULL 节点的简单路径上都包含相同数目的黑色节点
5. 每个红色节点的两个子节点一定都是黑色（叶子节点包含NULL）

红黑树结构

红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）
一颗树黑色高度为 3 的红黑树，从根结点到叶结点：

• 最短路径长度是 2 (黑-黑-黑)
• 最长路径为 4 (黑-红-黑-红-黑)

红黑树中最长路径就是一条红黑交替的路径，从根结点到叶结点的简单路径的最短长度为n-1，最大长度为2(n-1)

操作流程

插入节点

主要步骤

1. 插入节点且将颜色染成红色
2. 重新染色 且进行 旋转，修复

插入情况

1、父节点为空
当插入节点为父节点时，则将当前节点染为黑色
2、父节点为黑色
当插入节点的父节点为黑色，则什么都不用做
3、父节点为红色 且 叔叔节点为红色

1. 将父节点染黑
2. 将叔叔节点染黑
3. 将祖父节点染红
4. 从祖父节点继续递归

4、父节点为红色 且 叔叔节点为黑色（或不存在）
这种情况下 cur 一般不是刚插入进来的节点，而是又 黑 变 红，当它的两个子节点为 红 时，新增一个 孙 节点时，它就会发现这样的变色，所以在旋转之后，cur 下方依旧存在 黑 节点，所以这棵树还是平衡的

1. 左左——右单旋

2. 右右——左单旋

3. 左右——左右双旋

4. 右左——右左双旋

删除节点

所有情况：

1. 删除的是叶子节点（下面又分2种情况）
   1. 删除节点的颜色是红色
   2. 删除节点的颜色是黑色（下面再分5种情况）
      1. 兄弟节点没有左右孩子
      2. 兄弟节点左孩子为红色，右孩子为黑色
      3. 兄弟节点右孩子为红色，左孩子为黑色
      4. 兄弟节点有左右孩子，且都为红色
      5. 兄弟节点有左右孩子，且都为黑色（兄弟节点为红色）
2. 删除的只有左子节点，没有右子节点
3. 删除的只有右子节点，没有左子节点
4. 删除的既有左子节点，又有右子节点

删除的是叶子节点

1. 删除节点的颜色是红色：直接删除，因为删除掉红色节点不会影响到红黑树的基本特性

2. 兄弟节点没有左右孩子

3. 兄弟节点左孩子为红色，右孩子为黑色（或为空）

4. 兄弟节点右孩子为红色，左孩子为黑色（或为空）

5. 兄弟节点有左右孩子，且都为红色

6. 兄弟节点有左右孩子，且都为黑色（兄弟节点为红色）

删除的只有左子节点，没有右子节点

删除的只有右子节点，没有左子节点

删除的既有左子节点，又有右子节点

1. 寻找替代节点
2. 与替代节点的 key 和 value 互换
3. 删除替代节点
4. 问题转化为删除叶子节点

代码实现

成员变量

• int key : 关键字，用于比较大小
• Object value : 值
• TreeNode left : 左节点
• TreeNode right : 右节点
• Color color ：颜色，默认设置为红色
• TreeNode parent ：该节点的父亲节点

public class RedBlackTree { 

    enum Color { 
        RED,BLACK;
    } 

    private TreeNode root;

    private static class TreeNode { 
        int key;
        Object value;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        Color color = RED;

        //构造方法
        public TreeNode(int key, Object value) { 
            this.key = key;
            this.value = value;
        } 
    } 
} 

核心方法

1. 判断当前节点是否为左孩子节点

//判断是否为左孩子
 public boolean isLeftChild() { 
     return parent != null && parent.left == this;
 } 

2. 获取叔叔节点

 //获取叔叔节点
 public TreeNode uncle() { 
     if (this.parent == null || this.parent.parent == null) { 
         return null;
     } 
     if (this.isLeftChild()) { 
         return this.parent.parent.right;
     }  else { 
         return this.parent.parent.left;
     } 
 } 

3. 获取兄弟节点

 //获取兄弟节点
 public TreeNode brother() { 
     if (this.parent == null) { 
         return null;
     } 
     if (this.isLeftChild()) { 
         return this.parent.right;
     } else { 
         return this.parent.left;
     } 
 } 

4. 判断是否为红色节点

//判断是否为红色节点
private boolean isRed(TreeNode node) { 
    return node != null && node.color == RED;
} 

5. 判断是否为黑色节点

//判断是否为黑色节点
private  boolean isBlack(TreeNode node) { 
    return node == null || node.color == BLACK;
} 

旋转操作

1. 右旋

// 这里的 node 节点对应上图的 g
private void rightRotate(TreeNode node) { 
    TreeNode parent = node.parent;
    TreeNode nodeLeft = node.left;
    TreeNode nodeLeftRight = nodeLeft.right;
    if (nodeLeftRight != null) { 
        nodeLeftRight.parent = node;
    } 
    nodeLeft.right = node;
    nodeLeft.parent = parent;
    node.left = nodeLeftRight;
    node.parent = nodeLeft;
    if (parent == null) { 
        root = nodeLeft;
    }  else if (parent.left == node) { 
        parent.left = nodeLeft;
    } else { 
        parent.right = nodeLeft;
    } 

} 

2. 右旋

// 这里的 node 节点对应上图的 g
private void leftRotate(TreeNode node) { 
    TreeNode parent = node.parent;
    TreeNode nodeRight = node.right;
    TreeNode nodeRightLeft = nodeRight.left;
    if (nodeRightLeft != null) { 
        nodeRightLeft.parent = node;
    } 
    nodeRight.left = node;
    nodeRight.parent = parent;
    node.right = nodeRightLeft;
    node.parent = nodeRight;
    if (parent == null) { 
        root = nodeRight;
    }  else if (parent.left == node) { 
        parent.left = nodeRight;
    } else { 
        parent.right = nodeRight;
    } 
} 

插入节点

public void put (int key, Object value) { 
    // 搜索插入位置
    TreeNode p = root;
    TreeNode parent = null;
    while (p != null) { 
        parent = p;
        if (p.key > key) { 
            p = p.left;
        } else if (p.key < key) { 
            p = p.right;
        } else { 
            p.value = value;
            return;
        } 
    } 
    // 插入新节点
    TreeNode node = new TreeNode(key, value);
    if (parent == null) { 
        root = node;
    } else { 
        if (node.key > parent.key) { 
            parent.right = node;
        } else { 
            parent.left = node;
        } 
        node.parent = parent;
    } 
    // 可能会发生红红不平衡，则需要调整
    fixRedRed(node);

} 

/**
 * 调整红红不平衡
 */
private void fixRedRed(TreeNode node) { 
    // case1: 插入节点为根节点，将根节点变黑
    if(node == root) { 
        node.color = BLACK;
        return;
    } 
    if (isBlack(node.parent)) { 
        // case2:插入节点的父亲若为黑，树的红黑性质不变，无需调整
        return;
    } 
    // 插入节点的父亲为红色，触发红红相邻
    // case3:叔叔为红色
    TreeNode parent = node.parent;
    TreeNode grandparent = parent.parent;
    TreeNode uncle = node.uncle();
    if (isRed(uncle)) { 
        // 进行变色处理即可
        // 将其父亲、叔叔变为黑色，爷爷变为红色
        parent.color = BLACK;
        uncle.color = BLACK;
        grandparent.color = RED;
        // 若爷爷触发了红红，则继续递归调用该函数
        fixRedRed(grandparent);
        return;
    } 

    // case4:叔叔为黑色
    // 该父亲为左孩子，该插入点也为左孩子，右旋
    if (parent.isLeftChild() && node.isLeftChild()) { 
        // 先将父亲变为黑色、爷爷变为红色，再右旋转
        parent.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    } else if (parent.isLeftChild()) { 
        // 该插入节点为右孩子、该父亲为左孩子，则 先左旋 再 右旋
        leftRotate(parent);
        node.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    }  else if (!node.isLeftChild()) { 
        // 插入节点为右孩子、父亲节点也为右孩子，则 右旋
        parent.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);
    } else { 
        //插入节点为左孩子、父亲节点为右孩子，先右旋 再 左旋
        rightRotate(parent);
        node.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);

    } 
} 

删除节点

/**
 * 查找删除节点
 */
private TreeNode findDelete(int key) { 
    TreeNode p = root;
    while(p != null) { 
        if (p.key > key) { 
            p = p.left;
        }  else if (p.key < key) { 
            p = p.right;
        }  else { 
            return p;
        } 
    } 
    //若没有找到则返回null
    return null;
} 

/**
 * 查找剩余节点
 */
private TreeNode findReplaced(TreeNode deleted) { 
    //没有孩子的情况:
    if (deleted.left == null && deleted.right == null) { 
        return null;
    } 
    if (deleted.left == null) { 
        return deleted.right;
    } 
    if (deleted.right == null) { 
        return deleted.left;
    } 

    //有两个孩子的情况,找后继节点即可
    TreeNode p = deleted.right;
    while(p.left != null) { 
        p = p.left;
    } 
    return p;
} 

/**
 * 删除节点
 * 正常删除节点，遇到黑黑不平衡则需要进行调整
 */
public void remove(int key) { 
    TreeNode delete = findDelete(key);
    if (delete == null) { 
        return;
    } 
    doRemove(delete);
} 

private void doRemove(TreeNode deleted) { 
    TreeNode replaced = findReplaced(deleted);
    TreeNode parent = deleted.parent;
    //没有孩子的情况:
    if (replaced == null) { 
        //删除的节点为根节点情况下:
        if (deleted == root) { 
            root = null;
            return;
        } else { 
            if (isRed(deleted)) { 
                //无需任何操作
            } else { 
                //触发黑黑不平衡，需要进行复杂的操作
                fixBlackBlack(deleted);
            } 
            if (deleted.isLeftChild()) { 
                parent.left = null;
            } else { 
                parent.right = null;
            } 
            deleted.parent = null;
        } 
        return;
    } 
    //有一个孩子的情况
    if (deleted.left == null || deleted.right == null) { 
        if (deleted == root) { 
            root.key = replaced.key;
            root.value = replaced.value;
            root.left = root.right = null;
        } else { 
            if (deleted.isLeftChild()) { 
                parent.left = replaced;
            }  else { 
                parent.right = replaced;
            } 
            replaced.parent = parent;
            deleted.left = deleted.right = deleted.parent = null;

            if (isRed(replaced) && isBlack(deleted)) { 
                //却少一个黑色，则将替换的节点换为红色即可
                replaced.color = BLACK;
            } else { 
                //遇到黑黑不平衡情况，则需要进行复杂调整
                fixBlackBlack(replaced);
            } 
        } 
        return;
    } 
    //有两个孩子的情况,需要将用到李代桃僵技巧
    int key = deleted.key;
    deleted.key = replaced.key;
    replaced.key = key;

    Object value = deleted.value;
    deleted.value = replaced.value;
    replaced.value = value;
    doRemove(replaced);

} 

private void fixBlackBlack(TreeNode node) { 
    if (node == root) { 
        return;
    } 
    TreeNode parent = node.parent;
    TreeNode brother = node.brother();

    if (isRed(node.brother())) { 
        //先进行旋转调整，再换色暂时达到平衡
        if (brother.isLeftChild()) { 
            rightRotate(parent);
        } else { 
            leftRotate(parent);
        } 
        parent.color = RED;
        brother.color = BLACK;
        fixBlackBlack(node);
        return;
    } 
    //两个侄子都为黑色
    if (brother == null) { 
        fixBlackBlack(parent);
    } else { 
        //case 4 兄弟是黑色，两个侄子也是黑色
        if (isBlack(brother.left) && isBlack(brother.right)) { 
            brother.color = RED;
            if (isRed(parent)) { 
                parent.color = BLACK;
            } else { 
                fixBlackBlack(parent);
            } 
        } 

        //case 5 兄弟是黑色，侄子有红色
        else { 
            //其中某一个侄子不为黑色
            //兄弟为左孩子、侄子为左孩子，触发 ll
            if (brother.isLeftChild() && isRed(brother.left)) { 
                rightRotate(parent);
                brother.left.color = BLACK;
                brother.color = parent.color;
                parent.color = BLACK;
            }  else if (brother.isLeftChild() && isRed(brother.right)) { 
                //兄弟为左孩子、侄子为右孩子，先触发 lr
                //需要将 lr 转变为 ll 情况再处理
                brother.right.color = parent.color;
                leftRotate(brother);
                rightRotate(parent);
                parent.color = BLACK;
            }  else if ( !brother.isLeftChild() && isRed(brother.right)) { 
                //兄弟为右孩子，侄子为右孩子，触发 rr
                leftRotate(parent);
                brother.right.color = BLACK;
                brother.color = parent.color;
                parent.color = BLACK;
            } else { 
                //最后一种情况兄弟为右孩子、侄子为左孩子，触发 rl
                //需要将 rl 转变为 rr 情况再处理
                brother.left.color = parent.color;
                rightRotate(brother);
                leftRotate(parent);
                parent.color = BLACK;

            } 
        } 
    } 
} 

完整代码

import static TreeNode.RedBlackTree.Color.BLACK;
import static TreeNode.RedBlackTree.Color.RED;

public class RedBlackTree { 

    enum Color { 
        RED,BLACK;
    } 

    private TreeNode root;

    private static class TreeNode { 
        int key;
        Object value;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        Color color = RED;

        //构造方法
        public TreeNode(int key, Object value) { 
            this.key = key;
            this.value = value;
        } 

        public TreeNode(int key, Object value, TreeNode left, TreeNode right, TreeNode parent) { 
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        } 

        //判断是否为左孩子
         public boolean isLeftChild() { 
             return parent != null && parent.left == this;
         } 

         //获取叔叔节点
         public TreeNode uncle() { 
             if (this.parent == null || this.parent.parent == null) { 
                 return null;
             } 
             if (this.isLeftChild()) { 
                 return this.parent.parent.right;
             }  else { 
                 return this.parent.parent.left;
             } 
         } 

         //获取兄弟节点
         public TreeNode brother() { 
             if (this.parent == null) { 
                 return null;
             } 
             if (this.isLeftChild()) { 
                 return this.parent.right;
             } else { 
                 return this.parent.left;
             } 
         } 


    } 

    //判断是否为红色节点
    private boolean isRed(TreeNode node) { 
        return node != null && node.color == RED;
    } 

    //判断是否为黑色节点
    private  boolean isBlack(TreeNode node) { 
        return node == null || node.color == BLACK;
    } 

    //右旋
    //1.考虑旋转后节点的维护parent 2.重新与上一个节点建立联系
    private void rightRotate(TreeNode node) { 
        TreeNode parent = node.parent;
        TreeNode nodeLeft = node.left;
        TreeNode nodeLeftRight = nodeLeft.right;
        if (nodeLeftRight != null) { 
            nodeLeftRight.parent = node;
        } 
        nodeLeft.right = node;
        nodeLeft.parent = parent;
        node.left = nodeLeftRight;
        node.parent = nodeLeft;
        if (parent == null) { 
            root = nodeLeft;
        }  else if (parent.left == node) { 
            parent.left = nodeLeft;
        } else { 
            parent.right = nodeLeft;
        } 

    } 

    //左旋
    //1.考虑旋转后节点的维护parent 2.重新与上一个节点建立联系
    private void leftRotate(TreeNode node) { 
        TreeNode parent = node.parent;
        TreeNode nodeRight = node.right;
        TreeNode nodeRightLeft = nodeRight.left;
        if (nodeRightLeft != null) { 
            nodeRightLeft.parent = node;
        } 
        nodeRight.left = node;
        nodeRight.parent = parent;
        node.right = nodeRightLeft;
        node.parent = nodeRight;
        //2.重新与上一个节点建立联系
        if (parent == null) { 
            root = nodeRight;
        }  else if (parent.left == node) { 
            parent.left = nodeRight;
        } else { 
            parent.right = nodeRight;
        } 

    } 

    //更新、增添节点
    //正常更新、删除，遇到红红不平衡则需要进行调整
    public void put (int key, Object value) { 
        TreeNode p = root;
        TreeNode parent = null;
        while (p != null) { 
            parent = p;
            if (p.key > key) { 
                p = p.left;
            } else if (p.key < key) { 
                p = p.right;
            } else { 
                p.value = value;
                return;
            } 
        } 
        TreeNode node = new TreeNode(key,value);
        if (parent == null) { 
            root = node;
        } else { 
            if (node.key > parent.key) { 
                parent.right = node;

            } else { 
                parent.left = node;

            } 
            node.parent = parent;
        } 
        //可能会发生红红不平衡，则需要调整
        fixRedRed(node);

    } 
    //调整红红不平衡

    private void fixRedRed(TreeNode node) { 
        //case1: 插入节点为根节点，将根节点变黑
        if(node == root) { 
            node.color = BLACK;
            return;
        } 
        if (isBlack(node.parent)) { 
            //case2:插入节点的父亲若为黑，树的红黑性质不变，无需调整
            //无需调整
            return;
        } 
        // 插入节点的父亲为红色，触发红红相邻
        //case3:叔叔为红色
        TreeNode parent = node.parent;
        TreeNode grandparent = parent.parent;
        TreeNode uncle = node.uncle();
        if (isRed(uncle)) { 
            //进行变色处理即可
            //将其父亲、叔叔变为黑色，爷爷变为红色
            //若爷爷触发了红红，则继续递归调用该函数
            parent.color = BLACK;
            uncle.color = BLACK;
            grandparent.color = RED;
            fixRedRed(grandparent);
            return;
        } 

        //case4:叔叔为黑色
        //该父亲为左孩子，该插入点也为左孩子，则触发 ll
        if (parent.isLeftChild() && node.isLeftChild()) { 
            //先将父亲变为黑色、爷爷变为红色，再右旋转
            parent.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        } else if (parent.isLeftChild()) { 
            //该插入节点为右孩子、该父亲为左孩子，则触发 lr
            //先左旋变为 ll 情况
            leftRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        }  else if (!node.isLeftChild()) { 
            //插入节点为右孩子、父亲节点也为右孩子 rr
            parent.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        } else { 
            //插入节点为左孩子、父亲节点为右孩子 rl
            rightRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);

        } 
    } 

    //查找删除节点
    private TreeNode findDelete(int key) { 
        TreeNode p = root;
        while(p != null) { 
            if (p.key > key) { 
                p = p.left;
            }  else if (p.key < key) { 
                p = p.right;
            } else { 
                return p;
            } 
        } 
        //若没有找到则返回null
        return null;
    } 

    //查找剩余节点
    private TreeNode findReplaced(TreeNode deleted) { 
        //没有孩子的情况:
        if (deleted.left == null && deleted.right == null) { 
            return null;
        } 
        if (deleted.left == null) { 
            return deleted.right;
        } 
        if (deleted.right == null) { 
            return deleted.left;
        } 

        //有两个孩子的情况,找后继节点即可
        TreeNode p = deleted.right;
        while(p.left != null) { 
            p = p.left;
        } 
        return p;
    } 

    //删除节点
    //正常删除节点，遇到黑黑不平衡则需要进行调整
    public void remove(int key) { 
        TreeNode delete = findDelete(key);
        if (delete == null) { 
            return;
        } 
        doRemove(delete);

    } 

    private void doRemove(TreeNode deleted) { 
        TreeNode replaced = findReplaced(deleted);
        TreeNode parent = deleted.parent;
        //没有孩子的情况:
        if (replaced == null) { 
            //删除的节点为根节点情况下:
            if (deleted == root) { 
                root = null;
                return;
            } else { 
                if (isRed(deleted)) { 
                    //无需任何操作
                } else { 
                    //触发黑黑不平衡，需要进行复杂的操作
                    fixBlackBlack(deleted);
                } 
                if (deleted.isLeftChild()) { 
                    parent.left = null;
                } else { 
                    parent.right = null;
                } 
                deleted.parent = null;
            } 
            return;
        } 
        //有一个孩子的情况
        if (deleted.left == null || deleted.right == null) { 
            if (deleted == root) { 
                root.key = replaced.key;
                root.value = replaced.value;
                root.left = root.right = null;
            } else { 
                if (deleted.isLeftChild()) { 
                    parent.left = replaced;
                }  else { 
                    parent.right = replaced;
                } 
                replaced.parent = parent;
                deleted.left = deleted.right = deleted.parent = null;

                if (isRed(replaced) && isBlack(deleted)) { 
                    //却少一个黑色，则将替换的节点换为红色即可
                    replaced.color = BLACK;
                } else { 
                    //遇到黑黑不平衡情况，则需要进行复杂调整
                    fixBlackBlack(replaced);
                } 
            } 
            return;
        } 
        //有两个孩子的情况,需要将用到李代桃僵技巧
        int key = deleted.key;
        deleted.key = replaced.key;
        replaced.key = key;

        Object value = deleted.value;
        deleted.value = replaced.value;
        replaced.value = value;
        doRemove(replaced);

    } 
    private void fixBlackBlack(TreeNode node) { 
        if (node == root) { 
            return;
        } 
        TreeNode parent = node.parent;
        TreeNode brother = node.brother();

        if (isRed(node.brother())) { 
            //先进行旋转调整，再换色暂时达到平衡
            if (brother.isLeftChild()) { 
                rightRotate(parent);
            } else { 
                leftRotate(parent);
            } 
            parent.color = RED;
            brother.color = BLACK;
            fixBlackBlack(node);
            return;
        } 
        //两个侄子都为黑色
        if (brother == null) { 
            fixBlackBlack(parent);
        } else { 
            //case 4 兄弟是黑色，两个侄子也是黑色
            if (isBlack(brother.left) && isBlack(brother.right)) { 
                brother.color = RED;
                if (isRed(parent)) { 
                    parent.color = BLACK;
                } else { 
                    fixBlackBlack(parent);
                } 
            } 

            //case 5 兄弟是黑色，侄子有红色
            else { 
                //其中某一个侄子不为黑色
                //兄弟为左孩子、侄子为左孩子，触发 ll
                if (brother.isLeftChild() && isRed(brother.left)) { 
                    rightRotate(parent);
                    brother.left.color = BLACK;
                    brother.color = parent.color;
                    parent.color = BLACK;
                }  else if (brother.isLeftChild() && isRed(brother.right)) { 
                    //兄弟为左孩子、侄子为右孩子，先触发 lr
                    //需要将 lr 转变为 ll 情况再处理
                    brother.right.color = parent.color;
                    leftRotate(brother);
                    rightRotate(parent);
                    parent.color = BLACK;
                }  else if ( !brother.isLeftChild() && isRed(brother.right)) { 
                    //兄弟为右孩子，侄子为右孩子，触发 rr
                    leftRotate(parent);
                    brother.right.color = BLACK;
                    brother.color = parent.color;
                    parent.color = BLACK;
                } else { 
                    //最后一种情况兄弟为右孩子、侄子为左孩子，触发 rl
                    //需要将 rl 转变为 rr 情况再处理
                    brother.left.color = parent.color;
                    rightRotate(brother);
                    leftRotate(parent);
                    parent.color = BLACK;

                } 
            } 
        } 

    } 

} 

谢谢光临~

• 本文作者：晓江
• 本文链接：https://lxjblog.gitee.io/2024/06/18/%E7%BA%A2%E9%BB%91%E6%A0%91/
• 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。