Гибрид массива и списка

[T42]

Вопрос по структурам данных. Кто нибудь знает или может быть видел где нибудь структуру, позволяющую реализовать массив элементов, с возможностью быстрой вставки (добавления) и удаления элемента в любом месте массива и с возможностью быстрого доступа по индексу за время О(log2(n)), или быстрее? Естественно, структура должна быть самобалансирующейся за такое же время или быстрее.

[Albor]

Массив указателей не подходит?

[T42]

Не подходит. Один из вариантов использовать двоичные деревья. Но их надо балансировать...

[Albor]

и с возможностью быстрого доступа по индексу

Честно сказать, не представляю как к элементу дерева можно обратиться по индексу.

[T42]

На самом деле все достаточно просто, нужна небольшая модификация - использовать динамические ключи вместо фиксированных. В статье про неявное декартовое дерево описан один из вариантов реализации подобной структуры (см. http://e-maxx.ru/algo/treap).

[sriditerrs]

Об этом и об востановление экономики , протоколы заседаний фрг и об Банк Англии планирует повышение процентной ставки
на http://rus-crediter.ru/
У нас всегда интригующие новости.