简介
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（Symmetric Binary B-Trees），后来在1978年被Leo J. Guibas和Robert Sedgewick修改为如今的红黑树。
红黑树具有以下性质：
每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶节点（Nil或空值）都是黑色。
每个红色节点的两个子节点一定都是黑色（但黑色节点的子节点可以也是黑色）。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树的平衡性是通过上述性质来保证的，虽然它是弱平衡二叉树（左右子树高度差可能大于1，但不超过一倍），但在实践中是高效的。它可以在O(log n)时间内完成查找、插入和删除操作，其中n是树中元素的数目。
红黑树的应用广泛，其设计使得它在处理大量数据时能够保持相对稳定的性能，特别是在需要频繁进行插入、删除和查找操作的场景中。如需更深入地了解红黑树，建议查阅相关计算机科学或数据结构教材。
主要实现步骤
视频讲解： https://space.bilibili.com/518581788/channel/seriesdetail?sid=239783
代码实现： http://www.kittybunny.cn/2020/05/04/kitty/meow-kitty-red-blacktree/#