J. 红黑树（6）插入III

J. 红黑树（6）插入III

更新日期：2022-11-06

---

这一小节是代码示例。我将先演示关键性的代码，然后再给出一个完整的可执行的代码例子。

1. 关键代码(Java)

这一小节中演示了元素插入的关键代码。其中由于移动节点部分的四段代码具有相似性，所以这里又进一步的合并为两类，也就是一般教程中提到的【左旋转】和【右旋转】。

• 左旋转会把节点往左侧移动
• 右旋转会把节点往右侧移动

关键代码

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

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

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

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

    // 调整节点
    protected void _reBlance(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();
            // 将爷爷节点设为当前节点，进入下一轮调整
            _reBlance(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);
                // 将原父节点设定为当前节点，进入下一轮调整
                _reBlance(parent);
                // 调整结束
                return;
            }
            // 情形3-2-3：右左
            if (node == parent.right && parent == grand.left) {

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

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

    // 右旋转
    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;
    }

2. 完整的可执行代码(Java)

RedBlackTree.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(877);
        tree.add(648);
        tree.add(346);
        tree.add(311);
        tree.add(395);
        tree.add(610);
        tree.add(837);
        tree.add(689);
        tree.add(887);
        tree.add(715);
        tree.add(993);
        tree.add(807);
        tree.add(994);
        tree.add(383);
        tree.add(37);
        tree.add(290);
        tree.add(902);
        tree.add(798);
        tree.add(945);
        tree.add(451);


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

    // 根节点
    protected Node root;

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

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

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

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

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

        System.out.println("bt.add(" + e + ");");

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

    // 调整节点
    protected void _reBlance(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();
            // 将爷爷节点设为当前节点，进入下一轮调整
            _reBlance(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);
                // 将原父节点设定为当前节点，进入下一轮调整
                _reBlance(parent);
                // 调整结束
                return;
            }
            // 情形3-2-3：右左
            if (node == parent.right && parent == grand.left) {

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

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

    // 右旋转
    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 == n.parent.left) return n.parent.right;
        return n.parent.left;
    }

    //***************************二叉树的绘制*****************************
    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;
            }
        }
    }
}