红黑树的C++实现

红黑树核心概念解析

红黑树 是一种特殊的 二叉搜索树 ，其特点在于 每个节点中额外增加了一个用于标识颜色的存储单元，该颜色可为 Red（红色） 或 Black（黑色）。通过 对所有从根节点至叶节点路径上的节点颜色分配进行约束，红黑树能够保证 任意路径的长度不会超过其他路径长度的两倍 ，从而实现 结构近似平衡 的特性。（关于平衡的定义，可参考 AVL 树，这是一种高度平衡的二叉搜索树，其左右子树的高度差被严格限制在 1 以内）

图表展示与分析

引发的疑问：

如何确保任意路径的长度不会超过其他路径两倍以上？只要符合红黑树的基本特性，就能够实现这一目标。

红黑树核心性质解析

1. 每一个节点均被赋予红色或黑色属性
2. 树结构的起始节点必须为黑色
3. ** 当某节点呈现红色时，其子节点必须为黑色（这意味着树中不会出现相邻的两个红色节点）**
4. **针对任意一个节点，从该节点至其所有后代的空节点所形成的路径中，***黑色节点的数量保持一致