18. Red Black Trees

Rotation 方法

• rotateLeft(G)：让 G 成为它右侧子节点的新左侧子节点
  • 先合并，再让 G 移动到左侧
    
• rotateRight(P)：让 P 成为它左侧子节点的新右侧子节点
  • 先合并，再让 P 移动到右侧
    

Red Black Trees

改变 2-3 trees 的写法，将一个 3-Nodes（可以拥有三个子节点的节点）拆分，并用红线连接：

• 右侧在上，左侧在下

我们称这种结构为 Left-Leaning Red Black Binary Search Tree

• 他们也是一种 BST
• 满足 1-1 的关系
• 性质：
  • 高度：若 2-3 tree 的高度是 H，则 LLRB 的高度为 2H+1
  • 没有节点能同时有两条红色线
  • 从根节点到所有叶子节点的路径上拥有相同数量的黑色线

LLRB Tree 的添加规则

添加规则只有三条，所有情况都适用：

1. 右边有红色线，则 rotateLeft
2. 左边有两个连续的红色线，则 rotateRight
3. 左右两侧各有一个红色线，则反转颜色

详见示例幻灯片

复杂度分析

• 高度：$O(log N)$
• “包含”方法：$O(log N)$
• “插入”方法：$O(log N)$