Keywords:
Tries, Retrieval Trees, Smoothed Analysis, Mealy-type perturbation functions, edit perturbations, star-like perturbation functions, Additive Tree Spanners, NP hardness, Graph approximating spanning Trees, Centrality Approximating spanning Trees,