Any database that stores strings needs a data structure to handle searching and sorting. Fast and efficient algorithms for this purpose are discussed and analyzed in the paper "Fast Algorithms for Sorting and Searching Strings," which was published in the Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997, by Jon Bentley and Robert Sedgewick. It has been approved by Professor Arvo, and I have provided him with a copy.
This paper compares the efficiency of binary trees, digital tries, and ternary trees in sorting and searching strings. It also includes several sorting algorithms in C for ternary trees. I plan to implement binary trees and ternary trees in LISP and then to compare their time complexities for searching and sorting, both theoretically and practically. I find the mathematical derivations of complexity and the proofs of the theorems in the paper to be challenging and interesting. The topics of search trees and computational complexity have been covered in CS20.
Back to main page