红黑树数据结构与实现
1. 红黑树的概念
红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

2. 红黑树的性质
- 1. 每个结点不是红色就是黑色
- 2. 根节点是黑色的
- 3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
- 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点,是红黑树特有的 NIL 节点)
其中,第 5 条性质是为了帮助理解性质 4。例如:下面这棵树符合红黑树的定义吗?

直观上看似乎符合,但加上 NIL 节点后:

可以看到,用蓝色线条画出的这条路径容易被忽略。从根节点向下看,其他路径上的黑色节点数都是 2 个(不算 NIL 节点),唯独蓝色线路上的黑色节点只有 1 个,所以上面这棵树是不符合红黑树定义的,它不是红黑树!
满足了如上 5 条性质,就可以保证最长路径不超过最短路径的两倍。这是基于数学推导的设计,只要能使用并控制红黑树的结构即可。
3. 红黑树节点的定义
下面我们先实现一颗 kv 结构的红黑树。
// 颜色定义
enum Colour {
RED,
BLACK
};
// 红黑树节点
template<class K, class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
( pair<K, V>& kv) :
_left(),
_right(),
_parent(),
_kv(kv),
_col(RED) {}
};


