Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2597
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSzwarcfiter, Jayme Luiz-
dc.contributor.authorNavarro, Gonzalo-
dc.contributor.authorBaeza-Yates, Ricardo-
dc.contributor.authorOliveira, Joísa de S-
dc.contributor.authorZiviani, Nívio-
dc.date.accessioned2017-08-04T13:14:30Z-
dc.date.available2017-08-06T03:00:16Z-
dc.date.issued1999-12-31-
dc.identifier.citationSZWARCFITER, J. L. et al. Optimal binary search trees with costs depending on the access paths. Rio de Janeiro: NCE, UFRJ, 1999. 19 p. (Relatório Técnico, 23/99)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/2597-
dc.description.abstractWe describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(nᵏ+²) and O(nᵏ+¹ ), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating funcions, we present an exact analysis of the number of steps performed by the algorithms.en
dc.languageengpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmospt_BR
dc.subjectÁrvores de busca bináriapt_BR
dc.subjectFunções de geraçãopt_BR
dc.subjectAlgorithmsen
dc.subjectBinary search treesen
dc.subjectGeneratiing functionsen
dc.titleOptimal binary search trees with costs depending on the access pathsen
dc.typeRelatóriopt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOpt_BR
dc.citation.issue2399pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
23_99_000611348.pdf857,28 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.