logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-04192016-111159


Tipo di tesi
Tesi di dottorato di ricerca
Autore
AMANI, MAHDI
URN
etd-04192016-111159
Titolo
New Combinatorial Properties and Algorithms for AVL Trees
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Relatori
tutor Prof.ssa Pagli, Linda
tutor Prof.ssa Bernasconi, Anna
Parole chiave
  • AVL rotation.
  • AVL trees
  • Cache-oblivious model
  • COG-tree
  • Core partitioning scheme
  • External-memory model
  • Gap
  • Weight-balanced tree
Data inizio appello
15/05/2016
Consultabilità
Completa
Riassunto
In this thesis, new properties of AVL trees and a new partitioning of binary search trees named
core partitioning scheme are discussed, this scheme is applied to three binary search trees namely AVL trees, weight-balanced trees, and plain binary search trees.
We introduce the core partitioning scheme, which maintains a balanced search tree as a dynamic
collection of complete balanced binary trees called cores. Using this technique we achieve the same theoretical efficiency of modern cache-oblivious data structures by using classic data structures such as weight-balanced trees or height balanced trees (e.g. AVL trees). We preserve the original topology and algorithms of the given balanced search tree using a simple post-processing with guaranteed performance to completely rebuild the changed cores (possibly all of them) after each update. Using our core partitioning scheme, we simultaneously achieve good memory allocation, space-efficient representation, and cache-obliviousness. We also apply this scheme to arbitrary binary search trees which can be unbalanced and we produce a new data structure, called Cache-Oblivious General Balanced Tree (COG-tree).
Using our scheme, searching a key requires O(log_B n) block transfers and O(log n) comparisons
in the external-memory and in the cache-oblivious model. These complexities are theoretically efficient. Interestingly, the core partition for weight-balanced trees and COG-tree can be maintained with amortized O(log_B n) block transfers per update, whereas maintaining the core partition for AVL trees requires more than a poly-logarithmic amortized cost.
Studying the properties of these trees also lead us to some other new properties of AVL trees
and trees with bounded degree, namely, we present and study gaps in AVL trees and we prove Tarjan et al.'s conjecture on the number of rotations in a sequence of deletions and insertions.
File