Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/1451| Type: | Relatório |
| Title: | Optimal multiway search trees for variable size keys |
| Author(s)/Inventor(s): | Szwarcfiter, Jayme Luiz |
| Abstract: | Dada uma sequência de n chaves de tamanho variável, consideram-se algumas árvores ótimas de busca. A construção de árvores multibifurcadas de busca de custo ótimo, é NP-difícil, embora o problema seja solúvel em tempo pseudo-polinomial 0(n³L) e espaço 0(n²L), onde L é o limite dado para o tamanho da página. Tais árvores de espaço ótimo podem ser obtidas em tempo 0(n³), e espaço 0(n²) enquanto que aos de altura ótima são encontráveis em tempo 0(n²logn) e espaço 0(nlogn). O princípio da monotonicidade não se aplica para os casos acima. A determinação de uma árvore B geral de custo ótimo é um problema também NP-difícil. Contudo, uma árvore B geral de altura 2 e tamanho mínimo de raiz pode ser construída em tempo 0(logn) e espaço 0(n). Além disso, caso o número de chaves na raiz seja fixado em M, a complexidade de tempo aumenta para 0(n²M). Isto responde a uma conjectura de McCreight [11]. |
| Abstract: | Given a sequence of n keys of variable sizes, some optimal search trees are considered. Constructing optimal cost multiway search trees is NP-hard, although it can be done in pseudo-polynomial time 0(n³L) and space 0(n²L) where L is the page size limit. Optimal space multiway search trees are obtained in 0(n³) time and 0(n²logn) time and 0(nlogn) space. The monotonicity principle does not apply to the above cases. Finding optimal cost general B-trees is NP-hard. But, a general B-tree of height 2 and minimal root size can be constructed in 0(nlogn) time and 0(n) space. In addition, if its root is restricted to contain M keys then the time complexity increases to 0(n²M) This answers a conjecture by McCreight [11] |
| Keywords: | Árvore de pesquisa |
| Subject CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Production unit: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Issue: | 0282 |
| Issue Date: | 31-Oct-1982 |
| Publisher country: | Brasil |
| Language: | eng |
| Right access: | Acesso Aberto |
| Citation: | SZWARCFITER, J. L. Optimal multiway search trees for variable size keys. Rio de Janeiro: NCE, UFRJ, 1982. 16 p. (Relatório Técnico, 02/82) |
| Appears in Collections: | Relatórios |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.