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

166

Глава 13. Бинарное дерево поиска

те же два случая, что и в предыдущей ветке. Наконец, если

cmp == 0, то мы нашли ключ в дереве, поэтому заменяем его

и возвращаем старое значение.

Я написал этот метод рекурсивно, чтобы сделать его более удо-

бочитаемым, но было бы проще переписать его в итеративном

виде; возможно, вы захотите сделать то же самое в качестве

упражнения.

Симметричный обход

Последний метод, который я попросил вас написать, keySet,

возвращает набор Set, содержащий ключи дерева в порядке

возрастания. В других реализациях Map ключи, возвращаемые

keySet, не имеют особого порядка, но одна из возможностей

реа лизации на основе дерева заключается в простой и эффектив-

ной сортировке. Поэтому мы должны воспользоваться данным

преимуществом. ...