红黑树学

一、红黑树基础概念解析

1972年，Rudolf Bayer提出了平衡二叉B树（symmetric binary B-trees）这一数据结构。随后，在1978年，Leo J. Guibas与Robert Sedgewick对其进行了改进，并将其命名为“红黑树”。该结构属于AVL树的一种特殊形式，通过在插入与删除操作中执行特定的调整机制，能够维持二叉查找树的相对平衡状态，从而显著提升查找效率。

红黑树并不属于严格的AVL树范畴，其平衡特性仅体现在黑色节点的层次上，如上图所示，根节点P的左子树高度明显高于右子树，但左子树与右子树中黑色节点所处的层级数量保持一致。

二、红黑树核心特性解析

满足二叉搜索树基本属性的同时，还具有以下特征：

1. 每个节点的颜色只能为黑色或红色（不存在其他颜色）
2. 树的根节点被设定为黑色
3. 所有叶子节点均为黑色（在实际应用中，通常会省略这些节点）
4. 红色节点的子节点必须为黑色（相邻的两个节点不能同时为红色）
5. 在从任意一个节点到其下方叶子节点的所有路径中，所经过的黑色节点数目保持一致（