Классика баз данных - статьи

       

Поиск пути


Алгоритм BST-Search(r, k) возвращает вершину xn+1 такую, что:

  • строка s(xn), задаваемая путём S(r,xn), если такая существует, является префиксом искомой либо совпадает с ней,
  • искомая строка k является префиксом строки s(xn+1) либо совпадает с ней.

Т.е. выполняется неравенство: s(xn)≤k≤s(xn+1), где под операцией A≤B понимается то, что A является префиксом B или совпадает с ней.

Процедура получает на вход указатель x на корневой узел поддерева, а также строку k. Промежуточные результаты поиска сохраняются в стек S. В процедуре также используется функция y=L(x,c), которая находит среди исходящих рёбер вершины x ребро, помеченное символом c, и возвращает узел y, в который оно ведёт, либо NIL, если такого ребра нет. Такую функцию можно реализовать, например, бинарным поиском, т.к. массив рёбер упорядочен. Также используется функция Cut(p,s), которая возвращает строку, получающуюся из s удалением префикса p.

Алгоритм достаточно компактен, поэтому приведём его здесь: BST-Search(x, k, S) 1: Push(S, x) 2: if external(x) then

3: Disk-Read(J(x)) 4: return BST-Search(J(x), k, S) 5: endif

6: if not Is-Prefix(prefix(x), k)) then

7: if Is-Prefix(k, prefix(x)) then

8: return x

9: else

10: return NIL 11: endif

12: else

13: s ← Cut(prefix(x), k) 14: if Empty(s) then

15: return x

16: elseif L(x,s[1]) = NIL

17: return NIL

18: else

19: return BST-Search(L(x,s[1]), Cut(s[1], s), S) 20: endif

21: endif

Процедура возвращает такой узел x, что все пути, ведущие из корня в final-вершины и содержащие x, задают строки, для которых искомая строка является префиксом, либо NIL, если такого узла нет. Таким образом, нам остаётся найти все эти пути (обходом поддерева от возвращённой вершины).



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







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий