L. 红黑树（8）删除II

L. 红黑树（8）删除II

更新日期：2022-11-14

---

废话不多说，直接放代码了。这里的代码是红黑树的完整版代码，里面包括了：

• 红黑树的绘制
• 红黑树的插入
• 红黑树的删除

总算是在1000行之内完成了。

红黑树的删除（Java）

package org.example.redblacktree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 红黑树
public class RedBlackTree {

    // 节点颜色
    public static final int RED = 0;
    public static final int BLACK = 1;

    static RedBlackTree tree = new RedBlackTree();

    // 测试代码
    public static void main(String[] args) {

        // 插入20个随机节点
        tree.add(138);
        tree.add(866);
        tree.add(222);
        tree.add(106);
        tree.add(872);
        tree.add(38);
        tree.add(631);
        tree.add(443);
        tree.add(388);
        tree.add(899);
        tree.add(755);
        tree.add(40);
        tree.add(352);
        tree.add(235);
        tree.add(470);
        tree.add(497);
        tree.add(290);
        tree.add(793);
        tree.add(693);
        tree.add(306);

        // 打印结果
        tree.print();

        // 依次移除所有端点
        tree.remove(138);
        tree.remove(866);
        tree.remove(222);
        tree.remove(106);
        tree.remove(872);
        tree.remove(38);
        tree.remove(631);
        tree.remove(443);
        tree.remove(388);
        tree.remove(899);
        tree.remove(755);
        tree.remove(40);
        tree.remove(352);
        tree.remove(235);
        tree.remove(470);
        tree.remove(497);
        tree.remove(290);
        tree.remove(793);
        tree.remove(693);
        tree.remove(306);
    }

    // 根节点
    protected Node root;

    // 添加元素
    public void add(int e) {

        // 使用普通排序二叉树的规则插入元素
        Node newNode = addNormal(e);
        if (newNode == null) {
            return;
        }

        // 将新节点设定为红色
        newNode.color = RED;

        // 将新节点设定为当前节点，并开始进行调整
        _reBlanceA(newNode);
    }

    // 删除元素
    public void remove(int e) {

        System.out.println("移除节点：" + e);

        // 寻找要删除的节点
        Node n = searchNode(e);
        if (n == null) return;

        // 进入调整Z(删除节点：无条件)
        _reBlanceZ(n);

        // 打印结果
        tree.print();
    }

    // 添加元素
    protected Node addNormal(int e) {

        System.out.println("添加节点：" + e);

        // 没有根节点
        if (root == null) {
            root = createNewNode(e);
            return root;
        } else {
            return _add(root, e);
        }
    }

    // 调整A(插入节点)
    protected void _reBlanceA(Node node) {

        // 情形1：当前节点没有父节点
        if (node.parent == null) {
            // 把新节点颜色改为黑色
            node.color = BLACK;
            // 已经平衡，调整结束
            return;
        }

        // 情形2：当前节点的父节点为黑色
        if (node.parent.color == BLACK) {
            // 已经平衡，调整结束
            return;
        }

        // 情形3：当前节点的父节点为红色
        // 代码走到这里时已经满足此条件了

        // 提前取好常用节点
        Node parent = node.parent;
        Node uncle = getBrother(parent);
        Node grand = parent.parent;

        // 情形3-1：叔叔节点存在，且为红色
        if (uncle != null && uncle.color == RED) {

            // 将爷爷、父亲和叔叔节点反色
            grand.reverseColor();
            parent.reverseColor();
            uncle.reverseColor();
            // 将爷爷节点设为当前节点，进入下一轮调整
            _reBlanceA(grand);
            // 调整结束
            return;

        // 情形3-2：叔叔节点不存在，或者为黑色
        } else {
            // 情形3-2-1：左左
            if (node == parent.left && parent == grand.left) {

                // 右旋转
                turnRight(parent);
                // 将新的父节点和右子节点反色
                parent.reverseColor();
                grand.reverseColor();
                // 已经平衡，调整结束
                return;
            }
            // 情形3-2-2：左右
            if (node == parent.left && parent == grand.right) {

                // 右旋转
                turnRight(node);
                // 将原父节点设定为当前节点，进入下一轮调整
                _reBlanceA(parent);
                // 调整结束
                return;
            }
            // 情形3-2-3：右左
            if (node == parent.right && parent == grand.left) {

                // 左旋转
                turnLeft(node);
                // 将原父节点设定为当前节点，进入下一轮调整
                _reBlanceA(parent);
                // 调整结束
                return;
            }
            // 情形3-2-4：右右
            if (node == parent.right && parent == grand.right) {

                // 左旋转
                turnLeft(parent);
                // 将新的父节点和左子节点反色
                parent.reverseColor();
                grand.reverseColor();
                // 已经平衡，调整结束
                return;
            }
        }
    }

    // 调整Z(删除节点：无条件)
    protected void _reBlanceZ(Node n) {

        // 取得节点的关联节点
        Node parent = n.parent;
        Node brother = getBrother(n);

        // 取得当前节点的子节点数量
        int subCnt = getSubCount(n);

        // 当前节点没有子节点
        if (subCnt == 0) {
            // 当前节点为红色节点
            if (n.color == RED) {
                // 直接删除当前节点
                removeNode(n);
                // 调整完毕
                return;
            // 当前节点为黑色节点
            } else {
                // 父节点不存在
                if (parent == null) {
                    // 直接删除当前节点(变为空树）
                    removeNode(n);
                    // 调整完毕
                    return;
                }
                // 父节点为红色
                if (parent.color == RED) {
                    // 兄弟节点必为黑色
                    int subCntOfBrother = getSubCount(brother);
                    // 兄弟节点没有子节点
                    if (subCntOfBrother == 0) {
                        // 直接删除当前节点
                        removeNode(n);
                        // 将父节点置为黑色，兄弟节点置为红色
                        parent.color = BLACK;
                        brother.color = RED;
                        // 调整完毕
                        return;
                    // 兄弟节点有子节点
                    } else {
                        // 当前节点为左子节点，兄弟节点有左子节点
                        if (n == parent.left && brother.left != null) {
                            // 直接删除当前节点
                            removeNode(n);
                            // 将兄弟节点的左子节点上提 X 2
                            Node x = brother.left;
                            takeUp(x);
                            takeUp(x);
                            // 将同一个节点的左子节点置为黑色
                            x.left.color = BLACK;
                            // 调整完毕
                            return;
                        // 当前节点为右子节点，兄弟节点有右子节点
                        } else if (n == parent.right && brother.right != null) {
                            // 直接删除当前节点
                            removeNode(n);
                            // 将兄弟节点的右子节点上提 X 2
                            Node x = brother.right;
                            takeUp(x);
                            takeUp(x);
                            // 将同一个节点的右子节点置为黑色
                            x.right.color = BLACK;
                            // 调整完毕
                            return;
                        // 上记以外
                        } else {
                            // 直接删除当前节点
                            removeNode(n);                          
                            // 将兄弟节点上提
                            takeUp(brother);
                            // 调整完毕
                            return;
                        }
                    }
                // 父节点为黑色
                } else {
                    // 兄弟节点为红色
                    if (brother.color == RED) {
                        // 将兄弟节点上提
                        takeUp(brother);
                        // 将兄弟节点和父节点反色
                        brother.reverseColor();
                        parent.reverseColor();
                        // 进入下一次调整Z(删除节点：无条件)
                        _reBlanceZ(n);
                    // 兄弟节点为黑色
                    } else {
                        // 调整X(删除节点：当前节点没有子节点，当前节点、父节点和兄弟节点都为黑色)
                        _reBlanceX(n);
                    }
                }
            }
        // 当前节点有一个子节点
        } else if (subCnt == 1) {
            Node sub = n.left != null ? n.left : n.right;
            // 当前节点必为黑色节点
            // 子节点必为红色节点
            // 将子节点上提
            takeUp(sub);
            // 删去当前节点
            removeNode(n);
            // 将剩下的子节点置为黑色
            sub.color = BLACK;
            // 调整完毕
            return;
        // 当前节点有两个子节点
        } else {
            // 寻找左子树中最大的节点
            Node maxNode = findMax(n.left);
            // 替换当前节点和此最大节点(包括颜色）
            replaceNode(n, maxNode);
            Node nodeTemp = n;
            n = maxNode;
            maxNode = nodeTemp;
            // 进入下一次调整Z(删除节点：无条件)
            _reBlanceZ(n);
        }
    }

    // 调整X(删除节点：当前节点没有子节点，当前节点、父节点和兄弟节点都为黑色)
    protected void _reBlanceX(Node n) {

        // 取得节点的关联节点
        Node parent = n.parent;
        Node brother = getBrother(n);

        // 取得兄弟节点的子节点数量
        int subCntOfBrother = getSubCount(brother);

        // 兄弟节点没有子节点
        if (subCntOfBrother == 0) {
            // 直接删除当前节点
            removeNode(n);
            // 将兄弟节点置为红色
            brother.color = RED;
            // 以父节点为当前节点进入下一次调整
            // 进入下一次调整Y(升级调整：当前分支黑色层级少一级)
            _reBlanceY(parent);
        // 兄弟节点有子节点
        } else {
            // 当前节点为左子节点，兄弟节点有左子节点
            if (n == parent.left && brother.left != null) {
                // 直接删除当前节点
                removeNode(n);
                // 将兄弟节点的左子节点上提 X 2
                Node x = brother.left;
                takeUp(x);
                takeUp(x);
                // 将同一个节点置为黑色
                x.color = BLACK;
                // 调整完毕
                return;
            // 当前节点为右子节点，兄弟节点有右子节点
            } else if (n == parent.right && brother.right != null) {
                // 直接删除当前节点
                removeNode(n);
                // 将兄弟节点的右子节点上提 X 2
                Node x = brother.right;
                takeUp(x);
                takeUp(x);
                // 将同一个节点置为黑色
                x.color = BLACK;
                // 调整完毕
                return;
            // 上记以外
            } else {
                // 直接删除当前节点
                removeNode(n);
                // 将兄弟节点上提
                takeUp(brother);
                // 将兄弟节点的子节点置为黑色
                if (brother.left != null) brother.left.color = BLACK;
                if (brother.right != null) brother.right.color = BLACK;
                // 调整完毕
                return;
            }
        }
    }

    // 调整Y(升级调整：当前分支黑色层级少一级)
    protected void _reBlanceY(Node n) {

        // 取得节点的关联节点
        Node parent = n.parent;

        // 当前节点没有父节点
        if (parent == null) {
            // 当前节点为根节点，调整完毕
            return;
        // 当前节点有父节点
        } else {
            Node brother = getBrother(n);
            // 父节点、兄弟节点、兄弟节点的两个子节点都为黑色
            if (parent.color == BLACK && brother.color == BLACK &&
                    brother.left.color == BLACK && brother.right.color == BLACK) {
                // 将兄弟节点设定为红色
                brother.color = RED;
                // 以父节点为当前节点进入下一次调整Y(升级调整：当前分支黑色层级少一级)
                _reBlanceY(parent);
            // 上记以外
            } else {
                // 将兄弟节点上提
                takeUp(brother);

                // 重新取得关联节点
                parent = n.parent;
                brother = getBrother(n);
                Node grand = n.parent.parent;

                // 父节点红，爷爷节点为黑
                if (parent.color == RED && grand.color == BLACK) {
                    // 如果兄弟节点为黑
                    if (brother.color == BLACK) {
                        // 已经平衡，调整完毕
                        return;
                        // 如果兄弟节点为红
                    } else {
                        // 以兄弟节点为当前节点调用插入时的调整函数 进入下一次调整A(插入节点)
                        _reBlanceA(brother);
                    }
                    // 父节点黑，爷爷节点为红
                } else if (parent.color == BLACK && grand.color == RED) {
                    // 兄弟节点一定为黑
                    // 将父亲节点设定为红
                    parent.color = RED;
                    // 将爷爷节点设定为黑
                    grand.color = BLACK;
                    // 将以兄弟节点上提
                    takeUp(brother);
                    // 重新取得兄弟节点
                    brother = getBrother(n);
                    // 兄弟节点为黑色
                    if (brother.color == BLACK) {
                        // 调整完毕
                        return;
                    // 兄弟节点为红色
                    } else {
                        // 以兄弟节点为当前节点进入下一次调整A(插入节点)
                        _reBlanceA(brother);
                    }
                // 父节点黑，爷爷节点黑
                } else {
                    Node uncle = getBrother(parent);
                    // 叔叔节点为红
                    if (uncle.color == RED) {
                        // 将叔叔节点置为黑色
                        uncle.color = BLACK;
                        // 调整完毕
                        return;
                        // 叔叔节点为黑
                    } else {
                        // 兄弟节点为黑
                        if (brother.color == BLACK) {
                            // 将父节点置为红色
                            parent.color = RED;
                            // 以爷爷为当前节点调入下一次调整
                            // 进入下一次调整Y(升级调整：当前分支黑色层级少一级)
                            _reBlanceY(grand);
                            // 兄弟节点为红
                        } else {
                            // 将兄弟节点上提 X 2
                            takeUp(brother);
                            takeUp(brother);
                            // 将此节点设定为黑色
                            brother.color = BLACK;
                            // 调整完毕
                            return;
                        }
                    }
                }
            }
        }
    }

    // 删除当前节点
    protected void removeNode(Node n) {

        Node parent = n.parent;
        // 如果是根节点则直接删除
        if (parent == null) {
            root = null;

        // 如果不是根节点，则将此子树从整棵树中移除
        } else {
            if (parent.left == n) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
    }

    // 替换节点
    protected void replaceNode(Node x, Node y) {

        // 交换节点内容
        int valueTemp = x.value;
        x.value = y.value;
        y.value = valueTemp;
    }

    // 将节点上提
    protected void takeUp(Node n) {

        // 如果节点为左子节点就右旋转
        if (n == n.parent.left) {
            turnRight(n);
        // 如果节点为右子节点就左旋转
        } else {
            turnLeft(n);
        }
    }

    // 右旋转
    protected void turnRight(Node n) {

        Node parent = n.parent;
        Node grand = parent.parent;

        // 将节点n拎起来
        if (grand == null) root = n;
        else if (grand.left == parent) grand.left = n;
        else grand.right = n;
        n.parent = grand;
        // 将节点n的右子节点给父亲当左子节点
        parent.left = n.right;
        if (n.right != null) n.right.parent = parent;
        // 将父亲节点变为右子节点
        n.right = parent;
        parent.parent = n;
    }

    // 左旋转
    protected void turnLeft(Node n) {

        Node parent = n.parent;
        Node grand = parent.parent;

        // 将节点n拎起来
        if (grand == null) root = n;
        else if (grand.left == parent) grand.left = n;
        else grand.right = n;
        n.parent = grand;
        // 将节点n的左子节点给父亲当右子节点
        parent.right = n.left;
        if (n.left != null) n.left.parent = parent;
        // 将父亲节点变为左子节点
        n.left = parent;
        parent.parent = n;
    }

    // 创建新节点
    protected Node createNewNode(int e) {
        return new Node(e);
    }

    // 寻找最大节点
    protected Node findMax(Node n) {
        if (n == null) return null;
        if (n.right == null) return n;
        return findMax(n.right);
    }

    // 添加元素
    private Node _add(Node n, int e) {

        if (e == n.value) {
            System.out.println("元素已经存在，忽略本次插入");
            return null;
        } else if (e < n.value) {
            // 添加到左子树中
            if (n.left == null) {
                n.left = createNewNode(e);
                n.left.parent = n;
                return n.left;
            } else {
                return _add(n.left, e);
            }
        } else {
            // 添加到右子树中
            if (n.right == null) {
                n.right = createNewNode(e);
                n.right.parent = n;
                return n.right;
            } else {
                return _add(n.right, e);
            }
        }
    }

    // 查找指定值的节点
    protected Node searchNode(int e) {
        return _searchNode(root, e);
    }
    private Node _searchNode(Node n, int e) {
        // 元素不存在
        if (n == null) return null;

        // 递归查找
        if (e == n.value) return n;
        else if (e < n.value) return _searchNode(n.left, e);
        else return _searchNode(n.right, e);
    }

    // 取得兄弟节点
    protected Node getBrother(Node n) {
        if (n.parent == null) return null;
        if (n == n.parent.left) return n.parent.right;
        return n.parent.left;
    }

    // 取得指定节点的子节点数量
    protected int getSubCount(Node n) {
        int cnt = 0;
        if (n.left != null) cnt++;
        if (n.right != null) cnt++;
        return cnt;
    }

    //***************************二叉树的绘制*****************************
    private static final String LINE_CROSS = "┴";
    private static final String LINE_CROSS_LEFT = "┘";
    private static final String LINE_CROSS_RIGHT = "└";
    private static final String LINE_H = "─";
    private static final String LINE_V = "│";
    private static final String LINE_TURN_LEFT = "┌";
    private static final String LINE_TURN_RIGHT = "┐";
    // 绘制二叉树
    public void print() {
        List<String> drawStrs = getDrawStrings();

        for (String drawStr : drawStrs) {
            System.out.println(drawStr);
        }
    }

    // 取得二叉树绘制字符串
    public List<String> getDrawStrings() {
        List<String> rsts = new ArrayList<>();
        if (root == null) {
            rsts.add("■■空树■■");
            return rsts;
        }

        // 绘制以根节点为首的树
        List<String> treeStrs = _getDrawStrings(root);
        // 绘制根节点的值
        int crossLocation = findCrossLocation(treeStrs);
        String rootV = copyStringByCnt(" ", crossLocation) + root.toString();
        rsts.add(rootV);
        rsts.addAll(treeStrs);
        // 将结果集的所有行都补充到同一长度
        putInSpace(rsts);

        return rsts;
    }
    private List<String> _getDrawStrings(Node n) {

        List<String> rsts = new ArrayList<>();

        if (n == null) return rsts;
        if (n.left == null && n.right == null) return rsts;

        // *************绘制出各个部分*********
        // 本体
        List<String> nodeItself = drawNodeItself(n);
        // 左分支
        List<String> leftNode = _getDrawStrings(n.left);
        // 右分支
        List<String> rightNode = _getDrawStrings(n.right);

        // 拼接各个部分
        // 给本体补充左边分支的部分，以使本体的左节点与左分支的交叉点对齐
        if (leftNode.size() > 0) {
            int crossLocation = findCrossLocation(leftNode);
            insertBlankToLeft(nodeItself, crossLocation);
        }
        // 如果左右分支都有内容，则填充为同一大小
        if (leftNode.size() > 0 && rightNode.size() > 0) {
            int maxSize = Math.max(leftNode.size(), rightNode.size());
            insertBlankToDown(leftNode, maxSize - leftNode.size());
            insertBlankToDown(rightNode, maxSize - rightNode.size());
        }
        // 如果有右分支，则给右分支左边添加空白，以使本体的右节点与右分支的交叉点对齐
        if (rightNode.size() > 0) {
            int rl = findRightCrossLocation(nodeItself);
            int lw = (leftNode.size() > 0) ? leftNode.get(0).length() : 0;
            int rCrossLocation = findCrossLocation(rightNode);
            int blankW = rl - lw - rCrossLocation;
            insertBlankToLeft(rightNode, blankW);
        }
        // 将左右分支拼接在一起
        List<String> nodeStrs = combineNodeStrs(leftNode, rightNode);
        // 将所有行添加到结果中
        rsts.addAll(nodeItself);
        rsts.addAll(nodeStrs);
        // 将结果集的所有行都补充到同一长度
        putInSpace(rsts);

        return rsts;
    }

    // 将左右分支拼接在一起
    private List<String> combineNodeStrs(List<String> leftNode, List<String> rightNode) {

        if (leftNode.size() == 0) return rightNode;
        if (rightNode.size() == 0) return  leftNode;

        List<String> rsts = new ArrayList<>();
        for (int i = 0; i < leftNode.size(); i++) {
            rsts.add(leftNode.get(i) + rightNode.get(i));
        }

        return rsts;
    }

    // 查找右交叉点的位置
    private int findRightCrossLocation(List<String> strs) {
        return strs.get(0).indexOf(LINE_TURN_RIGHT);
    }

    // 在下面插入空白行
    private void insertBlankToDown(List<String> strs, int h) {
        int w = strs.get(0).length();
        String blank = copyStringByCnt(" ", w);
        for (int i = 0; i < h; i++) {
            strs.add(blank);
        }
    }

    // 在左边插入空白
    private void insertBlankToLeft(List<String> strs, int w) {
        String blank = copyStringByCnt(" ", w);
        for (int i = 0; i < strs.size(); i++) {
            String line = blank + strs.get(i);
            strs.set(i, line);
        }
    }

    // 查找交叉点的位置
    private int findCrossLocation(List<String> nodeStrs) {

        if (nodeStrs.isEmpty()) return 0;

        String firstLine = nodeStrs.get(0);
        return Math.max(
                firstLine.indexOf(LINE_CROSS),
                Math.max(
                        firstLine.indexOf(LINE_CROSS_LEFT),
                        firstLine.indexOf(LINE_CROSS_RIGHT)));
    }

    // 绘制节点本体
    private List<String> drawNodeItself(Node n) {

        List<String> rsts = new ArrayList<>();

        // 计算左右节点的树枝长度
        int lw = calcBrunchLen(n.left);
        int rw = calcBrunchLen(n.right);

        // 横线行
        {
            String line = "";
            // 左分支
            if (lw > 0) {
                line += LINE_TURN_LEFT + copyStringByCnt(LINE_H, lw);
            }
            // 交叉点
            String cross = LINE_CROSS;
            if (lw == 0) cross = LINE_CROSS_RIGHT;
            if (rw == 0) cross = LINE_CROSS_LEFT;
            line += cross;
            // 右分支
            if (rw > 0) {
                line += copyStringByCnt(LINE_H, rw) + LINE_TURN_RIGHT;
            }
            rsts.add(line);
        }
        // 两个竖线行
        {
            String line = "";
            if (lw > 0) line += LINE_V;
            line +=  copyStringByCnt(" ", lw + rw + 1);
            if (rw > 0) line += LINE_V;
            rsts.add(line);
            rsts.add(line);
        }
        // 值行
        {
            String line = "";
            // 左值
            if (lw > 0) {
                line += n.left.toString();
            }
            // 空白
            if (rw > 0) {
                int ww = 0;
                if (lw > 0) ww += lw + 1;
                ww += rw + 1;

                line += copyStringByCnt(" ", ww - line.length());
            }
            // 右值
            if (rw > 0) {
                line += n.right.toString();
            }
            rsts.add(line);
        }

        // 补充空格直至所有行的长度一致
        putInSpace(rsts);

        return rsts;
    }

    // 补充空格直至所有行的长度一致
    private void putInSpace(List<String> strs) {

        // 求得最大长度
        int max = 0;
        for (String str : strs) {
            if (str.length() > max) {
                max = str.length();
            }
        }

        // 将所有行补充到最大长度
        for (int i = 0; i < strs.size(); i++) {
            String str = strs.get(i);
            str += copyStringByCnt(" ", max - str.length());
            strs.set(i, str);
        }
    }

    // 重复一个字符串指定次数
    private String copyStringByCnt(String str, int cnt) {
        return String.join("", Collections.nCopies(cnt, str));
    }

    // 计算节点的树枝长度
    private int calcBrunchLen(Node n) {
        // 计算节点深度
        int dep = getNodeDepth(n);

        if (dep == 0) return 0;

        // 根据深度映射出树枝长度
        return (int)Math.pow(2, (dep + 2) * 1);
    }

    // 计算节点深度
    private int getNodeDepth(Node n) {
        if (n == null) return 0;

        int leftDep = getNodeDepth(n.left);
        int rightDep = getNodeDepth(n.right);

        return Math.max(leftDep, rightDep) + 1;
    }
    //***************************二叉树的绘制*****************************

    // 节点定义
    protected class Node {

        // 节点的值
        protected int value;
        // 父节点
        protected Node parent;
        // 左右子树
        protected Node left, right;
        // 颜色(0：红色，1：黑色)
        protected int color;

        public Node(int e) {
            value = e;
        }

        // 绘制节点
        public String toString() {
            // 绘制红色节点
            if (color == RED) {

                return "□" + String.valueOf(value);

            // 绘制黑色节点
            } else {

                return "■" + String.valueOf(value);
            }
        }

        // 反色
        public void reverseColor() {
            if (color == RED) {
                color = BLACK;
            } else {
                color = RED;
            }
        }
    }
}