Game Development Reference
In-Depth Information
Trie
A common data structure used for storing predictive text is a trie is a type of tree (term
appears to come from the word re
trie
val), it's not the most compact way to store autocom-
plete data, but it has good performance and it is not difficult to implement.
Every node in a trie may have up to n nodes under it, where n is the number of characters
thatmaysucceedanygivennode,forexample,insomelimitedimplementationsitcouldbe
up to twenty six, the number of characters in the English alphabet, however, no limitation
shouldbeenforced,afterall,wemaywanttosupportalphanumericcharacters,symbols,or
other alphabets.
Figure
55
- A visual representation of a trie.
Thetrieholdsarootnode,aninsertionfunctionandsomequeryfunctions.Nodesholdfour
members, first the character they represent, next a flag that identifies as a node as a word,
children nodes and an index that we will use while iterating through the different children.
This description of a trie's node can be defined by the following code.
class node
