Registro fonte: Árvore binária de pesquisa oculta com crescimento dinâmico

Árvore binária de pesquisa oculta com crescimento dinâmico

The hidden binary search tree (HBST) is a data structure that proposes an alternative definition for the search property of binary search trees. In the HBST, the search path is determined by the mean value of the keys interval. If Β represents the minimum amount of bits to uniquely represent every p...

ver descrição completa

Autor principal:	Bauer, Edimar Jacob
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Programação (Computadores) Sistema binário (Matemática) Pesquisa Computer programming Binary system (Mathematics) Research CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/15974
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-15974
recordtype	dspace
spelling	riut-1-159742020-11-19T18:24:23Z Árvore binária de pesquisa oculta com crescimento dinâmico Bauer, Edimar Jacob Queiroz, Saulo Jorge Beltrao de Queiroz, Saulo Jorge Beltrao de Almeida, Sheila Morais de Aires, Simone Bello Kaminski Programação (Computadores) Sistema binário (Matemática) Pesquisa Computer programming Binary system (Mathematics) Research CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO The hidden binary search tree (HBST) is a data structure that proposes an alternative definition for the search property of binary search trees. In the HBST, the search path is determined by the mean value of the keys interval. If Β represents the minimum amount of bits to uniquely represent every possible key, the largest interval is [0.2Β[, which leads to an Ο(Β) height. However, HSBT does not support linear-time in-order traversal. In this work we present the Sorted HBST (SHBST), a data structure that satisfies not only the hidden search property but also the traditional binary search tree property. This works also presents a procedure (named Enhanced Propagation) to improve the height of HSBT by one unit. Also, the work discusses different methods to enable the dynamic growth of HBST and presents the Dynamic HSBT. All discussed structures were evaluated along with the AVL search tree. The results suggest that all studied structures present the same asymptotic efficiency. A árvore binária de pesquisa oculta (do inglês, Hidden Binary Search Tree, HBST) é uma estrutura de dados que propõe uma definição alternativa à propriedade de pesquisa das árvores de busca. Na HBST, o caminho de busca é determinado pela média do intervalo de chaves possíveis. Assim, se Β representa a mínima quantidade de bits necessários para representar todos os valores chaves, o maior intervalo é [0,2Β[, resultando em uma altura Ο(Β). A HBST não garante elementos em ordem pelo valor chave, logo não se conhece método para realizar a operação de travessia em tempo linear. Este trabalho apresenta a Árvore Binária de Pesquisa Oculta Ordenada (do inglês, Sorted HBST, SHBST), que deixa a árvore Oculta em ordem tanto pelo valor oculto quanto pelo valor chave. Apresenta ainda o método de Propagação Estendida que diminui a quantidade máxima de níveis da HBST em uma unidade. E como objetivo principal, o trabalho discute diferentes métodos de crescimento dinâmico da HBST visando uma melhor distribuição dos nós na estrutura e conclui tal discussão apresentando a Árvore Binária de Pesquisa Oculta Dinâmica (DHBST). Por fim, é realizada uma pesquisa empírica de desempenho entre as Árvores AVL, HBST, SHBST e DHBST. Os resultados indicam que as estruturas propostas apresentam a mesma eficiência assintótica de árvores binárias de pesquisa auto balanceadas. 2020-11-19T18:24:23Z 2020-11-19T18:24:23Z 2018-11-13 bachelorThesis BAUER, Edimar Jacob. Árvore binária de pesquisa oculta com crescimento dinâmico. 2018. 69 f. Trabalho de Conclusão em (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. http://repositorio.utfpr.edu.br/jspui/handle/1/15974 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Ciência da Computação UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Programação (Computadores) Sistema binário (Matemática) Pesquisa Computer programming Binary system (Mathematics) Research CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle	Programação (Computadores) Sistema binário (Matemática) Pesquisa Computer programming Binary system (Mathematics) Research CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Bauer, Edimar Jacob Árvore binária de pesquisa oculta com crescimento dinâmico
description	The hidden binary search tree (HBST) is a data structure that proposes an alternative definition for the search property of binary search trees. In the HBST, the search path is determined by the mean value of the keys interval. If Β represents the minimum amount of bits to uniquely represent every possible key, the largest interval is [0.2Β[, which leads to an Ο(Β) height. However, HSBT does not support linear-time in-order traversal. In this work we present the Sorted HBST (SHBST), a data structure that satisfies not only the hidden search property but also the traditional binary search tree property. This works also presents a procedure (named Enhanced Propagation) to improve the height of HSBT by one unit. Also, the work discusses different methods to enable the dynamic growth of HBST and presents the Dynamic HSBT. All discussed structures were evaluated along with the AVL search tree. The results suggest that all studied structures present the same asymptotic efficiency.
format	Trabalho de Conclusão de Curso (Graduação)
author	Bauer, Edimar Jacob
author_sort	Bauer, Edimar Jacob
title	Árvore binária de pesquisa oculta com crescimento dinâmico
title_short	Árvore binária de pesquisa oculta com crescimento dinâmico
title_full	Árvore binária de pesquisa oculta com crescimento dinâmico
title_fullStr	Árvore binária de pesquisa oculta com crescimento dinâmico
title_full_unstemmed	Árvore binária de pesquisa oculta com crescimento dinâmico
title_sort	Árvore binária de pesquisa oculta com crescimento dinâmico
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	BAUER, Edimar Jacob. Árvore binária de pesquisa oculta com crescimento dinâmico. 2018. 69 f. Trabalho de Conclusão em (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/15974
_version_	1805323913865986048
score	10,814766

Árvore binária de pesquisa oculta com crescimento dinâmico

Registros relacionados