一、什么是红黑树？
红黑树是一种自平衡二叉查找树，在插入和删除时，通过特定操作，保持二叉查找树的平衡，从而获得较高的查询性能。通常类似的查找树，都是在插入和删除操作时，保持树的平衡，这样可以降低树的高度，树越深越倾近于链表，链表的查询性能最差。jdk8中，hashmap数据结构，元素小于8是使用链表存储，大于8时使用红黑树。在元素比较少的情况下，链表的查询性能稍差，但是新增和删除快；大于8个时，红黑树新增和删除慢，因为需要平衡树的高度，但是查询快。
树的平衡，从而获得较高的查询性能。通常类似的查找树，都是在插入和删除操作时，保持树的平衡，这样可以降低树的高度，树越深越倾近于链表，链表的查询性能最差。jdk8中，hashmap数据结构，元素小于8是使用链表存储，大于8时使用红黑树。在元素比较少的情况下，链表的查询性能稍差，但是新增和删除快；大于8个时，红黑树新增和删除慢，因为需要平衡树的高度，但是查询快。
二、红黑树特点
1、根节点是黑色
2、所有叶子节点是黑色，并且不存储数据
3、每个红色节点的两个子节点都是黑色
4、每个节点，从该节点到所有可达叶子节点的可达路径，都包含了相同数据量黑色节点
红黑树的查找性能是O(logn)