树

红黑树

为何引入红黑树(RBT)

平衡二叉树AVL:插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大)，再进行LL/RR/LR/RL调整。

红黑树RBT:插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

RBT定义

首先，红黑树是一个二叉排序树。其次，需要满足以下的条件：

①每个结点或是红色，或是黑色的
②根节点是黑色的
③叶结点（外部结点、NULL结点、失败结点）均是黑色的
④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色)
⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

这里需要注意的是，我们所说的第三条指的是查找失败的节点均是黑色的，如下图所示：

RBT的插入规则

1. 先查找，确定插入位置（原理同二叉排序树)。
2. 插入新结点是根——染为黑色；新结点非根——染为红色。
   1. 若插入新结点后依然满足红黑树定义，则插入结束。
   2. 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义。
      1. 叔叔结点是黑色：旋转+染色
         1. LL型:右单旋，父换爷+染色
         2. RR型:左单旋，父换爷+染色
         3. LR型:左、右双旋，儿换爷+染色
         4. RL型:右、左双旋，儿换爷+染色
      2. 叔叔结点是红色：染色+变新