-
Notifications
You must be signed in to change notification settings - Fork 7
Search
-
The access trie is traversed according to the leading characters in the query string. Initiallythe current object is the root of the access trie and the current depth i is 1.
While the current object is a trie node t of depth i ≤ n,
(a) Update the current object to be the node or container pointed to by the cith elementof t’s array p, and
(b) Increment i.
If the current object is a trie node t of depth i = n + 1, the current object is the objectpointed to by the empty-string pointer, which for simplicity can be regarded as a container of either zero or one records.
Otherwise, if the current object is null the string is not in the burst trie, and searchterminates
-
The current object is a valid container. If i ≤ n, use the remaining characters ci ··· cn tosearch the container, returning the record if found or otherwise returning null. Otherwise,the current object is a container of zero or one records that is pointed to by the empty-string pointer (since the entire string was consumed by traversal of the trie), which shouldbe returned