Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/87918

On the number of string lookups in BSTs (and related algorithms) with digital access
Frias Moya, Leonor
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
Binary search trees and quicksort are examples of comparison-based data structure and algorithm respectively. Comparison-based data structures and algorithms can be can be augmented so that no redundant character comparisons are made. Unnoticed, this approach also avoids looking up the string in some nodes. This paper haracterizes analytically the number of string lookups in so-augmented BSTs, quicksort and quickselect. Besides, we also characterize a variant proposed in this paper to reduce further the number of string lookups.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
BST
TST
Strings
Memory hierarchies
Analysis of algorithms
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Frias Moya, Leonor; Petit Silvestre, Jordi
Frias Moya, Leonor; Petit Silvestre, Jordi; Roura Ferret, Salvador
Frias Moya, Leonor; Roura Ferret, Salvador