Представление списков в виде БД

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

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

В каждом узле р, не являющемся листом, алгоритм определяет по значениям r и ListCount(p), находится ли нужный лист в левом или в правом поддереве. Если лист в левом поддереве, то поиск ведется по этому поддереву без изменения значения r, а если в правом, то перед поиском по этому поддереву значение r уменьшается на ListCount(p). Рассмотрим реализацию изложенного способа на примере. Пусть дан список элементов (рис. 21). На рис. 22.а и 22.б приведены два дерева, удовлетворяющие требованиям алгоритма.

Рис. 21 – Список элементов для поиска

Рис. 22.а – Первый вариант дерева с элементами списка

Рис. 22.б – Второй вариант дерева с элементами списка

Код алгоритма нахождения к -ого элемента списка

Здесь Tree – указатель на корень дерева; ListCount(p) – счетчик числа листьев, связанных с узлом, на который указывает рабочий указатель р; r – рабочая переменная; Find – указатель найденного элемента; Left(p) и Right(p) – указатели на левого и правого сыновей текущего узла.

Эффективность поиска с помощью данного алгоритма растет с увеличением числа элементов списка. Для 1000 элементов достаточно 10 сравнений.

Дата добавления: 2015-07-16