Оптимальная структура данных для добавления и поиска

[B@R5uk]

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

[mihaild]

B@R5uk в сообщении #1270507 писал(а):

и в то же время линейное время добавления элемента, как, например, связанный список

Здесь точно линейное, а не константное?

Вообще все основные операции за логарифм умеют делать самобалансирующиеся деревья поиска. Вы какие оценки всё-таки хотите? И в худшем или в среднем случае?

B@R5uk в сообщении #1270507 писал(а):

ключ, по которому производится сортировка у различных элементов может быть одинаков, но все такие элементы всё равно необходимо хранить в этой структуре

Это как раз не проблема, просто вместо значения храните контейнер значений.

[B@R5uk]

Спасибо за быстрый ответ.

mihaild в сообщении #1270513 писал(а):

Здесь точно линейное, а не константное?

Разумеется константное! Опечатку исправил.

mihaild в сообщении #1270513 писал(а):

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

То есть, например, класс TreeSet из коллекций языка Java?

mihaild в сообщении #1270513 писал(а):

Вы какие оценки всё-таки хотите? И в худшем или в среднем случае?

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

mihaild в сообщении #1270513 писал(а):

просто вместо значения храните контейнер значений

То есть деревья ломаются, если есть одинаковые элементы?

[mihaild]

B@R5uk в сообщении #1270519 писал(а):

То есть, например, класс TreeSet из коллекций языка Java?

Это надо смотреть, что у него внутри (скорее всего да, какое-нибудь классическое дерево).

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

B@R5uk в сообщении #1270519 писал(а):

То есть деревья ломаются, если есть одинаковые элементы?

В принципе ничто не мешает в дереве хранить и узлы с одинаковым ключом (требуем чтобы значения в правом поддереве были больше либо равны значению в узле, а не строго больше). Позволяет ли это делать конкретная реализация - зависит от реализации.

[B@R5uk]

mihaild, спасибо за советы. TreeSet оказывается как и любое множество из пакета коллекций Java допускает только уникальные элементы. Проблему решил так: сначала сравниваю хэши объектов, затем, если они совпадают, сравниваю по очереди все ключевые поля данных. Так достигается баланс между соблюдением требований и быстродействием. В итоге, подзадача решена, и задача, где это всё используется тоже заработала. Ещё раз, большое СПАСИБО.