1. Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT)
  2. GRAD - Cursos de Graduação
  3. TCC - Trabalhos de Conclusão de Curso de Graduação
  4. Ponta Grossa
  5. PG - Ciência da Computação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/15974
Registro completo de metadados
Campo DCValorIdioma
dc.creatorBauer, Edimar Jacob
dc.date.accessioned2020-11-19T18:24:23Z-
dc.date.available2020-11-19T18:24:23Z-
dc.date.issued2018-11-13
dc.identifier.citationBAUER, 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.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/15974-
dc.description.abstractThe 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.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectProgramação (Computadores)pt_BR
dc.subjectSistema binário (Matemática)pt_BR
dc.subjectPesquisapt_BR
dc.subjectComputer programmingpt_BR
dc.subjectBinary system (Mathematics)pt_BR
dc.subjectResearchpt_BR
dc.titleÁrvore binária de pesquisa oculta com crescimento dinâmicopt_BR
dc.typebachelorThesispt_BR
dc.description.resumoA á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.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Queiroz, Saulo Jorge Beltrao de
dc.contributor.referee1Queiroz, Saulo Jorge Beltrao de
dc.contributor.referee2Almeida, Sheila Morais de
dc.contributor.referee3Aires, Simone Bello Kaminski
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2018_2_02.pdf2,1 MBAdobe PDFThumbnail
Visualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.