红黑树概念
红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它在每个节点上增加了一个颜色属性（红色或黑色），并通过一组精巧的颜色约束和旋转操作，确保树在动态插入、删除的过程中始终保持“近似平衡”。这种近似平衡使得红黑树的查找、插入、删除操作在最坏情况下的时间复杂度都能稳定在 O(log n)，同时其维护成本又低于严格平衡的 AVL 树。因此，红黑树是工程界应用最广泛的平衡二叉查找树之一，Java 的 TreeMap、HashMap 中的树化桶、C++ STL 的 map/set、Linux 内核的调度器与内存管理等都大量使用了红黑树。
一、为什么需要红黑树
在红黑树出现之前，二叉查找树（Binary Search Tree，BST）已经能够提供平均 O(log n) 的查找效率。但普通 BST 有一个致命缺陷：当插入的数据有序时，树会退化成一条链表，查找复杂度恶化到 O(n)。例如，依次插入 1, 2, 3, 4, 5，得到的树就是一条向右的链。为了解决这个问题，人们发明了自平衡二叉查找树，其中最著名的就是 AVL 树。
AVL 树要求任意节点的左右子树高度差绝对值不超过 1，这是一种非常严格的平衡。严格平衡带来了极快的查找速度，但也导致插入和删除时维护成本很高。尤其
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/qq_41663505/article/details/164884667
