本文摘要：红黑树是一种自平衡的排序二叉树，其核心特性体现在五个性质上：所有节点按红色或黑色严格划分；根节点固定为黑色；空叶子节点亦为黑色；若节点为红色，则其子节点必为黑色，以此确保相邻节点不出现双红现象；任意节点到其所有后代叶节点路径上的黑节点数目相等。这些性质使得红黑树在进行插入和删除操作时能保持近似平衡，从而在包括Java的TreeSet、TreeMap以及C++ STL中的map与set等广泛应用中，能够实现O(log n)复杂度的关键字查找与管理。

转载文章

本篇文章为转载内容。原文链接：https://blog.csdn.net/u012017783/article/details/80562092。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

一、定义
这里写图片描述
红黑树的五个性质：
一般的，红黑树(一棵自平衡的排序二叉树)，满足以下性质，即只有满足以下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

抓住了红黑树的那5个性质，分开记忆。
如，
1.红黑红黑，要么是红，要么是黑；
2.根结点是黑；
3.每个叶结点是黑；
4.一个红结点，它的俩个儿子必然都是黑的；
5.每一条路径上，黑结点的数目等同。
五条性质，合起来，来句顺口溜就是：（1）红黑（2）黑（3）黑（4&5）红->黑黑
二、运用场景
java中的TreeSet,TreeMap，广泛用在C++的STL中。如map和set都是用红黑树实现的

本篇文章为转载内容。原文链接：https://blog.csdn.net/u012017783/article/details/80562092。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

名词解释

作为当前文章的名词解释，仅对当前文章有效。

红黑树：红黑树是一种自平衡的二叉查找树，其每个节点都具有红色或黑色属性。在满足特定规则（如文中所述五个性质）的情况下，这种数据结构能够确保任何插入、删除操作后，树的高度始终保持在O(log n)级别，从而保证了在大规模数据中进行搜索、插入和删除等基本操作时的时间效率。具体性质包括但不限于。

自平衡排序二叉树：自平衡排序二叉树是一种特殊的二叉查找树，其设计目标是在执行插入和删除操作之后，能自动调整自身的结构以保持树的高度平衡，进而确保关键操作（如查找、插入、删除）的最坏时间复杂度维持在O(log n)水平。红黑树就是一种自平衡排序二叉树的具体实现，通过定义并强制维护一系列严格的颜色与结构性质来达到这一目标。

树叶节点（NIL节点）：在红黑树的数据结构中，树叶节点（NIL节点）是一个特指的概念，它代表的是不存在实际数据的空节点，通常用作树的边界条件，同时也是实现红黑树性质的关键组成部分。在红黑树中，所有的树叶节点都被标记为黑色，这是红黑树第五个性质的一部分，即从任一节点到其所有后代叶节点的所有路径上的黑节点数量相等。

C++ STL：Standard Template Library（标准模板库），是C++编程语言中的一种强大的软件工具集，提供了许多预定义的数据结构（如容器类vector、list、set、map等）以及算法（如排序、查找等）。在STL中，map和set两种容器正是基于红黑树实现的，它们利用红黑树的特性，实现了键值对的高效存储和检索，使得插入、删除和查找操作的时间复杂度接近于O(log n)。

TreeSet/TreeMap（Java集合框架）：在Java集合框架中，TreeSet和TreeMap分别实现了有序的元素集合和键值映射关系，底层采用的就是红黑树这一数据结构。TreeSet保证了元素按照自然顺序或者自定义比较器排序；而TreeMap则根据键的自然顺序或定制的比较器对键值对进行排序。这两种数据结构同样利用红黑树的自平衡特性，在进行增删改查操作时保持了较高的性能。