前言
二叉排序树存在劣化情况 二叉平衡树为了维持查找性能在插入和删除的时候开销太大 红黑树就出现了。红黑树不像二叉平衡树在任意时刻两个子树高度差相差最多1 参考自 http://www.sohu.com/a/201923614_466939
性质
- 节点由红色和黑色构成，根节点为黑色
- 叶子节点由黑色的NIL节点构成
- 红色节点的子节点一定是黑色节点，并且一定包含两个叶子节点。这意味着不存在连续的两个红色节点。
- 从任意一个节点出发，到任意一个NIL节点，都经历了相同数目的黑色节点
这意味着从根节点出发，到任意一个叶子节点，最长路径和最短路径差不超过最长路径的一半。这种情况下，最长路径和最短路径的黑色数目一样，最长路径最多多黑色个红色节点。
变色与旋转
当插入一个节点（或删除一个节点），红黑树的性质被破坏。使用变色和旋转来调整。
变色
如果两个节点连续为红色，需要变色
旋转
如果有一条路径上的黑色节点太多，需要旋转
变色与旋转的条件
这个之后在总结