VietMX Staff asked 3 years ago
- The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers). This is simple but wasteful in terms of memory (as the structure wastes space storing null pointers).
// trie node class TrieNode { public TrieNode[] children = new TrieNode[ALPHABET_SIZE]; // isEndOfWord is true if the node represents // end of a word public bool isEndOfWord; public TrieNode() { isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = null; } }; - An alternative implementation represents a node as a triple (symbol, child, next) and links the children of a node together as a singly linked list: child points to the node’s first child, next to the parent node’s next child:
function Trie(parent, prev, key, value) { if (key !== void 0) this.key = key; // single-character key if (value !== void 0) this.value = value; // user-defined value if (prev) prev.next = this; // next sibling node else if (parent) parent.child = this; // first child node } - Another alternative in order to avoid the use of an array of 256 pointers (ASCII), is to store the alphabet array as a bitmap of 256 bits representing the ASCII alphabet, reducing dramatically the size of the nodes.
