RedBlack_Tree
五个条件
- 节点非黑即红
- 根节点是黑色的
- 叶节点(NIL)是黑色的
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 从根节点出发到所有叶节点路径上，黑色节点数量相同
最短路径全黑，节点数 a，最长路径有相同多个黑色节点（条件 5）
，红色节点不能连续（条件 4），节点数 2a
调整策略
插入节点站在祖父节点看
删除调整站在父节点看
插入调整
用带有两个黑色的 NIL 的新节点替换 NIL 叶节点
为了方便调整，新结点初始为红色（黑色节点影响条件 5）
情况一
插入节点的父节点是黑色
直接插入
情况二
插入节点的父节点和叔节点都是红色
父节点、叔节点染成黑色，祖父节点染成红色
情况三 LL
插入节点的父节点是红色，叔节点是黑色，插入节点是父节点的左孩子，父节点是祖父节点的左孩子
祖父节点右旋，祖父节点染成红色，父节点染成黑色
情况四 LR
插入节点的父节点是红色，叔节点是黑色，插入节点是父节点的右孩子，父节点是祖父节点的左孩子
父节点左旋，转换为情况三（祖父节点右旋，祖父节点染成红色，父节点染成黑色）
删除调整
情况一
兄弟节点是红色
父节点左旋，父节点染成红色，兄弟节点染成黑色
情况二
父节点、兄弟节点和兄弟节点的子节点都是黑色
父节点左旋，父节点染成红色
情况三
父节点红色，兄弟节点和兄弟节点的子节点都是黑色
父节点左旋
情况四
父节点任意颜色，兄弟节点的右儿子红色，删除节点是父节点的左儿子
父节点左旋，交换父节点、兄弟节点的颜色，兄弟节点的右孩子染成黑色
情况五
父节点任意颜色，兄弟节点的左儿子红色，删除节点是父节点的左儿子
兄弟节点染成红色，兄弟节点的左儿子染成黑色，兄弟节点右旋，转换为情况四