概述

RBT，RedBlackTree

应用场景

在JDK1.8的HashMap中，为了解决过度哈希冲突带来的长链表，会将链表转为红黑树；Linux底层的CFS进程调度算法中，vruntime利用红黑树来进行存储；多路复用技术的Epoll的核心结构也是红黑树+双向链表。

性质

每个节点或是红色的，或是黑色的。
根节点是黑色的。
每个叶子节点（NIL）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

引理

一棵有n个内部节点的红黑树的高度至多为 $2\lg(n+1)$

证明

当节点都为黑色时，该树的节点数最少。
若bh（black-height）为黑高，则用归纳法：

bh=0时n=0

x (NIL)

bh=1时n=1

NIL

bh=2时n=3

node

NIL

bh=3时n=7

node

NIL

因此，以x为根的子树至少包含 $2^{bh(x)}-1$ 个内部结点。
设h为树的高度，则根据性质4，从根到叶节点（不包括根节点）的任何一条简单路径上都至少有一半的节点为黑色，所以根的黑高至少为 $\frac h2$ ，于是有 $n\ge2^{\frac h2}-1$ ，即 $h\le2\log_2(n+1)$ 。

旋转

RIGHT-ROTATE(X) -->

<-- LEFT-ROTATE(Y)

插入

设插入节点为C

根节点：C涂黑
父黑：无操作
父红
1. 叔红：叔、父涂黑，祖涂红，以祖递归
  1. LAST
  GP
  
  P
  
  C
  
  NIL
  
  U
  
  NIL
  
  NIL
  
  NIL
  
  NIL
  1. NOW
  GP
  
  P
  
  C
  
  NIL
  
  U
  
  NIL
  
  NIL
  
  NIL
  
  NIL
2. 叔黑
  1. 父、C同侧
    1. 同左：以祖右旋，祖涂红，父涂黑
      1. LAST
      GP
      
      P
      
      C
      
      B (NIL)
      
      U (NIL)
      
      NIL
      
      NIL
      1. NOW
      GP
      
      P
      
      C
      
      B (NIL)
      
      U (NIL)
      
      NIL
      
      NIL
    2. 同右：以祖左旋，祖涂红，父涂黑
      1. LAST
      GP
      
      U (NIL)
      
      P
      
      B (NIL)
      
      C
      
      NIL
      
      NIL
      1. NOW
      GP
      
      P
      
      C
      
      B (NIL)
      
      U (NIL)
      
      NIL
      
      NIL
  2. 父、C异侧
    1. 父左：以父左旋，转至同左侧
      1. LAST
      GP
      
      P
      
      B (NIL)
      
      C
      
      U (NIL)
      
      NIL
      
      NIL
      1. NOW
      GP
      
      P
      
      B (NIL)
      
      C
      
      U (NIL)
      
      NIL
      
      NIL
    2. 父右：以父右旋，转至同右侧
      1. LAST
      GP
      
      U (NIL)
      
      P
      
      C
      
      B (NIL)
      
      NIL
      
      NIL
      1. NOW
      GP
      
      U (NIL)
      
      NIL
      
      P
      
      C
      
      B (NIL)
      
      NIL