Estruturas de dados (EDs) permitem operações de acesso e de modificação; operações de acesso apenas consultam um ou mais campos de uma ED, enquanto operações de modificação podem alterar os campos da estrutura. Dizemos que, ao realizar uma operação de modificação, criamos uma nova versão da ED. Uma ED é parcialmente persistente se permite apenas operações de acesso a versões anteriores e modificação apenas na versão mais nova, e totalmente persistente se também permite operações de modificação em todas as versões. Esta dissertação apresenta a descrição e implementação de uma versão total ou parcialmente persistente de várias estruturas: pilhas, filas, deques e árvores rubro-negras. Também são discutidas técnicas gerais para tornar persistentes certas classes de estruturas de dados. Por fim, é apresentada uma solução ao problema de localização de ponto, que usa uma árvore de busca binária persistente. / Data structures (DSs) allow access and update operations; access operations only allow accessing the value of one or more fields of the DS, while update operations allow modifying the fields of the structure. We say that, whenever an update operation is done, a new version of the DS is created. A DS is partially persistent if it allows access operations to previous versions of the structure and update operations only on the newest version, and totally persistent if it also allows update operations on all versions. This dissertation presents the description and implementation of totally or partially persistent versions of several data structures: stacks, queues, deques, and red-black trees. General techniques to make certain classes of DSs persistent are also discussed. At last, a solution to the point location problem, using a persistent binary search tree, is presented.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-24092019-181655 |
| Date | 08 January 2019 |
| Creators | Couto, Yan Soares |
| Contributors | Fernandes, Cristina Gomes |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.002 seconds