ETD system

Electronic theses and dissertations repository

 

Tesi etd-04192016-111159


Thesis type
Tesi di dottorato di ricerca
Author
AMANI, MAHDI
URN
etd-04192016-111159
Title
New Combinatorial Properties and Algorithms for AVL Trees
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Commissione
tutor Prof.ssa Pagli, Linda
tutor Prof.ssa Bernasconi, Anna
Parole chiave
  • AVL trees
  • Weight-balanced tree
  • External-memory model
  • Cache-oblivious model
  • Core partitioning scheme
  • COG-tree
  • Gap
  • AVL rotation.
Data inizio appello
15/05/2016;
Consultabilità
completa
Riassunto analitico
In this thesis, new properties of AVL trees and a new partitioning of binary search trees named<br>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.<br>We introduce the core partitioning scheme, which maintains a balanced search tree as a dynamic<br>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).<br>Using our scheme, searching a key requires O(log_B n) block transfers and O(log n) comparisons<br>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.<br>Studying the properties of these trees also lead us to some other new properties of AVL trees<br>and trees with bounded degree, namely, we present and study gaps in AVL trees and we prove Tarjan et al.&#39;s conjecture on the number of rotations in a sequence of deletions and insertions.
File