Full text
| |
| Author(s): |
Yan Soares Couto
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Defense date: | 2019-01-08 |
| Examining board members: |
Cristina Gomes Fernandes;
Álvaro Junior Pereira Franco;
Jorge Stolfi
|
| Advisor: | Cristina Gomes Fernandes |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 17/05481-8 - Advanced data structures |
| Grantee: | Yan Soares Couto |
| Support Opportunities: | Scholarships in Brazil - Master |