利用者:Yutaochi/translating/トライ木
出典: フリー百科事典『ウィキペディア（Wikipedia）』
トライ（あるいはprefix tree）はコンピュータ科学のデータ構造である順序付き木の一種で，キーが文字列であるような連想配列の実装に用いられる． 二分探索木とは異なり，ノードにキーを格納するのではなく，木構造の中の位置によってキーが何に関連付けられているかを. All the descendants of any one node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that happen to correspond to keys of interest.
トライという単語は英単語 "retrieval"から来ている.このため etymology it is pronounced "tree", although some encourage the use of "try" in order to distinguish it from the more general tree.
In the shown example, keys are listed in the nodes and values below them. Each complete English word has an integer value associated with it. A trie can be seen as a deterministic finite automaton, although the symbol on each edge is often implicit in the order of the branches.
Note that it is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the trie works.)
