一、红黑树的概念及性质
概念：
红黑树是一种二叉搜索树，每个结点上增加一个存储位表示结点的颜色
通过对各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
| 树种 | 平衡方式 | 现象 |
|---|---|---|
| AVL树(自平衡二叉查找树) | 严格平衡 | 左右子树高度不超过1 |
| 红黑树 | 近似平衡 | 最长路径不超过最短路径的二倍 |
性质：
- 根节点是黑色
- 红色节点的孩子结点是黑色
- 对于每个结点，每条从该结点到叶结点的简单路径上的黑色结点数目相同
- NIL结点是黑色
引申：
最短路径都是黑结点
最长路径是黑红相间的路径
红黑树示例图：
二、红黑树结点的定义 对于红黑树来说以颜色来代替AVL树的平衡因子的作用，除此之外在定义上没有什么区别
定义中将节点的默认颜色给成红色
| 默认颜色 | 现象 | 结果 |
|---|---|---|
| 黑 | 插入一个黑结点让该路径上的黑结点数量加1，造成与其他路径上黑结点数量不一致 | 一定会影响 |
| 红 | 父结点为黑色结点则没有影响,父结点为红结点有影响 | 不一定会影响 |
三、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，当违反限制条件时就需要做出相应的调整
红黑树的插入可分为两步：
按照二叉搜索的树规则插入新节点
新节点插入后检查红黑树的性质是否造到破坏
注意：
如果父节点黑色，没有违反红黑树任何性质，不需要调整
如果父节点红色，就违反了性质三，分情况来讨论
看祖父结点
看叔叔结点，可将红黑树的调整分为三种情况
注：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
1、变色处理
情况一: cur为红，p为红，g为黑，u存在且为红
情况二: cur为红，p为红，g为黑，u不存在/u为黑
情况三: cur为红，p为红，g为黑，u不存在/u为黑
我的理解：
| 树种 | 查找 | 删除 | 插入 |
|---|---|---|---|
| 二叉树 | 最好O(logn)、最差O(n) | - | - |
| 二叉搜索树（二叉排序树、二叉查找树） | 最好O(logn)、最差O(n) | - | - |
| 红黑树 | O(logn) | O(logn) | O(logn) |
| B树 | - | - | - |
| B+树 | - | - | - |
这些树好像都差不多，都是插入，判断、旋转
红黑树与AVL树的比较
分析总结：
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logn)
红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多