红黑树

红黑树是一棵二叉搜索树，每个结点上增加了一个存储位来表示结点的颜色，可以是RED 或 BLACK。

通过对任何一条root->叶子 的路径上的所有节点的颜色来进行约束。

红黑树确保没有一条路径比其他路径长2倍，是近似平衡的。

性质：

1、节点要么红，要么黑；

2、根节点黑色；

3、叶节点黑；

4、如果一个节点红，那么两个子节点都是黑；

5、每个节点到所有叶子节点的路径上的黑节点数目一样；

红黑树的操作：

每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。

插入删除可能会导致不再符合红黑树的性质，恢复红黑树的性质要O（logn），效率高。

一棵含有n个节点的红黑树的高度至多为2log(n+1).

插入操作

最后的这个T黑色节点是哨兵节点，从根节点沿任意路径到达哨兵节点，路径上的黑色节点总数是相同的。

为了满足这个条件，先让我们插入的数据都是红色，假设被插入的节点是e；

1、e是根节点，直接涂黑了；

2、e的父节点是黑，插入不用管了；

3、e的父节点是红：

（1）叔叔节点也是红：父叔变黑，爷变红，爷变成当前节点进行检查；

（2）e是右孩子，叔叔黑，父节点作为当前节点左旋；

（3）e是左孩子，叔叔黑，父变黑，爷变红，爷为支点右旋；

核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。