| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Реализовать список поверх бинарного дерева. |
| Автор: pathfinder 3.3.2010, 13:46 |
| Название темы лучше читать как - "Реализация динамического массива поверх сбалансированного бинарного дерева" Хорошо известны две структуры данных массив и связный список, которые в некоторм смысле являются антогонистами. В массиве стоимость операции доступа к елементу по номеру мала, стоимость операции вставки/удаления очень высока. Напротив в связном списке стоимость операции доступа к элементу по номеру очень высока, стоимость операции вставки/удаления очень низка. Обе эти структуры данных реализуют одну и ту же линейную структуру, т.е. структуру на которой определены позиционные операции get/insert/delete/update. А что если в качестве линейной структуры взять бинарное сбалансированное дерево(например АВЛ-дерево). В каждом узле дерева хранить(и соотвественно обновлять) счетчик - количество элементов хранимых в левом(относительно заданного узла) поддереве. Данные будут распологаться в листьях, при этом элементы распологающиеся слева от узла будут иметь номера меньше чем узлы распологающиеся справа. Поскольку дерево сбалансировано, то при операциях insert/delete необходимо будет обновить счетчики не более чем в log(n) количестве узлов. Дополнительно можно объединить все листья в связный список что позволит выполнять операции последовательного доступа очень быстро, т.к. при этом необходимо будет найти лишь первый элемент в последовательности. Стоимость всех операций get/insert/delete/update пропорциональна log(n). |
| Автор: maxdiver 3.3.2010, 22:20 |
| Ну да, это известный путь. Всяческие деревья - это среднее между массивом и списком, расплатой за что является логарифмическое время на обеих основных операциях вместо константного. Ну собственно во многих библиотеках и даже языках "массивы" именно так и хранятся - на деревьях. Кроме того, в деревьях можно дополнительно кучу всего другого выполнять. Особенно интересны неявные декартовы деревья, которые за то же логарифмическое время помимо обычных минимумов на отрезке / суммы на отрезке / прибавление(присвоение) на отрезке, также такие необычные штуки как изменение порядка элементов в подотрезке на противоположный / удаление(вставка) подотрезка / перестановка подотрезков. |
| Автор: pathfinder 3.3.2010, 22:25 | ||
Можно ссылку на такие реализации, а то в стандартной библиотеке Java ничего подобного нету Добавлено @ 22:33 To maxdiver огромное спасибо. Тему можно закрывать. |
| Автор: maxdiver 4.3.2010, 10:37 |
| Обычно это в интерпретируемых языках, - в императивных программист сам решает, какую структуру данных выбрать. |
| Автор: pathfinder 4.3.2010, 11:41 | ||
Насчет логорифмичности операции доступа - это так, но на списках очень часта операция последовательного доступа к элементам, поэтому если построить сбалансированное декартово дерево поверх двусвязного списка(если прохождение последовательности будет в обработном направлении) тогда доступ к первому элементу последовательности log(n), к последующим элементам = 0, причем можно кэшировать последний элемент(вмысле его индекс I) и проводить оптимизацию - если будеь запрашиваться элемент с индексом J, такой что |I - J| < log(n), будет дешевле пробежаться по двусвязному списку до элемента J, нежели искать его через дерево. Примеры последовательного доступа - отображение в графических элементах пользовательского интерфейса типа Список/Таблица/КобмоБокс данных из запроса к базе данных. |
