java - 树集子集方法的复杂性？

Question

我正在寻找树集子集方法的时间复杂度。是 O(n)，其中 n 是导航集中的项目数吗？

Answer 1

TreeSet的subSet()方法内部调用了TreeMap的subMap()方法。 Java中的TreeMap是使用红黑树实现的。 subMap() 方法返回 SubMap 类的新对象，SubMap 类是 TreeMap 的内部类(嵌套类)。 SubMap 类的构造函数只存储 subMap 的第一个和最后一个键，如下实现:

SubMap(Object minKey, Object maxKey)
{
  if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
    throw new IllegalArgumentException("fromKey > toKey");
  this.minKey = minKey;
  this.maxKey = maxKey;
}

除 size() 方法外，大多数操作与 TreeMap 花费的时间相同。SubMap类的size()方法实现如下:

public int size()
{
  //Returns node >= minKey(i.e. first node in subSet). Takes O(logN) time.
  Node node = lowestGreaterThan(minKey, true);
  //Returns node >= maxKey(i.e. first node in subSet). Takes O(logN) time.
  Node max = lowestGreaterThan(maxKey, false);
  int count = 0;
  while (node != max)
    {
      count++;
      //In worst case, successor takes logN time
      node = successor(node);
    }
  return count;
}

lowestGreaterThan() 方法需要 O(logN) 来查找子集中的键。 successor() 方法采用与红黑树中的高度成正比的 O(logN) 来查找下一个后继者。而要找到 subSet 返回的 NavigableSet 的大小，我们需要遍历 subSet 中的每个节点。因此，函数 SubMap.size() 的总复杂度:- O(logN)+O(logN)+O(MlogN) ~ O(MlogN)，其中 M 是子集的大小。