通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

核心提示： {aaa=80.0,bbb=89.0,ccc=89.0,zzz=80.0}TreeMap 的添加节点红黑树红黑树是一种自平衡排序二叉树，树中每个节点的值，通过分析 JDK 源代码研究 TreeMap 红黑树算法实现(3)，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所

　{aaa=80.0,　bbb=89.0,　ccc=89.0,　zzz=80.0}　

TreeMap 的添加节点

红黑树

红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。

为了理解 TreeMap 的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

它的左、右子树也分别为排序二叉树。

图 1 显示了一棵排序二叉树：

图 1. 排序二叉树