C/C++ 红黑树

由于强制平衡所导致付出的代价比较高,所以红黑树出现了。

红黑树是一种二叉搜索树，但是它多了一个颜色的属性。通过红黑染色规则来弱平衡二叉树，与AVL的强制平衡相比，红黑树的树调整次数大大降低。

红黑树性质如下：

1. 将新添加的结点设置为红，“热乎的”。
2. 根节点一定是黑的；
3. 在每个路径的最后都加入一个不带数据的叶子节点，这个叶子节点一定是黑的。
4. 一节点到任意树尾端（NULL）叶子节点路径上含有的黑色结点个数相同。
5. 父子层不能连续出现红色节点，如若出现就改变颜色。
6. 改变颜色后也要保证遵循以上性质。

插入操作

1. 父为黑，直接插。
2. 父为红，叔为红。父叔变黑，爷爷变红。
3. 父为红，叔为黑。若爷父子是弯的就掰直。爷父变色再旋转。（旋转以确保第4条规则）

情况1：

情况2：

情况3：

删除操作：

删除的各情况操作见思维导图：

此处内容需要 回复 后才能查看

补充

调换完可能未达到平衡，需要向下，观察其平衡

根据颜色和树深度观平衡，短树可以认为是发生了删除操作，问题又变为了删除操作的n种情况。

删除的节点有两个非叶子节点：

*p节点删除后位置空缺，需要在树中找到一个节点放置此位置，且能满足排序树规则。其*p在左子树的中序直接前驱或右子树的中序直接后续可满足规则。