红黑树

五个要点：

应用、性质、复杂度、左旋和右旋、插入、删除

应用：

C++的set和map Java中的TreeSet和TreeMap都是用红黑树实现的

五条性质：

1. 红黑树的节点非红即黑
2. 红黑树的根节点是黑
3. 红黑树的叶节点是nil节点（黑）
4. 红节点的子节点必是黑节点，即不会有连续的红节点
5. 从任一节点到其子树上的根节点都经过相同数目的黑节点

复杂度：

查找logn，一个n个节点的红黑树，高度至多为2log(n+1)   

左旋和右旋：

左旋：左旋是将某个节点旋转为其右孩子的左孩子 右旋：右旋是将某个节点旋转为其左孩子的右孩子 右旋过程：  

插入：

如果插入黑节点：则可能违反性质5，会造成大范围改动 如果插入红节点：则可能违反性质2（简单的涂黑即可），可能违反性质4。 所以我们插入的都是红节点。

1. 插入的是根结点：直接涂黑即可
2. 插入的节点的父节点是黑节点：直接插入，没有破坏规则
3. 插入的节点的父节点是红节点，叔叔节点是红节点：父亲和叔叔节点变黑，祖父节点变红。
4. 插入的节点的父节点是红节点，叔叔节点是黑节点，父亲节点是祖父节点的左分支，插入的节点是父亲的左分支：祖父节点右旋，祖父和父亲颜色互换
5. 插入的节点的父节点是红节点，叔叔节点是黑节点，父亲节点是祖父节点的左分支，插入的节点是父亲的右分支：先对父节点进行左旋，然后就可视为将插入节点和父节点的身份互换，然后进行第4种类型进行操作
6. 插入的节点的父节点是红节点，叔叔节点是黑节点，父亲节点是祖父节点的右分支，插入的节点是父亲的左分支：祖父节点左旋，祖父和父亲颜色互换
7. 插入的节点的父节点是红节点，叔叔节点是黑节点，父亲节点是祖父节点的右分支，插入的节点是父亲的右分支：先对父节点进行右旋，然后就可视为将插入节点和父节点的身份互换，然后进行第6种类型进行操作

    上面4-7的情况(Case)处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。  

删除：

先像二叉查找树一样将节点删除，然后再调整。 当删除有两个孩子的节点时，我们把后继的值给当前节点。而后继节点必定只有一个孩子，所以相当于简化了操作。 再进行简单的操作。 如果是没有孩子的节点，可以直接删除。

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄