红黑树

1. 基于 2-3 Tree

为了让树高能够维持~lg(n)。
保持各个底部空链接和root距离相等(为了维持这个性质，后面插入时才会有各种变化)

1.1 结构

• 2节点(含有一个key和两个链接)
• 3节点(含有两个key和三个链接)

1.2 操作

• 2节点 插入-->直接添加，变成3节点
• 3节点 插入-->直接添加，然后裂变成三个2节点
• 向父节点为2节点的 3节点 插入-->父节点变3节点，然后下面裂变成2个2节点
• 向父节点为3节点的 3节点 插入-->会一直向上裂变，知道遇到2节点

2. 红黑树就是2-3树的一个实现

1.1 结构

• 2节点(含有一个key和两个链接) ，就是普通链接，我们叫这种链接为黑链接
• 3节点(含有两个key和三个链接)，为了在二叉树中模拟出这种节点，我们设计两个节点由左斜链接相连的为3节点，其中的链接叫红链接

由此产生两个性质(联想2-3树原型就可以看出):

1. 红链接均为左链接
2. 没有任何一个节点与两个红链接相连
3. 树是黑色平衡的。

如何表示红键：我们在每个node设一个color，其指代指向这个节点的链接的颜色。