Nicolai Baron von Hoyningen-Huene

Digital Search Trees -- Average case analysis of digital search trees and tries

Abstract

A very common problem in computer science is to search for the appearance of a string inside a text. There exist algorithms that use suffix trees, which are often implemented as digital trees to optimize the performance of the search. In this article some properties of those data structures are analyzed, which can be used to calculate the average performance and space complexity of algorithms using digital trees.