Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Frias, L.
Tipus d'activitat
Document cientificotècnic
Data
2009-05
Codi
LSI-09-14-R
Repositori
http://hdl.handle.net/2117/87918 Obrir en finestra nova
Resum
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 character- ize a variant proposed in this paper to reduce f...
Citació
Frias, L. "On the number of string lookups in BSTs (and related algorithms) with digital access". 2009.
Paraules clau
Bst, Tst, Strings, Memory Hierarchies, Analysis Of Algorithms

Participants

  • Frias Moya, Leonor  (autor)

Arxius