Delphi - сбориник статей

       

Сравнительный анализ


Проведем небольшой сравнительный анализ различных вариантов представления дерева с точки зрения качества реализации рассмотренных в статье операций. Будем считать, что операция реализуется хорошо, если количество запросов для реализации не зависит от характеристик дерева (количества узлов, глубины и др.). Если же зависимость есть, то будем считать, что операция реализуется плохо.

№ п/п Операция Варианты дерева

Простое Фиксированное Неограниченное
1 Вывод дерева плохо хорошо плохо
2 Добавление узла хорошо хорошо хорошо
3 Удаление узла плохо хорошо хорошо
4 Вхождение узла в поддерево плохо хорошо хорошо
5 Изменение родителя хорошо хорошо хорошо

Из таблицы видно, что простое дерево слабо годится для работы с ним на уровне БД. Только две операции из пяти будут выполняться эффективно. Но так как для изменения родителя нужно сначала определить, допустимо ли такое изменение, а операция проверки вхождения узла в поддерево также реализуется плохо, то остается одно лишь добавление нового узла. Для задачи, в которой в основном выполняется только операция добавления нового узла, а остальные операции выполняются крайне редко, такой вариант подойдет. Но я как-то слабо могу себе представить такую задачу (ведение древовидных логов что ли?). Так что применять простое дерево имеет смысл для сравнительно небольших деревьев, которые выгружаются из БД в какие-либо компоненты (например, TTreeView), а вся дальнейшая работа производится уже на уровне компонентов.

Для фиксированного дерева все операции реализуются хорошо. Так что, если по условиям задачи допустимо ограничить максимальную глубину дерева, то, возможно, это будет лучший вариант (если не будет придуман способ хорошей реализации вывода неограниченного дерева). Имейте в виду, что максимальную глубину для фиксированного дерева можно задать и побольше, чем 5. Можно взять с запасом. Главное -- чтобы глубину можно было хоть как-то ограничить.

Ну, а если таких ограничений задать невозможно (или если скорость вывода не критична), то можно воспользоваться вариантом неограниченного дерева.



Содержание раздела