5. Древовидные таблицы
 
   5.1.Сравнение табличной и древовидной структур
 

Табличное представление данных находит самое широкое применение в информационных системах. Для таких систем ocновными операциями являются поиск и выборка нужной информации. Вычислительная сложность алгоритмов поиска, как мы знаем, зависит от того, является ли таблица упорядоченной или . Для неупорядоченных таблиц она порядка О(n), а для упорядоченных — порядка O(log₂n). Если число элементов в таблице велико, то в большинстве случаев можно применять неупорядоченные таблицы. Однако большие объемы данных вынуждают создавать упорядоченные таблицы.

Оценим вычислительную сложность алгоритма создания таблицы, упорядоченной по возрастанию ключей. Алгоритм основан на том, что очередная запись таблицы помещается не простор конец таблицы, а сразу же в нужное место. Если ключ новой записи больше ключа последней записи в таблице, то новая запись включается в конец таблицы. В противном случае все записи, ключ которых больше ключа новой записи, сдвигаются на одну позицию к концу таблицы, и новая запись помещается на место последней сдвинутой записи. Таким образом, основными операциями алгоритма создания упорядоченной таблицы являются операции сравнения и перемещения. В наилучшем случае, когда при создании таблицы записи поступают в порядке возрастания ключей, для каждой записи тратится по одной операции сравнения и перемещения. В наихудшем случае, когда исходные записи упорядочены в об-ратном порядке, включение каждой i-й записи (i = 1,2, ....n) требует i операций сравнения и (i + 1) операций перемещения. Общее количество операций сравнения для n записей составит:

C= сумма от I=1 до n-1 от I=0.5(n²-n), а для операций перемещения
М= сумма от I=1 до n-1 jn (I+1) = 0.5(n²-n)+(n-1)

Общее число операций сравнения и перемещения будет равно С + М = n² — 1, т.е. порядка О(n²), такого же порядка будет и в среднем.

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

Вычислительная сложность поиска в упорядоченной таблице O(log₂n) такая же, как и в сбалансированном двоичном дереве поиска. Однако создание бинарного дерева поиска имеет сложность порядка O(nlog₂n), а включение и удаление элементов — O(log₂n), т.е. по этим показателям сбалансированное бинарное дерево поиска имеет значительное преимущество перед, упорядоченными таблицами.