Self-Adjusting of Ternary Search Tries Using Conditional Rotations and Randomized Heuristics.

A ternary search trie (TST) is a highly efficient dynamic dictionary structure applicable for strings and textual data. The strings are accessed based on a set of access probabilities and are to be arranged using a TST. We consider the scenario where the probabilities are not known a priori and is time-invariant. Our aim is to adaptively restructure the TST so as to yield the best access or retrieval time. Unlike the case of lists and binary search trees where numerous methods have been proposed, in the case of the TST, currently, the number of reported adaptive schemes are few. In this paper we consider various self-organizing schemes that were applied to binary search trees and apply them to TSTs. Three new schemes, which are the splaying, the conditional rotation and the randomization heuristics, have been proposed, tested and comparatively presented. The results demonstrate that the conditional rotation heuristic is the best when compared with other heuristics that are considered in the paper. [ABSTRACT FROM PUBLISHER]