An Efficient Digital Search Algorithm by Using a Double-Array Structure.

An efficient digital search algorithm is presented in this paper by introducing a new internal array structure, called a double- array, that combines the fast access of a matrix form with the compactness of a list form. Each arc of a digital search tree, called a DS- tree, can be computed from the double-array in O(1) time; that is to say, the worst-case time complexity for retrieving a key becomes O(k) for the length k of that key. The double-array is modified to make the size compact while maintaining fast access and algorithms for retrieval, insertion and deletion are presented. Suppose that the size of the double-array is n + cm, n being the number of nodes of the DS-tree, m being the number of input symbols, and c a constant depending on each double-array. Then it is theoretically proved that the worst-case times of deletion and insertion are proportional to cm and cm², respectively, independent of ii. From the experimental results of building the double-array incrementally for various sets of keys, it is shown that the constant c has an extremely small value, ranging from 0.17 to 1.13. [ABSTRACT FROM AUTHOR]