红黑树是一种自平衡二叉树查找树，是一种常用的数据结构。在jdk1.8中，TreeMap、TreeSet和HashMap都使用到了红黑树。
二叉排序树
性质
- 左子节点的值小于父节点的值
- 右子节点的值大于父节点的值
- 任意节点的左右子树也是一个二叉排序树
时间复杂度
在理想的情况下，时间复杂度为 O(logN)
极端情况下(树为一链表)，时间复杂度为 O(N)
红黑树
红黑树从本质上来说也是一颗二叉查找树，但是在二叉树的基础上增加了着色相关的性质，使得红黑树可以保证相对平衡，从而保证红黑树的增删改查的时间复杂度最坏也能达到O(log N)。
性质
- 节点是红色或黑色
- 根节点是黑的
- 叶子节点是黑的空节点
- 如果一个节点是红的，他的两个儿子节点都是黑的
- 对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点
插入
- 按二叉查找树的算法，将目标结点插入；
- 把目标结点设置为当前结点，并把它着红色；
- 这时可能违背红黑树的性质，所以，进行修正；
左旋和右旋
旋转时，不能改变节点的左右关系。
