Главная » Java, Структуры данных и алгоритмы » АТД «упорядоченный словарь»

0

В упорядоченном словаре требуется сохранить стандартные словарные операции и при этом содержать ключи в определенных упорядоченных отношениях. Для обеспечения упорядоченности ключей можно воспользоваться компаратором, и, как показано ниже, использование упорядоченности помогает эффективно реализовывать АТД «словарь». Кроме того, упорядоченный словарь дополнительно поддерживает следующие методы, не входящие в стандартный набор АТД «словарь»:

closest Key Before( к): возвращает ключ объекта с наибольшим ключом, меньшим или равным к.

. Input: объект (ключ); Output: объект (ключ).

closestElemBefore(A;): возвращает элемент объекта с наибольшим ключом, меньшим или равным к. Input: объект (ключ); Output: объект (элемент).

closestKeyAfter(A;): возвращает ключ объекта с наименьшим ключом, большим или равным к. Input: объект (ключ); Output: объект (ключ).

closestElemAfter(A;): возвращает элемент объекта с наименьшим ключом, большим или равным к. Input: объект (ключ); Output: объект (элемент).

Каждый из этих методов возвращает специальный объект NO_SUCH_KEY, если в словаре не найден объект, отвечающий требованиям запроса.

Поскольку вышеперечисленные операции предполагают упорядоченность, невозможно применить регистрационный файл или хеш-таблицу для реализации словаря, поскольку эти структуры не позволяют систематизировать данные. И действительно, наилучшего результата при работе с хеш-таблицами можно достичь при произвольном распределении их ключей. Таким образом, должна быть создана новая разновидность реализации при работе с упорядоченными словарями.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии