Computing and Information Technology Interactive Digital Educational Library


Planet Math Computer Science  >
Planet Math Computer Science Collection >

Please use this identifier to cite or link to this item:

Title: trie
Issue Date: 20-Feb-2004
Publisher: PlanetMath
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

Files in This Item:

File SizeFormat

All items in DSpace are protected by copyright, with all rights reserved.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback