红黑树学习笔记

定义：

红黑树比 AVL 树的性能要高，插入/删除的时间复杂度还是O(log2n)

五个性质：

1. 节点都是红，黑；
2. 根节点是黑色的；
3. 叶子节点（没有左/ 右儿子的节点） 的左右儿子都是 Nil 节点，Nil 节点都是黑色的
4. 红色节点的左右儿子都是黑色节点；
5. 从根节点到每个 Nil 节点的黑色节点数都相同。

难点

插入操作：

情形1：该树为空树，

​ 操作：直接在根节点上插入黑色节点。

​ 由于性质3和性质5，插入节点必须是红色节点，但是根节点例外。

情形2：插入节点 N 的父节点是黑色的，

​ 操作：不违反任何规则，不需要调整，直接插入一个红色节点。

情形3：插入节点 N是红色的， 其父节点P是红色的

情形4：插入节点 N是红色的，其父节点P 是红色的，P 的兄弟节点U是黑色的，

​ G 是 P 的父节点， P 是 G 的左儿子，插入节点 N 也是 P 的左儿子

情形5：插入节点 N是红色的，其父节点P 是红色的，P 的兄弟节点U是黑色的，

​ G 是 P 的父节点， P 是 G 的左儿子，插入节点 N 是 P 的右儿子