Java TreeMap调用subMap().clear()的时间复杂度是多少

问题代码 #

TreeMap<Integer, Integer> tree = new TreeMap<>();// 假设该TreeMap包含N个键
NavigableMap<Integer, Integer> subMap = tree.subMap(left, true, right, true);// 假设返回的subMap包含M个键
subMap.clear();// 该行代码的时间复杂度分析

最终结论 #

针对Oracle/OpenJDK的标准TreeMap实现，subMap.clear()的最坏时间复杂度为O(M log N)，摊销时间复杂度为O(M + log N)，达不到严格的O(M)最坏时间复杂度。

原理说明 #

• TreeMap底层基于红黑树实现，subMap()返回的是原TreeMap的视图，不会额外拷贝M个元素，对subMap的所有修改都会直接作用在原TreeMap上。
• subMap.clear()的执行逻辑分为两个阶段：
  1. 定位区间的左右边界节点：依赖红黑树的搜索能力，耗时固定为O(log N)
  2. 遍历并删除区间内的所有节点：从左边界节点开始，通过节点内置的后继指针依次遍历M个属于区间的节点，逐个执行删除操作。遍历获取所有待删除节点的过程是O(M)，不需要额外的搜索开销。
• 删除操作的开销说明：
  单个红黑树节点删除后的结构平衡调整最坏需要O(log N)时间，因此最坏情况下总开销为O(M log N + log N) = O(M log N)。但由于删除的是中序遍历连续的节点，红黑树的调整开销可以被摊销，实际运行时的摊销复杂度为O(M + log N)，远优于随机删除M个节点的开销。
• 目前Java标准库的TreeMap没有实现连续区间批量删除的专项优化，因此达不到严格的O(M)最坏时间复杂度，部分其他语言或第三方有序集合实现（如C++的std::map区间erase重载）可做到O(M + log N)的最坏时间复杂度。

内容的提问来源于stack exchange，提问作者Veera Kumar