Категория:Информационные деревья

В программировании часто приходится иметь дело с  необходимостью хранения динамических множеств, состоящих из однотипных объектов, между которыми нет никаких отношений. Разные приложения используют разные наборы операций. Нередко, например, требуется лишь добавлять или удалять элементы множества, а также проверять, принадлежит ли множеству данный объект.

Обычно элементы множества — это объекты сложной природы и с внутренней структурой, поэтому для эффективной работы с ними всем возможным элементам множества ставится в соответствие (взаимно однозначно) так называемые ключи — некоторые объекты без внутренней структуры, между которыми существует некоторое отношение, позволяющее сделать динамическое множество информационным.

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

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

В качестве системы ключей всегда выбирается такая, для которой между ключами существует некоторое естественное отношение. Это означает, что приписывание элементам информационного множества ключей вводит в него, как правило, некоторую структуру. Эта структура используется для регуляризации операций над информационными множествами.