Trie and Tree-Based Data Structures for Efficient String Searching

This paper presents a comparative study of trie-based and tree-based data structures for efficient string searching, with applications in text processing, information retrieval, and database indexing. This paper analyzes standard tries, binary search trees, balanced trees, and suffix trees in terms of time complexity, space usage, and operational characteristics. This paper introduces a Hybrid Trie–Tree Index that stores the first k characters of each string in a trie and delegates the remaining suffix to a secondary container at depth k. This design reduces construction overhead while preserving efficient prefix-based navigation. Experimental evaluation is conducted on datasets of increasing scale, including a controlled 68-word vocabulary, a 200,000-word dataset, and a 1.5 million-word dataset. Results show that the hybrid structure achieves significantly faster build times compared to a standard trie, while search performance depends on the size of suffix containers. A parameter study varying the prefix depth k demonstrates a clear trade-off between construction efficiency and query latency. Smaller k values reduce build time but increase search overhead, while larger k values improve search performance at the cost of deeper trie expansion. These findings highlight the importance of tuning k based on dataset characteristics and application requirements.