Ответ на »сообщение 643« (Cepгей Poщин)
___________________________
А мне помнится, в Турбо-Паскале, ни-то 5-й, ни-то еще 4-й версии был модуль построения индексных деревьев.
Ни у кого сей раритет не сохранился?

Ответ на »сообщение 644« (Как слышно? Прием!)
___________________________

К сожалению, нет у меня Кнута.
Но тогда что такое балансировка?

В Инете о деревьях с полем RANK для описания индекса элемента, к сожалению, уже я ничего не встречал, описаны были только самые примитивные алгоритмы.
Балансировка дерева (для АВЛ-деревьев) - это операция поддержания минимальной разницы высот правого и левого поддерева. Ключевое поле (для дерева) - это способ однозначной идентификации местоположения элемента внутри дерева. Принципиально две несвязанные вещи. Если возможно однозначно идентифицировать элемент дерева (а для этого можно воспользоваться положением этого элемента относительно начала списка) другим способом, то тогда отпадает необходимость в ключевом поле, но балансировка остается и, в принципе, операции балансировки сводятся к правому (левому) одинарному(двойному) повороту и производятся на основе фактора сбалансированности, который хранится в узле дерева (те не является частью пользовательских данных). Отсюда и глубокомысленный вывод о том, что для самобалансирующихся деревьев наличие ключевого поля необязательно(!!!) (в случае представления линейного списка).
Также, к большому моему сожалению, я не находил книжек Кларка Крейна (Clark Crane), на которого ссылается Кнут в связи с трехсвязными древовидными структурами. Если кто увидит - киньте ссылку, пожалуйста.
Я не про небрежность или лень, я про принципиальные дефекты.
То есть программа разработана и реализована корректно,
но в результате эксплуатации вкрались ошибки в данные ...
Вся фишка состоит в том, что пользователь не может обратиться к внутренним структурам данных, а ошибка в данных пользователя не влияет на алгоритмы поддержания дерева реализованные внутри соответствующего класса.
Вообще говоря, avl деревья очень активно используются в stl, но не, так скажем, не полностью, реально можно еще замутить с прошивкой дерева, к примеру.... Никто, вроде, особых претензий к stl не предъявлял. В Дельфи используется ну о-о-очень редко.

Ответ на »сообщение 641« (matvey)
___________________________
>>> Программа реализации дерева может и должна быть проверена серией тестов

Я не про небрежность или лень, я про принципиальные дефекты.
То есть программа разработана и реализована корректно,
но в результате эксплуатации вкрались ошибки в данные ...

Вообще, мне нравится идея использовать структурные индексы,
как в методе балансированного дерева.
Только вот использовать простейшие схемы не есть гуд, IMHO.

Ответ на »сообщение 641« (matvey)
___________________________
>>> Абсолютно неверное утверждение. Кнут, том 3, гл 6.2.3 , представление линейных списков.

К сожалению, нет у меня Кнута.
Но тогда что такое балансировка?

Ответ на »сообщение 641« (matvey)
___________________________
Не, ну если по-быстрому набросать что попало - ничего, естественно не выйдет, тут действительно ошибки могут стоить дорого Вот и пришли к ответу :) Ни кто не хочет экономить машинное время заказчика за счет своего личного времени.

Ответ на »сообщение 640« (Как слышно? Прием!)
___________________________

>>> для 1000000 элементов доступ по индексу в дереве займет не более 100 операций

Вроде 2 в 20 степени как раз 1000000.
То есть 20 операций.
Или имеется в виду, что там 5 тактов?

Всё правильно, 20 операций, тут я ошибся, сорри.

Ответ на »сообщение 639« (Как слышно? Прием!)
___________________________

>>> в большинстве литературы рассматриваются (уж не знаю по какой причине) деревья, упорядоченные по ключу
Дык, балансировка дерева предусматривает сортировку.
Абсолютно неверное утверждение. Кнут, том 3, гл 6.2.3 , представление линейных списков.

Возможна ситуация, что при одиночной вставке прийдется перетрясти (перебалансировать) полдерева.
Соответственно, полбазы блокировано.
Среднестатистически картина более оптимистична, но всё же постоянная переиндексация ...
Кстати, как бы оценить среднюю величину переиндексации дерева?
Не более одного поворота. Статистические величины много меньше и вероятность поворота составляет около 50% (повернется или нет) :), вероятность вставки без поворота - 0,534, одиночный поворот - 0,232, двойной - 0,232. Продолжительность работы алгоритма log(n)

>>> баги реализации дерева не учитываем
Вот тут-то собака и порылась!
Деревья несут на себе родовое проклятие хрупкости :)
Корень увяз, всей ветке пропасть.
Программа реализации дерева может и должна быть проверена серией тестов, которые гарантируют правильность реализации. Не, ну если по-быстрому набросать что попало - ничего, естественно не выйдет, тут действительно ошибки могут стоить дорого.

Поэтому в СУБД и используются более изощрённые алгоритмы, чем балансированное дерево.
СУБД хранит информацию на дисковых массивах или файлах(что в общем случае приводится к ленте). Соответственно алгоритмы в этом случае используются несколько другие.

Обратите внимание, Дейкстра анализировал структуры более общие, жизненные и богатые возможностями, чем дерево.
Например, алгоритм Дейкстры.
Угу... сложность алгоритма n^2 при использовании фибоначчиевой кучи (читай дерево) уменьшается до n*log(n). Интересное кино...

Ответ на »сообщение 638« (matvey)
___________________________
>>> для 1000000 элементов доступ по индексу в дереве займет не более 100 операций

Вроде 2 в 20 степени как раз 1000000.
То есть 20 операций.
Или имеется в виду, что там 5 тактов?

Ответ на »сообщение 638« (matvey)
___________________________
>>> в большинстве литературы рассматриваются (уж не знаю по какой причине) деревья, упорядоченные по ключу
Дык, балансировка дерева предусматривает сортировку.

Откажусь от своей фразы, что метод хорош для одиночной вставки.
Возможна ситуация, что при одиночной вставке прийдется перетрясти (перебалансировать) полдерева.
Соответственно, полбазы блокировано.
Среднестатистически картина более оптимистична, но всё же постоянная переиндексация ...
Кстати, как бы оценить среднюю величину переиндексации дерева?

>>> баги реализации дерева не учитываем

Вот тут-то собака и порылась!
Деревья несут на себе родовое проклятие хрупкости :)
Корень увяз, всей ветке пропасть.

Поэтому в СУБД и используются более изощрённые алгоритмы, чем балансированное дерево.

PS
Обратите внимание, Дейкстра анализировал структуры более общие,
жизненные и богатые возможностями, чем дерево.
Например, алгоритм Дейкстры.

Ответ на »сообщение 636« (Как слышно? Прием!)
___________________________

Балансированные деревья хорошо работают при добавлении одного элемента.
А вот если требуется добавить список или массив, тут успехов не видно.
Ввиду того, что одиночные добавления редки, а метод сложен
(в тои числе неустойчив к сбоям) он и непопулярен.

Кнут (том 3) Оригинальный алгоритм конкатенации был разработан Кларком А.Крейном. Крейн решил также и более сложную задачу - разделить список на две части. Всё это работает для случая, если все элементы конкатенируемого поддерева больше (меньше) элементов исходного поддерева, но в случае конкатенации упорядоченных массивов накладывается такое же ограничение. В противном случае алгоритмы приведут либо к поэлементной вставке, что медленнее, чем вставка в дерево или к сортировке, вычислительная сложность которой пропорциональна вставке в бинарное дерево, те как ни крути, а выигрыша от массива не получается. Кстати, обратите внимание на то, что Borland рекомендует при вставке большого числа элементов в TList отключать(!!!) сортировку.
Опять же в большинстве литературы рассматриваются (уж не знаю по какой причине) деревья, упорядоченные по ключу. На самом деле в режиме эмуляции динамического массива (списка) ключ не требуется (!!!), а элементы можно описывать при помощи только индекса.
Сложность алгоритмов и повышенный расход памяти являются платой за повышение быстродействия (при обработке больших массивов данных). Устойчивость к сбоям определяется доступностью внутренних структур данных. Если они (ссылки на них) недоступны извне класса реализующего древовидную структуру, то проблем быть не должно (баги реализации дерева не учитываем). Достаточно показательна в этом отношении реализация TVirtualTreeView. Там для работы с элементами дерева используются ссылки на внутренние элементы древовидной структуры, что, действительно, потенциально может привести к очень большим проблемам в приложении.

Ответ на »сообщение 637« (Geo)
___________________________
Хм... Я имел ввиду, что медленнее по сравнению с массивом. Там все же доступ к элементу по смещению получаем сразу же. Что имеет свои плюсы для определенных задач.
Я это понял, но для 1000000 элементов доступ по индексу в дереве займет не более 100 операций, что при современном быстродействии машин может быть не так критично (ну все зависит, конечно, от частоты чтения) ;). Тут также стоит заметить, что доступ по индексу часто используется для полного перебора элементов, но для этой цели прекрасно подходит итератор и при его использовании (на прошитом дереве) потери времени на обходе всего массива элементов будут минимальны по сравнению с доступом по индексу. Кроме того, следует заметить, что правильно спроектированный итератор позволяет сделать полный обход дерева (без пропуска элементов или повторного обращения) при условии удаления элементов во время итерации, а если принять меры к тому, что добавление элементов производится после (до для реверсивного итератора) текущей позиции итерации, то подобная фигня будет наблюдаться и в случае вставки новых элементов.

ЗЫ. На самом деле интересно а что будет если сделать древовидную структуры на основе упорядоченного списка при помощи описания области действия элемента с реализацией этого самого списка на основе бинарного дерева. Вроде как расход памяти должен быть не больше, чем в случае TVirtualTreeView, а быстродействие не меньше при условии очень интересных возможностей доступа к элементам такого дерева.