Поиск пути
Алгоритм 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, если такого узла нет. Таким образом, нам остаётся найти все эти пути (обходом поддерева от возвращённой вершины).
