Developing.ru

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

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

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

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

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

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

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