更多数据结构内容，请参考：数据结构 - 概要
简介
红黑树介绍请参考：
红黑树是二叉查找树中的Super Star，应用极其广泛，远甚于其他查找树。
红黑树在面试中被问到的概率非常大。
疑问中理解技术
红黑树有什么特点
红黑树的特点，只能记了：
- 是一个二叉查找树
- 所有的节点只有也必须有红色和黑色两种颜色
- 根节点是黑色的
- 所有的叶子节点是黑色的
- 根节点到叶子节点的所有路径上，黑色节点数量必须一样
- 任意两个红色节点不能相连
正是由于上述规定，导致了红黑树的特性
为什么使用红黑树
首先，红黑树是个二叉查找树，说明这个树是主要用来进行查找的。
普通的二叉查找树有个缺点，即在极端情况下，会退化成链表，这样查找效率是非常差的。这个参考数据结构 - 二叉查找树
为了使查找效率比较均衡，不会出现极端情况下变得太差的情况，需要二叉查找树是平衡的。参考数据结构 - 平衡二叉树
红黑树的上述特点，使红黑树是近似平衡的，即两棵子树的高度差不会超过2倍。
这样就使红黑树的查询效率是比较高，也比较稳定的
为什么不使用AVL树
AVL树是严格的平衡二叉树，两棵子树的高度差最大为1。所以AVL树的查找性能是非常均衡，也非常好的。
但是正是由于AVL的条件比较严格，实现起来会非常复杂。当然，实现复杂不算什么问题，问题是在严格的平衡条件下，插入和删除效率比较低。为了保证严格平衡，增减节点时，旋转次数比较多，影响性能。
红黑树不追求完全平衡，但是旋转次数大大较少。在保证查询性能没有降低多少的情况下，大大提高了增删节点的性能。
红黑树在哪些地方得到了使用
- java中的TreeMap、TreeSet底层使用的红黑树
- java8中的HashMap和ConcurrentHashMap在处理Hash冲突时，使用的红黑树(java8之前使用的是链表)
One More Thing
红黑树也有缺点。
缺点就是实现起来非常复杂，有诸多特殊条件需要考虑。即使是高级程序员，也不能保证实现出一个完美的红黑树。
像redis的作者就嫌红黑树实现太过复杂，就使用跳表(Skip List)来代替红黑树。
那么跳表又是什么高级东西？他为什么可以代替大名鼎鼎的红黑树？请参考数据结构 - 跳表
网友评论