A trie node needs a terminal flag as well as its children: a stored word can also be the prefix of a longer stored word.Index zero denotes
TYPE Trie = POINTER TO Node;
Node = RECORD
terminal: BOOLEAN;
child: ARRAY 26 OF Trie
END;a, index 25 denotes z; null pointers denote absent branches. The set represented by a nonnull node consists of the empty string if terminal is true, together with every child's words prefixed by that child's letter. Represent the empty set by NIL. The singleton containing the empty string instead has a terminal root and no children.The declarations alone do not force a unique representation. A nonterminal leaf, or a whole branch without terminal descendants, contributes no word. To obtain uniqueness up to pointer addresses, impose a representation invariant: the structure is a finite rooted tree, and each allocated node lies on a path to a terminal node. Then precisely the prefixes of stored words exist, all flags are determined, and the empty set has only the
NIL representation. The insertion procedures below preserve this invariant when starting with such a trie.For the paper's 26-letter alphabet, use the Oberon Both cases of a letter map to the same uppercase letter before subtraction, so the result lies in
CAP operation and contiguous character codes:PROCEDURE Index(c: CHAR): INTEGER;
BEGIN
RETURN ORD(CAP(c)) - ORD("A")
END Index;0..25. This relies on the ordinary Latin A–Z and a–z character encoding used by Oberon; it is not a Unicode case-folding algorithm. The stipulated letter-only precondition avoids any need to reject punctuation.Perform a depth-first traversal, retaining the path's letters in a buffer. A terminal node must be printed before its children, so a word precedes its proper extensions in lexicographic order.The recursion invariant is that
VAR word: ARRAY N OF CHAR;
PROCEDURE Visit(t: Trie; depth: INTEGER);
VAR j, c: INTEGER;
BEGIN
IF t # NIL THEN
IF t.terminal THEN
j := 0;
WHILE j < depth DO
Out.Char(word[j]); j := j+1
END;
Out.Ln
END;
c := 0;
WHILE c < 26 DO
IF t.child[c] # NIL THEN
word[depth] := CHR(ORD("a")+c);
Visit(t.child[c], depth+1)
END;
c := c+1
END
END
END Visit;
PROCEDURE PrintTrie(t: Trie);
BEGIN
Visit(t, 0)
END PrintTrie;word[0..depth) spells the path to t. The child loop's loop invariant says children with indices below c have been completely printed. Each edge appends its lowercase label; each terminal flag prints exactly one represented string. All words therefore appear once, in lowercase. The output loop prints precisely the prefix of length depth; no terminating zero needs storing in this buffer.An
N-character buffer suffices for words of length at most N. At depth N there can be no child, so word[N] is never accessed. A terminal root prints an empty line; a NIL root prints nothing. The running time is linear in allocated nodes plus the number of printed characters, since the alphabet size is fixed at 26.Allocate nodes only as required, explicitly initializing every field:Here
PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
NEW(t); t.terminal := FALSE; c := 0;
WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;
PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
IF t = NIL THEN Make(t) END;
IF s[i] = 0X THEN
t.terminal := TRUE
ELSE
AddTail(t.child[Index(s[i])], s, i+1)
END
END AddTail;
PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
AddTail(t, s, 0)
END Add;0X is the zero character, and s must contain its terminator within its array bounds. Make establishes that the first c child fields are NIL as its loop invariant. Passing t by reference lets the base allocation replace a missing root or child pointer.For correctness, use induction on the number of characters before the terminator. At length zero, setting
terminal adds exactly the empty suffix. Otherwise the chosen child stores exactly words with the required next letter, and the induction hypothesis adds the remaining suffix while preserving all other words. Thus the resulting set is the old set union the supplied word, ignoring case. Repeated insertion changes no word membership. A newly allocated path reaches the newly terminal node, preserving the canonical representation invariant after the procedure finishes. The running time is for a word of length , using call stack space without optimization.A directly self-recursive procedure can be replaced by a simple loop when every recursive call is a tail call. This is tail recursion: no operation, including an update or cleanup action, remains to be performed after the call returns. The loop tests the same cases, performs the same nonrecursive work, and replaces the current parameters by the next call's arguments. Argument values must be computed before assignments if their expressions depend on old parameter values; by-reference bindings also need preserving.
A traversal that must return to explore another child is not in this form. It can still be implemented iteratively with an explicit stack, but that is a different transformation and generally retains the deferred work.
AddTail in part (d) is already tail-recursive: the recursive call is the final action of its branch. The following loop follows a separate cursor so that the caller's root pointer is preserved:PROCEDURE AddIter(VAR t: Trie; s: ARRAY OF CHAR);
VAR u: Trie; i, c: INTEGER;
BEGIN
IF t = NIL THEN Make(t) END;
u := t; i := 0;
WHILE s[i] # 0X DO
c := Index(s[i]);
IF u.child[c] = NIL THEN Make(u.child[c]) END;
u := u.child[c]; i := i+1
END;
u.terminal := TRUE
END AddIter;u points to the node reached by the first i letters, all necessary nodes along that path exist, and no previously terminal node has lost its flag. Each iteration advances one character. At the terminator, marking u inserts exactly the desired string. Using t := t.child[c] as the cursor update would instead overwrite the caller's root through the VAR parameter. This version has running time and constant auxiliary space, apart from newly allocated nodes in the result. Articles by others on the same topic
There are currently no matching articles.