红黑树的概念

1. 每个节点不是红色就是黑色。（废话）
2. 树的根节点是黑色。（一棵树最上面的那一个节点）
3. 不存在相连的红色节点，黑色节点可以相连。
4. 所有的叶子节点都是黑色的节点，且是空值（NIL），不会存储数据。
5. 从整棵树上的任意一个节点出发，到达其任意一个叶子节点的路径，所包含的黑色节点相同。

插入节点时，当前节点为红色（插入节点一定是红色），父亲节点为红色，叔叔节点也是红色，此时就将父亲节点和叔叔节点设为黑色，爷爷节点设为红色。

此时会发现有两个红色节点相连了，这是不符合定义的，所以需要进行旋转和变色。

旋转方案

1. 左旋条件

   当发现存在这么一个红色节点，其父亲节点是红色，叔叔节点是黑色（空值NIL的叶子节点也算），当前节点是右子树，则需要以其父亲节点为根节点进行左旋（以其自身节点为基础左旋）。

2. 右旋条件

   当发现存在这么一个红色节点，其父亲节点是红色，叔叔节点是黑色，当前节点是左子树，便以其爷爷节点为根结点（以父节点为基础）右旋，将其父节点改为黑色，其爷爷节点改为红色。

为什么大多数据结构都不用平衡二叉树，而用红黑树的原因在于，平衡二叉树为了保持树的平衡，需要进行大量的旋转操作，这个会影响到操作性能。而红黑树有时虽然也需要进行旋转操作（红黑树是一个弱平衡树），但是他不需要保持整棵树的平衡，每次插入操作最多也只会旋转2次。

且红黑树和平衡二叉树的查询性能都为O(logn)。