请输入您要查询的字词:

 

单词 Trie
释义

trie


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 wordretrieval, 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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the length of the string being looked up.

If a trie is to store some set of strings SΣ* (where Σ 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 Σ. Any edge leading to a leaf node is labelled by $ (some symbol not in Σ). For every string sS, there is a path from the root of the trie to a leaf, the labels of which when concatenated form s++$ (where ++ 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 S.

Example

Suppose we wish to store the set of strings S:={alpha,beta,bear,beast,beat}. The trie that stores S would be

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:40:10