红黑树

红黑树比平衡二叉树更加宽松，左右子树高度差最大可以达到差别一倍

根据上面的定义能得知：红黑不能相连，最长的路径为红黑相间，最短的都是黑节点。如果忽略所有的红节点和 NIL，此时的红黑树是满树，是一颗非常标准的平衡树（不一定是二叉）。

插入失衡的调整：左旋和右旋

删除：

若待删除节点为树中唯一的节点的话，直接删除即可，这里不将其算作删除操作的 3 种基本情况中。
若待删除节点 N 既有左子节点又有右子节点，则需找到它的前驱或后继节点进行替换（仅替换数据，不改变节点颜色和内部引用关系），则后续操作中只需要将后继节点删除即可。
待删除节点为叶子节点，若该节点为红色，直接删除即可，删除后仍能保证红黑树的 4 条性质。若为黑色，删除后性质 4 被打破，需要重新进行维护。
待删除节点 N 有且仅有一个非 NIL 子节点，则子节点 S 一定为红色。因为如果子节点 S 为黑色，则 S 的黑深度和待删除结点的黑深度不同，违反性质。由于子节点 S 为红色，则待删除节点 N 为黑色，直接使用子节点 S 替代 N 并将其染黑后即可满足性质。

双黑是指删除操作中替换节点与删除节点均为黑色的情况，双黑标记表明了当前树违背了黑色节点数目一致的原则，需要进行修复

🪴 Cyril