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

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

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

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

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

eNoseНе особо вдаваясь в теорию:
shorewallВ каждом узле дерева хранить(и соотвественно обновлять) счетчик - количество элементов хранимых в левом(относительно заданного узла) поддереве. вы сами себе ответили - журтвуете памятью :)

Накладные расходы естественно будут. Но при хранении в списке "больших" объектов "удельная" стоимость хранения будет не велика.

Если рассматривать линейные структуры данных, то их всего то: динамический массив, связный список. Статичный массив не подходит.

При работе с ними используем следующие методы: get, insert, delete, update. При этом для того что-бы выполнить методы необходимо сначала опредилить позицию, ну скажем через метод pos.

Стоимость операций:
1) для диначного массива
pos = 0
get = 0
insert = Cost(создание нового массива) + Cost(копирование в него прежнего содержимого)
delete = Cost(создание нового массива) + Cost(копирование в него прежнего содержимого)

2) для связного списка
pos = Cost(цикл длиной в среднем n/2)
get = pos
insert = pos
delete = pos

MasterZiv
shorewall wrote:

> А что если в качестве линейной структуры взять бинарное сбалансированное
> дерево(например АВЛ-дерево). В каждом узле дерева хранить(и

Так есть уже и такие структуры, map, hashmap, hashtable.



map, hashmap, hashtable - суть хранилище пар(характеристика, занчение). Я же говорю о линейном списке, где главное это доступ к элементу по номеру.

В топике не совсем похоже не совсем понятна идея.

Топик следует читать как: Реализация динамического массива поверх бинарного дерева

mayton,

По памяти:
cost(all) = равны количесто_узлов * размер_узла
cost(узла) = два указателя, один байт для высоты(требуется для АВЛ-дерева), четыре байта для счетчика(т.е. максимальное количество элементов = 2^32)

если принять размеры указателя за 4 байта, то cost(all) = количество_узлов * (2*4 + 1 + 4) = количество_узлов*13

поскольку в сбалансированном дереве количество узлов(при большом n) ~ 2^(log(n) - 1), то

cost(all) = 13 * 2^(log(n)-1), затраты на дерево

если данные дополнительно объединить в односвязный список, то общая стоимость возрастет на 4 на каждый элемент и составит: 4*n + 14*(2^(log(n)-1))

По времени: поскольку это бинарное сбалансированное дерево то стоимость всех операций O(log(n)).

mayton,

Ну дык не зная как устроена куча нету и возможности учитывать ее особенности.

Данная идея у меня родилась в связи с необходимостью хранения результатов запроса к БД. При этом размер строки могут быть достаточно велики, по сравнению с накладными расходами на поддержание структуры данных. Обычные неплотные динамические массивы(ArrayList из Java) не совсем устраивают в том плане что при большом количестве элементов стоимость операций insert/delete (для ArrayList add/remove) достаточно высока.

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

Подкинули ссылку на "Декартово дерево".

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

MasterZiv
shorewall wrote:

> map, hashmap, hashtable - суть хранилище пар(характеристика, занчение).

Применение глагола "суть" тут неуместно. Не говори то, чего не понимаешь
смысл.

> Я же говорю о линейном списке, где главное это доступ к элементу по номеру.

в линейных списках НЕТ доступа по номеру. Есть только последовательный
доступ. А map как раз и есть дерево идентификаторов, хранящее
в листах значения (всю запись), что ты и предлагал сделать.
В map get/insert/delete/update - O( log(n) ). (операции update на
самом деле нет, либо это GET, либо это delete+insert).

Так что что тебе ещё нужно, я не понимаю.


Хоть и оффтоп.

Из Яндекс -> Русский язык.

Морфемно-орфографический словарь
суть/1 (сущность)

Словарь русских синонимов и сходных по смыслу выражений
Суть, сущность , существо, естество, главное, душа, сила, соль, секрет, ядро, экстракт, эссенция, квинтэссенция; центр, фокус; остов, скелет. Польза отечества у него всегда на первом плане стояла. Не в том дело. Правосудие есть душа закона. Ср. Главный Содержание вещество главный содержание.

По поводу того, что мне было нужно: Реализация динамического массива поверх бинарного дерева

Декартово дерево позволяет это сделать, засим тема закрыта.

mayton,

Декартово дерево .

Неявные декартовы деревья

Неявное декартово дерево - это простая модификация обычного декартового дерева, которая, тем не менее, оказывается очень мощной структурой данных. Фактически, неявное декартово дерево можно воспринимать как массив, над которым можно реализовать следующие операции (все за O (log N) в режиме онлайн):

* Вставка элемента в массив в любую позицию
* Удаление произвольного элемента
* Сумма, минимум/максимум на произвольном отрезке, и т.д.
* Прибавление, покраска на отрезке
* Переворот (перестановка элементов в обратном порядке) на отрезке

Ключевая идея заключается в том, что в качестве ключей key следует использовать индексы элементов в массиве. Однако явно хранить эти значения key мы не будем (иначе, например, при вставке элемента пришлось бы изменять key в O (N) вершинах дерева).

Заметим, что фактически в данном случае ключ для какой-то вершины - это количество вершин, меньших неё. Следует заметить, что вершины, меньшие данной, находятся не только в её левом поддереве, но и, возможно, в левых поддеревьях её предков. Более строго, неявный ключ для некоторой вершины t равен количеству вершин cnt(t->l) в левом поддереве этой вершины плюс аналогичные величины cnt(p->l)+1 для каждого предка p этой вершины, при условии, что t находится в правом поддереве для p.

Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое поддерево - накапливаемая сумма не меняется, а если идём в правое - увеличивается на cnt(t->l)+1.

Мой предыдущий ответ на это

mayton
Не знаю как вам а мне чесно говоря непонятно, каким образом... .

Первноначально же меня просто интересовала сама возможность реализации "Динамического массива поверх бинарного дерева" не болле того.