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. Articles by others on the same topic
There are currently no matching articles.