数据结构与算法-12高级数据结构_树论（红黑树）

🕗 发布于 2024-07-21 01:41 数据结构

红黑树

1 红黑树-简介

1.1 定义

定义：红黑树是一种每个节点都带有颜色属性的二叉查找树，节点颜色为红色或黑色。
发明：红黑树由Rudolf Bayer在1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），后由Guibas和Robert Sedgewick修改为现今的“红黑树”。

1.2 基本性质

节点颜色：每个节点是红色或黑色。
根节点颜色：根节点是黑色。
叶子节点：叶子节点（NIL节点，空节点）是黑色。
红色节点：如果一个节点是红色的，则它的两个子节点都是黑色的（这保证了路径上不会有两个连续的红色节点）。
黑色节点路径：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树保证了在最坏情况下的基本操作（查找、插入、删除）的时间复杂度为O(log n)，其中n是树中元素的数目。这是因为红黑树的性质确保了树的高度不会过高，从而保证了操作的效率。

1.3 插入节点的步骤

查找插入位置
- 对红黑树进行二分查找，直到找到新节点的插入位置（即红黑树的叶子节点）。
插入节点并设为红色
- 将新节点插入到找到的位置，并将节点颜色设为红色。
调整红黑树以恢复性质
- 如果新节点是根节点
  - 直接将新节点颜色改为黑色，因为根节点必须是黑色的。
- 如果新节点的父节点是黑色
  - 不需要进行任何调整，因为新节点的插入没有违反红黑树的性质。
- 如果新节点的父节点是红色
  - 叔叔节点也是红色
    - 将父节点和叔叔节点都设置为黑色。
    - 将祖父节点设置为红色。
    - 将祖父节点视为新的插入节点，递归进行上述检查。
    - 在这里插入图片描述
  - 叔叔节点是黑色
    - 左左插入（新节点在父节点的左子树，且父节点在祖父节点的左子树）
      - 将父节点设置为黑色。
      - 将祖父节点设置为红色。
      - 对祖父节点进行右旋。
    - 左右插入（新节点在父节点的右子树，且父节点在祖父节点的左子树）
      - 对父节点进行左旋，这样原来的父节点就变成了新节点的子节点，且新节点成为了其父节点的左子节点。
      - 按照左左插入的情况处理新的父子关系。
    - 右右插入（新节点在父节点的右子树，且父节点在祖父节点的右子树）
      - 这是左左插入的镜像情况，处理方式相同，但方向相反（即将父节点设为黑色，祖父节点设为红色，并对祖父节点进行左旋）。
    - 右左插入（新节点在父节点的左子树，且父节点在祖父节点的右子树）
      - 对父节点进行右旋，这样原来的父节点就变成了新节点的子节点，且新节点成为了其父节点的右子节点。
      - 按照右右插入的情况处理新的父子关系。

1.4 删除节点的步骤

一、总体流程

在删除节点时，需依次查看删除节点的颜色、兄弟节点的颜色、侄子节点的颜色（先远侄子，再近侄子），最后是父节点的颜色。

顺序为：当前节点->兄弟节点->远侄子节点->近侄子节点->父节点。

（补充说明：删除节点分为叶子节点和非叶子节点两种情况。若为非叶子节点，则先与子节点的值进行交换，直至转化为删除叶子节点的情况。）

二、具体情况分析

删除的是叶子节点且为红色
- 可直接删除，无需后续处理。
删除的是叶子节点且为黑色
- 需进一步处理。
删除节点下有一个子节点
- 将当前删除的节点与子节点的值进行交换，从而转化为删除叶子节点的情况。
  - 3.1 若转化后的叶子节点为红色，对应情况 1，直接删除。
  - 3.2 若转化后的叶子节点为黑色，对应情况 2，进行后续处理。
删除节点有两个子节点
- 将当前节点与后续节点中的一个节点值进行交换，转变为删除叶子节点的情况。
  - 4.1 若转变后没有叶子节点，对应情况 1 或 2。
  - 4.2 若转变后有一个叶子节点，对应情况 3。
  - 4.3 若转变后有两个叶子节点，对应情况 4。

经过上述步骤的转换，情况已转化为删除叶子节点。其中叶子节点为红色的情况已处理完毕，接下来重点关注删除叶子节点为黑色的情形。

删除的叶子节点为黑色
5.1 删除节点的兄弟节点为红色
- 若删除节点为左节点：将父节点和兄弟节点颜色互换，然后对父节点进行左旋。
- 若删除节点为右节点：将父节点和兄弟节点颜色互换，然后对父节点进行右旋。
5.2 删除节点兄弟节点为黑色，远侄子节点为红色
- 若删除节点为左节点：此时删除节点的远侄子节点为兄弟节点的右节点。将父节点和兄弟节点颜色对调，并把远侄子节点变成黑色，接着对父节点进行左旋，最后删除当前需要删除的节点。
- 若删除节点为右节点：此时删除节点的远侄子节点为兄弟节点的左节点。将父节点和兄弟节点颜色对调，并把远侄子节点变成黑色，接着对父节点进行右旋，最后删除当前需要删除的节点。
5.3 删除节点兄弟节点是黑色，近侄子节点是红色
- 若删除节点为左节点：近侄子节点和兄弟节点颜色互换，并将近侄子节点进行右旋，此时转变为 5.2 情况。
- 若删除节点为右节点：近侄子节点和兄弟节点颜色互换，将近侄子节点进行左旋，此时转变为 5.2 情况。
5.4 父节点是红色，兄弟节点和兄弟节点的两个孩子（只能是空节点）都是黑色的情况
- 将父节点变成黑色，兄弟节点变成红色，然后删除当前节点。
5.5 父节点和兄弟节点及兄弟节点的两个子节点，都是黑色
- 将兄弟节点变成红色，删除节点。这样删除节点后，父节点的左右两个黑色节点数相等，但经过祖父节点的路径黑色节点数少 1 个。此时，以父节点为起始节点（无需再处理原删除节点），继续根据上述情况进行平衡操作，判断所属情况并做相应调整，如此一直向上，直至新的起始节点为根节点。

2 红黑树代码示例

2.1 插入

核心代码

/**
     * 新增节点
     * @param data
     */
    public void addNode(Integer data) {
        MyRedBlackTreeNode<Integer> node = new MyRedBlackTreeNode<>(data);
        addNode(root,node);
        fixTree(node); // 核心方法，用于调整红黑树
    }

    /**
     * 新增节点：递归函数
     * @param root
     * @param node
     */
    private void addNode(MyRedBlackTreeNode<Integer> root, MyRedBlackTreeNode<Integer> node) {
        if (node.data <= root.data){
            if (root.left == null){
                root.left = node;
                node.parent = root;
            }else{
                addNode(root.left, node);
            }
        } else {
            if (root.right == null){
                root.right = node;
                node.parent = root;
            }else{
                addNode(root.right, node);
            }
        }
    }

    /**
     * 红黑树调整
     * @param node
     */
    private void fixTree(MyRedBlackTreeNode<Integer> node) {
        // 第一种情况：node节点作为根节点，将当前节点修改为黑色
        // 第二种情况：node节点的父节点为黑色节点，不需要做调整
        if (node.parent == null || node.parent.color == MyRedBlackTreeNode.BLACK) {
            return;
        }
        while (node.parent != null && node.parent.color == MyRedBlackTreeNode.RED){
            if (node.parent.parent == null){
                node.parent.color = MyRedBlackTreeNode.BLACK;
                continue;
            }
            // 第三种情况：node节点的父节点为红色
            if (node.parent.parent.left == node.parent){ // 父节点在祖父节点的左子树
                MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.right; // 获取到叔叔节点
                // 3.1 叔叔节点为红色
                // - 将父节点和叔叔节点都设置为黑色。
                //- 将祖父节点设置为红色。
                //- 将祖父节点视为新的插入节点，递归进行上述检查。
                if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
                    node.parent.color = MyRedBlackTreeNode.BLACK;
                    uncleNode.color = MyRedBlackTreeNode.BLACK;
                    node.parent.parent.color = MyRedBlackTreeNode.RED;
                    node = node.parent.parent;
                    continue;
                }
                // 3.2 叔叔节点为黑色
                // 3.2.2 新节点在父节点的右子树，且父节点在祖父节点的左子树
                // - 对父节点进行左旋，这样原来的父节点就变成了新节点的子节点，且新节点成为了其父节点的左子节点。
                // - 按照左左插入的情况处理新的父子关系。
                if (node.parent.right == node){
                    node = node.parent;
                    leftRotate(node);
                }
                // 3.2.1 新节点在父节点的左子树，且父节点在祖父节点的左子树
                // - 将父节点设置为黑色。
                //- 将祖父节点设置为红色。
                //- 对祖父节点进行右旋。
                node.parent.color = MyRedBlackTreeNode.BLACK;
                node.parent.parent.color = MyRedBlackTreeNode.RED;
                rightRotate(node.parent.parent);
            } else if (node.parent.parent.right == node.parent) { // 父节点在祖父节点的右子树
                MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.left; // 获取到叔叔节点
                // 3.1 叔叔节点为红色
                // - 将父节点和叔叔节点都设置为黑色。
                //- 将祖父节点设置为红色。
                //- 将祖父节点视为新的插入节点，递归进行上述检查。
                if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
                    node.parent.color = MyRedBlackTreeNode.BLACK;
                    uncleNode.color = MyRedBlackTreeNode.BLACK;
                    node.parent.parent.color = MyRedBlackTreeNode.RED;
                    node = node.parent.parent;
                    continue;
                }
                // 3.2 叔叔节点为黑色
                // 3.2.4 新节点在父节点的右子树，且父节点在祖父节点的左子树
                if (node.parent.left == node){
                    node = node.parent;
                    rightRotate(node);
                }
                // 3.2.3 新节点在父节点的左子树，且父节点在祖父节点的右子树
                // 父节点设为黑色，祖父节点设为红色，并对祖父节点进行左旋
                node.parent.color = MyRedBlackTreeNode.BLACK;
                node.parent.parent.color = MyRedBlackTreeNode.RED;
                leftRotate(node.parent.parent);
            }
        }
        root.color = MyRedBlackTreeNode.BLACK;
    }

完整代码

/**
 * 红黑树
 */
public class MyRedBlackTreeDemo {
    private MyRedBlackTreeNode<Integer> root;

    public MyRedBlackTreeDemo(Integer data) {
        root = new MyRedBlackTreeNode<>(data);
        root.setColor(MyRedBlackTreeNode.BLACK); // 根节点为黑色
    }

    /**
     * 新增节点
     * @param data
     */
    public void addNode(Integer data) {
        MyRedBlackTreeNode<Integer> node = new MyRedBlackTreeNode<>(data);
        addNode(root,node);
        fixTree(node); // 核心方法，用于调整红黑树
    }

    /**
     * 新增节点：递归函数
     * @param root
     * @param node
     */
    private void addNode(MyRedBlackTreeNode<Integer> root, MyRedBlackTreeNode<Integer> node) {
        if (node.data <= root.data){
            if (root.left == null){
                root.left = node;
                node.parent = root;
            }else{
                addNode(root.left, node);
            }
        } else {
            if (root.right == null){
                root.right = node;
                node.parent = root;
            }else{
                addNode(root.right, node);
            }
        }
    }

    /**
     * 红黑树调整
     * @param node
     */
    private void fixTree(MyRedBlackTreeNode<Integer> node) {
        // 第一种情况：node节点作为根节点，将当前节点修改为黑色
        // 第二种情况：node节点的父节点为黑色节点，不需要做调整
        if (node.parent == null || node.parent.color == MyRedBlackTreeNode.BLACK) {
            return;
        }
        while (node.parent != null && node.parent.color == MyRedBlackTreeNode.RED){
            if (node.parent.parent == null){
                node.parent.color = MyRedBlackTreeNode.BLACK;
                continue;
            }
            // 第三种情况：node节点的父节点为红色
            if (node.parent.parent.left == node.parent){ // 父节点在祖父节点的左子树
                MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.right; // 获取到叔叔节点
                // 3.1 叔叔节点为红色
                // - 将父节点和叔叔节点都设置为黑色。
                //- 将祖父节点设置为红色。
                //- 将祖父节点视为新的插入节点，递归进行上述检查。
                if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
                    node.parent.color = MyRedBlackTreeNode.BLACK;
                    uncleNode.color = MyRedBlackTreeNode.BLACK;
                    node.parent.parent.color = MyRedBlackTreeNode.RED;
                    node = node.parent.parent;
                    continue;
                }
                // 3.2 叔叔节点为黑色
                // 3.2.2 新节点在父节点的右子树，且父节点在祖父节点的左子树
                // - 对父节点进行左旋，这样原来的父节点就变成了新节点的子节点，且新节点成为了其父节点的左子节点。
                // - 按照左左插入的情况处理新的父子关系。
                if (node.parent.right == node){
                    node = node.parent;
                    leftRotate(node);
                }
                // 3.2.1 新节点在父节点的左子树，且父节点在祖父节点的左子树
                // - 将父节点设置为黑色。
                //- 将祖父节点设置为红色。
                //- 对祖父节点进行右旋。
                node.parent.color = MyRedBlackTreeNode.BLACK;
                node.parent.parent.color = MyRedBlackTreeNode.RED;
                rightRotate(node.parent.parent);
            } else if (node.parent.parent.right == node.parent) { // 父节点在祖父节点的右子树
                MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.left; // 获取到叔叔节点
                // 3.1 叔叔节点为红色
                // - 将父节点和叔叔节点都设置为黑色。
                //- 将祖父节点设置为红色。
                //- 将祖父节点视为新的插入节点，递归进行上述检查。
                if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
                    node.parent.color = MyRedBlackTreeNode.BLACK;
                    uncleNode.color = MyRedBlackTreeNode.BLACK;
                    node.parent.parent.color = MyRedBlackTreeNode.RED;
                    node = node.parent.parent;
                    continue;
                }
                // 3.2 叔叔节点为黑色
                // 3.2.4 新节点在父节点的右子树，且父节点在祖父节点的左子树
                if (node.parent.left == node){
                    node = node.parent;
                    rightRotate(node);
                }
                // 3.2.3 新节点在父节点的左子树，且父节点在祖父节点的右子树
                // 父节点设为黑色，祖父节点设为红色，并对祖父节点进行左旋
                node.parent.color = MyRedBlackTreeNode.BLACK;
                node.parent.parent.color = MyRedBlackTreeNode.RED;
                leftRotate(node.parent.parent);
            }
        }
        root.color = MyRedBlackTreeNode.BLACK;
    }

    /**
     * 左旋
     * @param node
     * @return
     */
    private MyRedBlackTreeNode<Integer> leftRotate(MyRedBlackTreeNode<Integer> node) {
        if (node == null || node.right == null){
            return node;
        }
        MyRedBlackTreeNode<Integer> rightNode = node.right;
        node.right = rightNode.left;
        if (rightNode.left != null){
            rightNode.left.parent = node;
        }
        rightNode.parent = node.parent;
        if (node.parent != null && node.parent.left == node){
            node.parent.left = rightNode;
        } else if (node.parent != null && node.parent.right == node) {
            node.parent.right = rightNode;
        }else{
            root = rightNode;
        }
        node.parent = rightNode;
        rightNode.left = node;

        return rightNode;
    }

    /**
     * 右旋
     * @param node
     * @return
     */
    private MyRedBlackTreeNode<Integer> rightRotate(MyRedBlackTreeNode<Integer> node) {
        if (node == null || node.left == null){
            return node;
        }
        MyRedBlackTreeNode<Integer> leftNode = node.left;
        node.left = leftNode.right;
        if (leftNode.right != null){
            leftNode.right.parent = node;
        }
        leftNode.parent = node.parent;
        if (node.parent != null && node.parent.left == node){
            node.parent.left = leftNode;
        } else if (node.parent != null && node.parent.right == node) {
            node.parent.right = leftNode;
        }else{
            root = leftNode;
        }
        node.parent = leftNode;
        leftNode.right = node;
        return leftNode;
    }

    /**
     * 展示树的结构
     * @param node
     * @return
     */
    public void show() {
        if (root == null) {
            System.out.println("EMPTY!");
            return ;
        }
        // 得到树的深度
        int treeDepth = getHeight(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }

    /**
     * 获取树的高度
     * @param node
     * @return
     */
    private int getHeight(MyRedBlackTreeNode<Integer> node) {
        if (node == null){
            return 0;
        }
        // 递归求取当前节点的最大的高度
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    /**
     * 将节点的值写入到二维数组中
     * @param node
     * @param rowIndex
     * @param columnIndex
     * @param res
     * @param treeDepth
     */
    private void writeArray(MyRedBlackTreeNode<Integer> currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null)
            return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.data+"["+(currNode.color == MyRedBlackTreeNode.BLACK ? "B" : "R")+"]");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth)
            return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }
}

2.2 测试&结果

public class MyRedBlackTreeTest {
    public static void main(String[] args) {
        MyRedBlackTreeDemo tree = new MyRedBlackTreeDemo(10);
        tree.addNode(5);
        tree.addNode(15);
        tree.addNode(2);
        tree.addNode(7);
        tree.show();
        System.out.println("--------------------------------------");
        tree.addNode(8);
        tree.show();
        System.out.println("--------------------------------------");
        tree.addNode(9);
        tree.show();
        System.out.println("--------------------------------------");
        tree.addNode(6);
        tree.show();
    }
}

结果

      10[R]    
    /   \    
  5[B]    15[B]
 / \         
2[R]7[R]     
--------------------------------------
            10[B]          
         /     \         
      5[R]        15[B]    
    /   \                
  2[B]    7[B]           
           \             
            8[R]         
--------------------------------------
            10[B]          
         /     \         
      5[R]        15[B]    
    /   \                
  2[B]    8[B]           
         / \             
        7[R]9[R]         
--------------------------------------
            8[B]         
         /     \         
      5[R]        10[R]    
    /   \       /   \    
  2[B]    7[B]9[B]    15[B]
         /               
        6[R]

原文地址：https://blog.csdn.net/qq_40469712/article/details/140553953

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【golang-ent】go-zero框架整合 ent orm框架 | 解决left join未关联报错的问题
下一篇：Redis的计数功能

推荐系统与大模型
目前大模型在推荐系统取得巨大进展的同时也上主要一些的问题。主要有以下三点。1. Position Bias.在推荐系统的生成语言建模范式中，用户行为序列和推荐候选序列等各种信息以文本序列描述的形式输入
阅读更多2024-11-19
element-ui】使用el_upload上传文件无法动态修改action
问题：最近在使用el_upload上传文件时，发现无法动态修改action的值，进行提交时，caseId2还是默认值null。原因：el-upload的先执行上传，后执行action里的响应，也就是赋
阅读更多2024-11-19
JavaScript 如何获取本机IP地址
获取本机IP地址是前端工程师经常需要处理的问题。JavaScript 有几种方法可以获取客户端的IP地址。下面是三种获取本机IP的方法。
阅读更多2024-11-19
如何用 JavaScript 复制到剪贴板
以上就是几种在 JavaScript 中实现文本复制到剪贴板的方法。随着技术的发展，建议尽量使用最新的异步剪贴板 API，但为了兼容性，可以结合使用方法。希望本文能够帮助你更好地理解和应用这些 API
阅读更多2024-11-19
【第29章】MyBatis-Plus之分页插件
的分页插件提供了强大的分页功能，支持多种数据库，使得分页查询变得简单高效。属性名类型默认值描述overflowbooleanfalse溢出总页数后是否进行处理maxLimitLong单页分页条数限制d
阅读更多2024-11-19
weixin-java-miniapp 微信小程序登陆
1. 用户在小程序中选择使用微信授权登录功能。2. 小程序调用 `` 接口，向发起登录请求。3. 微信服务器验证小程序的合法性，如果合法，会返回一个。4. 小程序。5. 后台服务器接收到 **code
阅读更多2024-11-19
都2023年了，Servlet还有必要学习吗？一文带你快速了解Servlet
不得不说，Servlet 确实是一门古老的技术了，现在很少有公司直接使用 Servlet 来写项目了，大家都在用 SpringMVC-Spring-MyBatis / SpringBoot 做开发了，
阅读更多2024-11-19
掌握Java中集合的交集与并集操作
本文还有配套的精品资源，点击获取简介：集合操作是编程中的基础任务，涉及找出多个集合的共有元素（交集）和所有不同元素的总和（并集）。本文介绍如何在Java中利用 HashSet 和 St
阅读更多2024-11-19
Java 环境配置——Java 语言的安装、配置、编译与运行
正确配置 Java 开发环境是进行 Java 开发的第一步。通过本文的详细介绍，读者应能够在不同操作系统上安装和配置 JDK，并熟练编写、编译和运行 Java 程序。随着技术的发展，Java 生态系统
阅读更多2024-11-19
java 配置多数据源
mysql和clickhouse多数据源配置。
阅读更多2024-11-19