Алгоритмы и структуры данных. Извлечение информации на языке Java

155

Реализация TreeMap

Некоторые из методов Map легко реализовать, как size и clear:

public int size() {

return size;

}

public void clear() {

size = 0;

root = null;

}

Метод size, очевидно, является методом постоянного времени.

Кажется, что и метод clear должен быть таким же, но учтите

следующее: когда root установлен в null, сборщик мусора ути-

лизирует узлы дерева, а это занимает линейное время. Нужно ли

учитывать работу сборщика мусора? Я думаю, да.

В следующем разделе вы дополните некоторые другие методы,

в том числе наиболее важные — get и put.

Реализация TreeMap

В репозитории для этой книги вы найдете следующие исходные

файлы:



MyTreeMap.java содержит код из предыдущего раздела с опи-

санием отсутствующих методов;



MyTreeMapTest.java включает