Название темы лучше читать как - "Реализация динамического массива поверх сбалансированного бинарного дерева"

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

Обе эти структуры данных реализуют одну и ту же линейную структуру, т.е. структуру на которой определены позиционные операции get/insert/delete/update.

А что если в качестве линейной структуры взять бинарное сбалансированное дерево(например АВЛ-дерево). В каждом узле дерева хранить(и соотвественно обновлять) счетчик - количество элементов хранимых в левом(относительно заданного узла) поддереве.  Данные будут распологаться в листьях, при этом элементы распологающиеся слева от узла будут иметь номера меньше чем узлы распологающиеся справа. Поскольку дерево сбалансировано, то при операциях insert/delete необходимо будет обновить счетчики не более чем в log(n) количестве узлов.

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

Стоимость всех операций get/insert/delete/update пропорциональна log(n).
  
  
  

Это сообщение отредактировал(а) pathfinder - 3.3.2010, 22:22

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

Кроме того, в деревьях можно дополнительно кучу всего другого выполнять. Особенно интересны неявные декартовы деревья, которые за то же логарифмическое время помимо обычных минимумов на отрезке / суммы на отрезке / прибавление(присвоение) на отрезке, также такие необычные штуки как изменение порядка элементов в подотрезке на противоположный / удаление(вставка) подотрезка / перестановка подотрезков.

Можно ссылку на такие реализации, а то в стандартной библиотеке Java ничего подобного нету

Добавлено @ 22:33
To maxdiver огромное спасибо.

Тему можно закрывать.

Это сообщение отредактировал(а) pathfinder - 3.3.2010, 22:33

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

Насчет логорифмичности операции доступа - это так, но на списках очень часта операция последовательного доступа к элементам, поэтому если построить сбалансированное декартово дерево поверх двусвязного списка(если прохождение последовательности будет в обработном направлении) тогда доступ к первому элементу последовательности log(n), к последующим элементам = 0, причем можно кэшировать последний элемент(вмысле его индекс I) и проводить оптимизацию - если будеь запрашиваться элемент с индексом J, такой что |I - J| < log(n), будет дешевле пробежаться по двусвязному списку до элемента J, нежели искать его через дерево.

Примеры последовательного доступа - отображение в графических элементах пользовательского интерфейса типа Список/Таблица/КобмоБокс данных из запроса к базе данных.

Это сообщение отредактировал(а) pathfinder - 4.3.2010, 16:14