Гибрид массива и списка
Вопрос по структурам данных. Кто нибудь знает или может быть видел где нибудь структуру, позволяющую реализовать массив элементов, с возможностью быстрой вставки (добавления) и удаления элемента в любом месте массива и с возможностью быстрого доступа по индексу за время О(log2(n)), или быстрее? Естественно, структура должна быть самобалансирующейся за такое же время или быстрее.
Массив указателей не подходит?
Не подходит. Один из вариантов использовать двоичные деревья. Но их надо балансировать...
Честно сказать, не представляю как к элементу дерева можно обратиться по индексу.и с возможностью быстрого доступа по индексу
На самом деле все достаточно просто, нужна небольшая модификация - использовать динамические ключи вместо фиксированных. В статье про неявное декартовое дерево описан один из вариантов реализации подобной структуры (см. http://e-maxx.ru/algo/treap).
-
- Сообщения: 0
- Зарегистрирован: 21 окт 2012, 22:31
- Откуда: Россия
- Контактная информация:
Об этом и об востановление экономики , протоколы заседаний фрг и об Банк Англии планирует повышение процентной ставки
на http://rus-crediter.ru/
У нас всегда интригующие новости.
на http://rus-crediter.ru/
У нас всегда интригующие новости.