Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2597
Type: Relatório
Title: Optimal binary search trees with costs depending on the access paths
Author(s)/Inventor(s): Szwarcfiter, Jayme Luiz
Navarro, Gonzalo
Baeza-Yates, Ricardo
Oliveira, Joísa de S
Ziviani, Nívio
Abstract: We 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.
Keywords: Algoritmos
Árvores de busca binária
Funções de geração
Algorithms
Binary search trees
Generatiing functions
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 2399
Issue Date: 31-Dec-1999
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: SZWARCFITER, 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)
URI: http://hdl.handle.net/11422/2597
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.