Java 1.8: частичный обход NavigableMap с амортизированным O (1), чтобы найти следующую запись?

Question

Я доволен первой операцией O (log n), чтобы найти мою начальную точку в

NavigableMap<Double,MyThing> navlevel = new TreeMap<>();

Но в рукописном C ++ (или, я полагаю, рукописном Java), как только я нашелузел, указывающий на рассматриваемый MyThing, затем я мог бы выполнить «следующую» операцию на этом узле, которая бы амортизировала всего пару операций с указателями.(Если есть правая ссылка, идите вправо, затем полностью влево; в противном случае переходите к своему родителю, пока не найдете узел, из которого вы исходите из левого дочернего узла родителя.)

    Map.Entry<Double,MyThing> entry =
        navthing.ceilingEntry( dSomeValue );

    while ( entry != null ) {

        MyThing level = entry.getValue();

        // Process and break on some condition.

        // vvvvvvvvv This I'm sure is O( log n ) and I want it to be faster!
        entry = navthing.higherEntry( entry.getKey() );
    }

Answer 1

Получите SortedMap с помощью метода tailMap или аналогичного, в соответствии с вашими потребностями, и итерируйте SortedMap запись, установленную следующим образом:

NavigableMap<String, String> original = new TreeMap();
original.put("1", "A");
original.put("2", "B");
original.put("3", "C");

//this headmap1 will contain "2" and "3"
SortedMap<String, String> submap1 = original.tailMap("2");
for(Map.Entry<String, String> entry : submap1.entrySet()) {
  String key = entry.getKey();
  String value = entry.getValue();

  System.out.println(key + " => " + value);
}