红黑树的插入操作与普通的 BST 类似，对于红黑树来说，新插入的节点初始为红色，完成插入后需根据插入节点及相关节点的状态进行修正，使之称为合法的红黑树。

结合维护操作，插入操作的平均时间复杂度为

$O(logn)$，n 为当前 tree 的最大高度

具体如何维护有六种情况，其中以下三种比较复杂：

• Case 1: 当前节点 N 的父节点 P 和叔节点 U 均为红色：
  

  
  维护过程如下：
  • 将 P，U 节点染黑，将 G 节点染红（可以保证每条路径上黑色节点个数不发生改变）。
  • 递归维护 G 节点（因为不确定 G 的父节点的状态，递归维护可以确保性质 3 成立）。

• Case 2: 当前节点 N 与父节点 P 和祖辈节点 G 组成三角形（即 N 节点为右子节点且父节点为左子节点，或 N 节点为左子节点且父节点为右子节点。类似 AVL 树中 LR 和 RL 的情况）。此时 U 要么为 NIL 黑色节点，要么普通黑色节点。
  

  
  该种情况无法直接进行维护，需要通过对节点 P 进行旋转操作，将子树结构调整为 Case 3 的初始状态并进入 Case 3 进行后续维护。

• Case 3: 当前节点 N 与父节点 P 和祖辈节点 G 组成一条线（即 N 节点为右子节点且父节点为右子节点，或 N 节点为左子节点且父节点为右子节点。类似 AVL 树中 LL 和 RR 的情况）。此时 U 要么为 NIL 黑色节点，要么普通黑色节点。
  

  
  维护过程如下：
  • 若 N 为左子节点则右旋祖父节点 G，否则左旋祖父节点 G.（该操作使得旋转过后 P - N 这条路径上的黑色节点个数比 P - G - U 这条路径上少 1，暂时打破性质 4）。
  • 重新染色，将 P 染黑，将 G 染红，同时满足了性质 3 和 4。

比较简单的情况如下：

• 该树原先为空，插入第一个节点后不需要进行修正。
• 当前的节点的父节点为黑色且为根节点，这时性质已经满足，不需要进行修正。
• 当前节点 N 的父节点 P 是为根节点且为红色，将其染为黑色即可，此时性质也已满足，不需要进一步修正。