On the number of string lookups in BSTs (and related algorithms) with digital access

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/87918

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor.author	Frias Moya, Leonor
dc.date	2009-05
dc.identifier.citation	Frias, L. "On the number of string lookups in BSTs (and related algorithms) with digital access". 2009.
dc.identifier.uri	http://hdl.handle.net/2117/87918
dc.language.iso	eng
dc.relation	LSI-09-14-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	BST
dc.subject	TST
dc.subject	Strings
dc.subject	Memory hierarchies
dc.subject	Analysis of algorithms
dc.title	On the number of string lookups in BSTs (and related algorithms) with digital access
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	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.