• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
Document
Author
Full name
Yan Soares Couto
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2019
Supervisor
Committee
Fernandes, Cristina Gomes (President)
Franco, Álvaro Junior Pereira
Stolfi, Jorge
Title in Portuguese
Estrutura de dados persistentes
Keywords in Portuguese
Árvores rubro-negras
Estruturas de dados
Localização de ponto
Persistência
Abstract in Portuguese
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.
Title in English
Persistent data structures
Keywords in English
Data structures
Persistence
Point location
Red-black trees
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
main.pdf (763.98 Kbytes)
Publishing Date
2019-09-25
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2019. All rights reserved.