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

Consultar RECERCAT

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

Título:	On the number of string lookups in BSTs (and related algorithms) with digital access
Autor/a:	Frias Moya, Leonor
Otros autores:	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
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.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -BST -TST -Strings -Memory hierarchies -Analysis of algorithms
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Frias Moya, Leonor

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

Frias Moya, Leonor; Petit Silvestre, Jordi

Frias Moya, Leonor

Frias Moya, Leonor; Roura Ferret, Salvador

Coordinación

Patrocinio