红黑树规则
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树从根节点到叶子节点的路径不会超过最短路径的2倍。
红黑树并不是完美平衡二叉树，它主要保证每个节点到叶子节点的路径都包含相同数量的黑节点。
也因此需要把其中一些节点变色为红节点，否则，节点全部是黑色不就行了？？？
红黑树变换
红黑树保持平衡主要靠三个操作：
- 左旋：以某个节点作为支点(旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。
- 右旋：以某个节点作为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
- 变色：节点的颜色由红变黑或由黑变红。
插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。
红黑树为空树
直接把插入节点作为根节点就行，根据规则二，设置为黑节点。
插入节点的Key已存在
插入前已经平衡，所以需要做的替代。设置为对应节点的颜色并更新值。
插入节点的父节点为黑节点
直接插入，并设置为红色。
插入节点的父节点为红节点
根据红黑树的性质2：根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。
然后可根据下列子场景操作：