TreeMap源码剖析:自定义排序规则的红黑树map数据结构

本文主要是介绍TreeMap源码剖析:自定义排序规则的红黑树map数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

概述
基本结构
构造函数
自定义排序实现
维护红黑树性质
小结

概述

Java中的TreeMap类实现了自定义排序规则的红黑树（Red-Black Tree）Map数据结构，它保证了键值对按照键的自然顺序或提供的比较器（Comparator）进行排序。TreeMap实现了NavigableMap接口的有序映射，它使用红黑树数据结构存储键值对。红黑树是一种自平衡的二叉查找树，它通过颜色标记和性质维持来确保树的平衡，从而保证了查找、插入、删除等操作的高效性（平均和最坏情况下时间复杂度为O(log n)）。

基本结构

成员变量：TreeMap内部维护了一个根节点（root），用于指向红黑树的根；一个比较器实例（comparator），用于自定义排序逻辑；以及其他辅助变量如size（存储元素数量）、modCount（记录修改次数，用于快速失败机制）、entrySet（存储所有Entry的集合）等。
Entry节点：TreeMap内部使用Entry类表示每个映射关系的节点，包含键（key）、值（value）、左子节点（left）、右子节点（right）、父节点（parent）以及颜色标志（color，使用布尔值表示红黑）。

Entry<K,V>内部类：代表红黑树中的节点，包含键、值、颜色、左右子节点和父节点等信息。
root：指向红黑树的根节点。
comparator：用于自定义键排序的比较器，如果没有提供，则使用键自身实现的Comparable接口进行排序。
size：记录树中节点的数量。
modCount：用于追踪结构修改的次数，用于迭代器的快速失败机制。

构造函数

默认构造函数：默认情况下，如果未提供比较器，TreeMap会使用键的自然排序（通过实现Comparable接口）。
带比较器构造函数：可以通过传递一个Comparator实例来指定自定义排序规则。
从其他集合构造：可以从已有的Map或SortedMap构造TreeMap，并继承或重新定义排序规则。

public TreeMap() {comparator = null;
}public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;
}

自定义排序实现

比较器使用：TreeMap在插入、删除和查找操作时，会调用comparator来比较键的顺序。如果键实现了Comparable接口且没有提供比较器，它将使用Comparable.compareTo()方法；如果提供了比较器，则使用Comparator.compare()方法。
插入操作：插入操作（如put(K key, V value)）涉及到了查找插入位置、创建新节点、调整树结构以维持红黑树性质的过程。核心在于putTreeVal()方法，它负责找到插入点，并调用balanceInsertion()来保持红黑树的平衡。
删除操作：删除操作（如remove(Object key)）较为复杂，需要处理多种情况，包括节点是叶节点、只有一个子节点或两个子节点的情况。删除后，通过balanceDeletion()方法调整树结构，确保红黑性质。
查找操作：查找操作（如get(Object key)）利用了红黑树的有序性，从根节点开始，根据键的比较结果选择左孩子或右孩子进行递归查找，直到找到目标节点或达到叶子节点。

维护红黑树性质

颜色规则：红黑树通过节点的颜色标记来维持平衡，确保任何路径从根到叶子节点经过的黑色节点数量相同，从而保证最坏情况下的查询时间复杂度为O(log n)。
旋转：包括左旋(rotateLeft())和右旋(rotateRight())，用于在插入或删除后重新平衡树。
颜色翻转：改变节点及其子节点的颜色，用于调整红黑树的平衡。在某些情况下，仅通过颜色翻转(flipColors())即可恢复平衡，这通常发生在两个连续红色节点的情况。

插入和删除平衡调整：通过balanceInsertion()和balanceDeletion()方法，根据插入或删除后的具体情况进行相应的调整操作，包括颜色变化和旋转。