Premium
An efficient implementation of trie structures
Author(s) -
Aoe JunIchi,
Morimoto Katsushi,
Sato Takashi
Publication year - 1992
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380220902
Subject(s) - trie , computer science , array data structure , data structure , algorithm , programming language
A new internal array structure, called a double‐array , implementing a trie structure is presented. The double‐array combines the fast access of a matrix form with the compactness of a list form. The algorithms for retrieval, insertion and deletion are introduced through examples. Although insertion is rather slow, it is still practical, and both the deletion and the retrieval time can be improved from the list form. From the comparison with the list for various large sets of keys, it is shown that the size of the double‐array can be about 17 per cent smaller than that of the list, and that the retrieval speed of the double‐array can be from 3–1 to 5–1 times faster than that of the list.