红黑树（Red-Black Tree）：原理、常见算法及其应用

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它的设计目的是为了在最坏的情况下保证查找、插入和删除操作的时间复杂度为 O(logn)。红黑树通过特定的颜色标记和旋转操作来维持树的近似平衡，从而确保了高效的性能表现。本文将从红黑树的基本概念出发，逐步介绍其原理、常见算法，并通过具体的Java代码示例来加深理解，最后探讨红黑树在算法中的实际应用场景，并总结对比红黑树与平衡二叉树（如AVL树）的优势。

红黑树的基本概念

红黑树是一种特殊的二叉查找树，其特点在于通过颜色标记来保持树的平衡性。每个节点都被标记为红色或黑色，并遵循以下规则：

根节点是黑色。
每个叶子节点（NIL节点）都是黑色。
没有相邻的两个红色节点（即任何一个红色节点的父节点和子节点必须是黑色）。
从任一节点到达其每个叶子节点的所有路径上黑色节点的数量相同（称为黑高）。

这些规则确保了红黑树的高度不会超过 2log2(n+1)，其中 n 是树中的节点数。

节点定义

class RedBlackTreeNode {
    int val;
    boolean color; // true for red, false for black
    RedBlackTreeNode left;
    RedBlackTreeNode right;
    RedBlackTreeNode parent;

    RedBlackTreeNode(int x) {
        val = x;
        color = true; // New nodes are initially red
        left = null;
        right = null;
        parent = null;
    }
}

常见算法

插入节点

插入新节点时，需要先按照二叉查找树的方式找到合适的位置，然后进行必要的旋转和重新着色操作以恢复红黑树的平衡性。

Java代码实现

public class RedBlackTree {
    private RedBlackTreeNode root;
    private RedBlackTreeNode nil;

    public RedBlackTree() {
        nil = new RedBlackTreeNode(Integer.MIN_VALUE);
        nil.color = false; // Black
        root = nil;
    }

    // 插入节点
    public void insert(int value) {
        RedBlackTreeNode newNode = new RedBlackTreeNode(value);
        RedBlackTreeNode y = nil;
        RedBlackTreeNode x = root;

        while (x != nil) {
            y = x;
            if (newNode.val < x.val) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        newNode.parent = y;
        if (y == nil) {
            root = newNode;
        } else if (newNode.val < y.val) {
            y.left = newNode;
        } else {
            y.right = newNode;
        }

        newNode.left = nil;
        newNode.right = nil;
        newNode.color = true; // New node is red

        // Balance the tree
        insertFixup(newNode);
    }

    private void insertFixup(RedBlackTreeNode z) {
        while (z.parent.color == true) {
            if (z.parent == z.parent.parent.left) {
                RedBlackTreeNode y = z.parent.parent.right;
                if (y.color == true) { // Case 1
                    z.parent.color = false;
                    y.color = false;
                    z.parent.parent.color = true;
                    z = z.parent.parent;
                } else { // Case 2
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }
                    // Case 3
                    z.parent.color = false;
                    z.parent.parent.color = true;
                    rightRotate(z.parent.parent);
                }
            } else { // Symmetric to the above code
                RedBlackTreeNode y = z.parent.parent.left;
                if (y.color == true) {
                    z.parent.color = false;
                    y.color = false;
                    z.parent.parent.color = true;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }
                    z.parent.color = false;
                    z.parent.parent.color = true;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.color = false; // Root is always black
    }

    // 左旋
    private void leftRotate(RedBlackTreeNode x) {
        RedBlackTreeNode y = x.right;
        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == nil) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋
    private void rightRotate(RedBlackTreeNode y) {
        RedBlackTreeNode x = y.left;
        y.left = x.right;
        if (x.right != nil) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == nil) {
            root = x;
        } else if (y == y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        x.right = y;
        y.parent = x;
    }
}

示例：插入关键字序列 (16, 3, 7, 11, 9, 26, 18, 14, 15)

public static void main(String[] args) {
    RedBlackTree rbTree = new RedBlackTree();

    // 插入关键字序列
    rbTree.insert(16);
    rbTree.insert(3);
    rbTree.insert(7);
    rbTree.insert(11);
    rbTree.insert(9);
    rbTree.insert(26);
    rbTree.insert(18);
    rbTree.insert(14);
    rbTree.insert(15);

    // 打印树的节点
    rbTree.printTree(rbTree.root);
}

查找节点

查找特定值的节点时，从根节点开始，根据值与当前节点值的关系决定向左还是向右。

Java代码实现

public RedBlackTreeNode search(int value) {
    return searchRecursive(root, value);
}

private RedBlackTreeNode searchRecursive(RedBlackTreeNode current, int value) {
    if (current == nil) {
        return nil;
    }

    if (value == current.val) {
        return current;
    }

    return value < current.val
            ? searchRecursive(current.left, value)
            : searchRecursive(current.right, value);
}

删除节点

删除节点时需要考虑三种情况：

节点是叶子节点。
节点有一个子节点。
节点有两个子节点。

Java代码实现

public void delete(int value) {
    RedBlackTreeNode z = search(value);
    if (z == nil) {
        return; // Value not found
    }
    deleteNode(z);
}

private void deleteNode(RedBlackTreeNode z) {
    RedBlackTreeNode y = z;
    boolean yOriginalColor = y.color;
    RedBlackTreeNode x = nil;

    if (z.left == nil) {
        x = z.right;
        transplant(z, z.right);
    } else if (z.right == nil) {
        x = z.left;
        transplant(z, z.left);
    } else {
        y = minimum(z.right);
        yOriginalColor = y.color;
        x = y.right;
        if (y.parent == z) {
            x.parent = y;
        } else {
            transplant(y, y.right);
            y.right = z.right;
            y.right.parent = y;
        }
        transplant(z, y);
        y.left = z.left;
        y.left.parent = y;
        y.color = z.color;
    }
    if (yOriginalColor == false) {
        deleteFixup(x);
    }
}

private void deleteFixup(RedBlackTreeNode x) {
    while (x != root && x.color == false) {
        if (x == x.parent.left) {
            RedBlackTreeNode s = x.parent.right;
            if (s.color == true) { // Case 1
                s.color = false;
                x.parent.color = true;
                leftRotate(x.parent);
                s = x.parent.right;
            }
            if (s.left.color == false && s.right.color == false) { // Case 2
                s.color = true;
                x = x.parent;
            } else {
                if (s.right.color == false) { // Case 3
                    s.left.color = false;
                    s.color = true;
                    rightRotate(s);
                    s = x.parent.right;
                }
                // Case 4
                s.color = x.parent.color;
                x.parent.color = false;
                s.right.color = false;
                leftRotate(x.parent);
                x = root;
            }
        } else { // Symmetric to the above code
            RedBlackTreeNode s = x.parent.left;
            if (s.color == true) { // Case 1
                s.color = false;
                x.parent.color = true;
                rightRotate(x.parent);
                s = x.parent.left;
            }
            if (s.right.color == false && s.left.color == false) { // Case 2
                s.color = true;
                x = x.parent;
            } else {
                if (s.left.color == false) { // Case 3
                    s.right.color = false;
                    s.color = true;
                    leftRotate(s);
                    s = x.parent.left;
                }
                // Case 4
                s.color = x.parent.color;
                x.parent.color = false;
                s.left.color = false;
                rightRotate(x.parent);
                x = root;
            }
        }
    }
    x.color = false;
}

private void transplant(RedBlackTreeNode u, RedBlackTreeNode v) {
    if (u.parent == nil) {
        root = v;
    } else if (u == u.parent.left) {
        u.parent.left = v;
    } else {
        u.parent.right = v;
    }
    v.parent = u.parent;
}

private RedBlackTreeNode minimum(RedBlackTreeNode x) {
    while (x.left != nil) {
        x = x.left;
    }
    return x;
}

private void printTree(RedBlackTreeNode node) {
    if (node != nil) {
        printTree(node.left);
        System.out.print("Value: " + node.val + " Color: " + (node.color ? "Red" : "Black") + "\n");
        printTree(node.right);
    }
}

红黑树的应用场景

1. 数据库索引

红黑树可以用于构建数据库的索引，以加速查询速度。

应用原理

数据库记录的键值存储在红黑树的节点中。
查询时，根据键值在树中查找对应的记录。
插入和删除记录时，自动调整树的平衡，保持较低的高度。

场景描述

在数据库管理系统中，索引是提高查询效率的重要手段之一。当数据库需要频繁地按某个字段进行查询时，可以创建基于该字段的红黑树索引。这样，在执行查询操作时，可以迅速定位到指定键值所在的记录，而不需要全表扫描。红黑树的自平衡特性确保了索引结构的高效性，即使在频繁的插入和删除操作下也能保持良好的性能。

2. 符号表

在编程语言的编译器中，符号表用于跟踪变量声明和类型信息。

应用原理

变量名称作为键值存储在红黑树中。
变量的类型和其他相关信息作为键值对应的数据存储。
编译器在处理源代码时，需要维护一个符号表来跟踪所有的变量声明及其属性。

场景描述

编译器在处理源代码时，需要维护一个符号表来跟踪所有的变量声明及其属性。红黑树可以有效地管理这些信息，因为编译器可以根据变量名称快速查找、插入或更新相应的信息。这有助于编译器在编译过程中进行类型检查和其他优化工作。红黑树的自平衡特性使得符号表能够在处理大型代码库时依然保持高效。

3. 动态集合

红黑树可以用于实现动态集合，支持动态添加、删除元素并保持有序。

应用原理

集合中的元素作为键值存储在红黑树中。
插入新元素时，保持树的有序性。
删除元素时，调整树以保持红黑树的性质。

场景描述

在需要动态管理一组有序元素的应用场景中，如任务队列或优先级队列，红黑树可以有效地支持元素的插入、删除操作，同时保持集合的有序性。这使得在处理动态变化的数据集合时更加高效和灵活。红黑树的自平衡特性使得动态集合在频繁的操作下依然保持良好的性能。

总结

红黑树作为一种高效的数据结构，在计算机科学中有广泛的应用。通过特定的颜色标记和旋转操作来保持树的近似平衡，红黑树在最坏的情况下也能够保证操作的时间复杂度为 �(log⁡�)O(logn)。掌握红黑树的概念和相关算法对于深入理解计算机科学的核心知识至关重要。

以下是总结对比红黑树与平衡二叉树（如AVL树）的优势：

优势对比

自平衡条件

红黑树：允许一定程度的高度不平衡，只要满足红黑树的五条规则即可。
AVL树：严格限制左右子树的高度差不超过1，这使得AVL树的高度始终接近最优。

旋转次数

红黑树：在插入或删除节点时，需要进行的旋转次数通常少于AVL树。
AVL树：为了保持严格的平衡条件，AVL树在插入或删除节点时需要频繁地进行旋转。

操作效率

红黑树：由于旋转次数较少，红黑树在频繁的插入和删除操作下整体性能通常优于AVL树。
AVL树：虽然AVL树的高度更低，但由于频繁的旋转，整体性能在某些情况下可能不如红黑树。

应用场景

红黑树：因其较宽松的平衡条件，适用于更多需要自平衡特性的场景，如数据库索引、操作系统调度等。
AVL树：适用于需要严格平衡条件的应用场景，如某些特定的数值计算领域。

实现复杂度

红黑树：相比AVL树，红黑树的实现相对简单，更容易理解和实现。
AVL树：AVL树的实现较为复杂，需要处理更多的情况来保持严格的平衡条件。

综上所述，红黑树以其较高的灵活性、较低的旋转次数以及更简单的实现方式，在许多实际应用中表现出色。然而，AVL树在某些特定的应用场景下仍然具有其独特的优势。选择哪种数据结构取决于具体的应用需求和性能要求。

原文地址：https://blog.csdn.net/weixin_43841461/article/details/142497560

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

上一篇：R&S FSW43 信号与频谱分析仪
下一篇：权限维持——Linux

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

红黑树（Red-Black Tree）：原理、常见算法及其应用

引言

红黑树的基本概念

常见算法

插入节点

查找节点

删除节点

红黑树的应用场景

1. 数据库索引

2. 符号表

3. 动态集合

总结

优势对比

自平衡条件

旋转次数

操作效率

应用场景

实现复杂度

相关文章