Planet Math Computer Science >
Planet Math Computer Science Collection >
Please use this identifier to cite or link to this item:
|Issue Date: ||20-Feb-2004 |
|Abstract: ||A ... trie is a digital tree for storing a set of strings in which there is one node for every prefix of every string in the set. The name comes from the word re ... trie val, and thus is pronounced the same as ... tree (which leads to much confusion when spoken aloud). The word retrieval is stressed, because a trie has a lookup time that is equivalent to the length of the string being looked up. If a trie is to store some set of strings ... (where Sigma is an alphabet), then it takes the following form. Each edge leading to non-leaf nodes in the trie is labelled by an element of Sigma. Any edge leading to a leaf node is labelled by ... (some symbol ... not in Sigma). For every string ... , there is a path from the root of the trie to a leaf, the labels of which when concatenated form ... (where concat is the string concatenation operator). For every path from the root of the trie to a leaf, the labels of the edges concatenated form some string in|
|Appears in Collections:||Planet Math Computer Science Collection|
All items in DSpace are protected by copyright, with all rights reserved.