rbtree红黑树

https://zhuanlan.zhihu.com/p/370775073

结点必须是红色或者黑色。
根节点必须是黑色。
叶节点(NIL)必须是黑色(NIL节点无数据，是空节点)。
红色结点不能连续。
从任一节点出发到其每个叶子节点的路径，黑色节点的数量必须相等。

https://blog.csdn.net/qq_38685503/article/details/103425572

插入
由于红黑树对黑色节点的要求较为苛刻，新插入的节点默认为红色。

将某个节点插入到红黑树，详细过程如下：

首先，红黑树本身是一个二叉搜索树，依据其性质可以找到相应的插入位置，保证节点插入后key仍有序。
插入后，进行一系列的旋转、着色使其继续保持红黑特性。

删除
删除和插入操作类似，也分为两个步骤：

红黑树本身是一个二叉搜索树，根据其性质寻找到对应节点并删除掉。删除的情况如下
若该节点是叶子节点，则直接删除。
若只有一个子树，则用子树替代当前节点。
若有两个子树，则用右子树的最小值(大于被删除元素的最小值)替代当前节点。
通过旋转、着色等操作将红黑树修正，使之成为新的红黑树。

https://blog.csdn.net/weixin_46065476/article/details/122442833