Pantheon Repositorio Institucional
Recopila, preserva y difundi la producción académica digital en todas las áreas del conocimiento.
Comprende los activos del repositorio, además de tesis y disertaciones en la UFRJ, artículos científicos, libros electrónicos, capítulos de libros y trabajos presentados en eventos para los profesores, investigadores, personal administrativo y estudiantes de maestría y doctorado.
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/1451| Especie: | Relatório |
| Título : | Optimal multiway search trees for variable size keys |
| Autor(es)/Inventor(es): | Szwarcfiter, Jayme Luiz |
| Resumen: | 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]. |
| Resumen: | 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] |
| Materia: | Árvore de pesquisa |
| Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| Es parte de: | Relatório Técnico NCE |
| Número: | 0282 |
| Fecha de publicación: | 31-oct-1982 |
| País de edición : | Brasil |
| Idioma de publicación: | eng |
| Tipo de acceso : | Acesso Aberto |
| Citación : | 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) |
| Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 02-82.pdf | 472.99 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.