JDK源码——TreeMap类

摘要

本文将详细介绍TreeMap类的源码与红黑树的相关的特性。红黑树的平衡和红黑树增删该查的方法。帮助大家更好应用这样一种数据结构。

一、TreeMap基础数据结构

public class TreeMap
    extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable

TreeMap内部就是基于红黑树实现的，它的查找、插入、删除操作的时间复杂度均为 O(logn)。

一、TreeMap成员变量

/**
 * The comparator used to maintain order in this tree map, or
 * null if it uses the natural ordering of its keys.
 *
 * TreeMap 内部的比较器，若为空，则为自然顺序
 */
private final Comparator