红黑树，是二叉搜索树的一种，它的每个节点只有红色和黑色，从而达到接近平衡的目的。
红黑树的性质：
·根节点都是黑色节点
·每个节点不是黑的就是红的
·如果一个节点是红的，那么它的两个孩子都是黑的
·不能右两个连续的红色节点
·每条路径下，黑色节点的数量都是相等的
·叶子节点都是黑色节点(这里指空节点)
·根节点到叶子节点最长的路径，最多是最短路径的2倍(最短路径都是黑子，最长路径是一黑一红)
红黑树的原理：
和AVL树不一样的是，没有平衡因子，而是节点的结构体中添加了颜色，默认新增节点为红色。
这时候平衡就需要看叔叔节点，也就是父亲节点的兄弟。
我们以右旋为例，父亲在爷爷的左边，当父亲节点存在且为红时，进入场景
场景一：叔叔存在且为红 -- 变色
把父亲和叔叔变黑，爷爷变红，孩子变爷爷，继续往上直到根节点，注意最后根节点变黑。
场景二：叔叔不存在或者存在且为黑色，孩子在父亲的左边 -- 右单旋
爷爷节点右旋下来，父亲变黑，爷爷变红。
场景三：叔叔不存在或者存在且为黑色，孩子在父亲的右边 -- 左右双旋
父亲先左旋，然后到爷爷右旋，爷爷变红，孩子变黑。
方向相反的则反之。
可以观察到，每条路径的黑色节点数目都是相等的。
红黑树与AVL树的比较：
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
