Должны ли узлы деревьев и подобные структуры данных быть видимыми снаружи?

Question

Я прочитал книгу «Структуры данных и алгоритмы Майкла Т. Гудрича в Java» и часто сталкивался с сигнатурами методов, как, например, в следующем примере, взятом из дерева:* Для меня предложенный API выглядит немного странно.Я не понимаю, почему они делают класс / объекты Position доступными для внешнего мира.Лично я бы создал что-то вроде этого:

public E parent(E e)

Я вижу, что, учитывая, что Position хранит ссылку на своего родителя, второй вариант медленнее, потому что метод первыйдолжен найти e 'Position объект в дереве.Тогда как первый метод мог вернуть ссылку в постоянное время.

Но версия из книги позволила бы функции-члену parent() запускаться даже с объектами позиции, не сохраненными в связанном дереве, что, по моему мнению,очень странно.

Есть ли веские причины для первой версии, которую я не принимаю во внимание?

Answer 1

Почему странно вызывать parent() для объектов, которых нет в дереве? Вы можете сделать это и со второй версией, то есть вы можете вызвать parent(E) на некоторых E, которых нет в дереве.

В общем, я думаю, что раскрытие древовидной структуры имеет смысл, когда то, что вы предоставляете пользователям, является деревом. Если вы, например, создавали ассоциативный массив, используя дерево, вам даже не нужно показывать метод parent().

Другая причина первой может заключаться в том, что некоторые E могут быть не уникальными в дереве. Так что, если в дереве дважды присутствует E, каждый раз с другим родителем, неясно, что должно возвращать parent(E). parent(Position<E>) не имеет этой проблемы.

И причина производительности тоже может быть значительной. Если разница между O(N) и O(1), то это, безусловно, того стоит.