关于红黑树的一些总结

红黑树：R-B Tree 也是一颗自平衡的有序二叉树，但它的平衡不是根据子树的高度来调整的 而是给每个节点设置颜色，通过颜色的关系达到平衡

红黑树的特性： 1、每个节点或者是黑色或者是红色 2、根节点必须是黑色 3、每个叶子节点（NULL）是黑色 [注意：这里的叶子节点，是指空的叶子节点（NULL）] 4、如果一个节点是红色，则它的子节点必须是黑色 不能已有两个连续的红色 5、从从一个节点到该节点的所有子孙节点的所有路径上，包含了相同数目的黑色节点

红黑树只能保证大致上是平衡的（最长路径不会超过最短路径的两倍）

红黑树的插入： 插入的节点必须是红色 1、如果父节点是黑色，直接插入、不需要调整 2、如果父节点是红色，需要调整 a、叔叔节点不存在 or 叔叔节点为黑色 进行左旋 or 右旋 祖父节点置红、父节点置黑 黑色节点不增加 b、叔叔节点存在且为红色 祖父节点置红、父节点和叔叔置黑 把祖父节点看作当前节点，继续向上讨论 讨论a： 1、父节点为祖父节点的左子树，叔叔为右 (i)node节点为父节点的右节点，以父为轴右旋转 祖父置红、父置黑 (ii)node节点为父节点的右节点，以node为轴左旋、右旋 祖父置红、node置黑 2、父节点为祖父节点的右节点 叔叔为左 (i)node节点为父节点的右节点 以父为轴左旋转 祖父置宏、父置黑 （ii）node节点为父节点的左节点 以node为轴右旋、左旋 祖父置红、node置黑

红黑树的删除： 注意：红黑树删除一个数，再把同样一个树插进去，其实就已经不是同一棵树了 1、叶子节点 如果叶子节点为红色，直接删除不需要调整 如果叶子节点为黑色，删除后需要调整 2、只有一个字节点 子节点一定是红色 把子节点的值替换掉当前节点的值，删除红色节点 3、有两个字节点 转变成1和2 从左子树找最大值替换当前节点的值 从左子树中删除最大值，就转变成1或2的操作(最大值节点只能是叶子节点或者是只有一个子节点)

红黑树的优缺点： 优点：插入、删除效率，比AVL树高 缺点：没有AVL树那么均匀，查找效率没有AVL高