Partitioned Trees

Authors

  • Fahd Mustapha Meguellati Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309
  • Djamel Eddine Zegour Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309
  • Seyfeddine Zouana Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309

DOI:

https://doi.org/10.13053/cys-29-2-4820

Keywords:

Binary Search trees, AVL-trees, Red-Black trees, Restructuring, Partitioning, Departitioning

Abstract

We introduce the Partitioned Trees, a form of Partitioned Binary Search Tree parameterized to represent both Red-Black trees and a family of partially balanced Binary Search Trees. Partitioned Tree is interesting not only because it provides the same time and space complexity as Balanced Binary Search trees O(logn), but also because it’s simple to implement, easily understandable, and highly adaptable in different fields where rebalancing is costly. We outline the various maintenance operations and insertion anddeletion algorithms employed by the proposed data structure. Additionally, we conduct an in-depth analysis on the worst-case height of Partitioned Trees followed by a comparison of Partitioned Trees and Red-Black Trees. Our simulations confirm that Partitioned Trees exhibit superior performance compared to Red-Black Trees.

Author Biographies

Fahd Mustapha Meguellati, Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309

Meguellati Fahd Mustapha is a Ph.D. student at the High School of Computer Sciences, Algiers (ESI: Ecole Supérieure d’Informatique), specializing in data structures. He received his master’s degree in 2013 from the University of Batna 2 in computer science engineering.

Djamel Eddine Zegour, Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309

Djamel Eddine Zegour is a doctor in the Paris Dauphine University and a professor in High School of Computer Science, Algiers (ESI: Ecole Supérieure d’Informatique). With over three decades of expertise, he specializes in data structures and programming paradigms. He has authored numerous scientific publications and educational software, contributing significantly to the field.

Seyfeddine Zouana, Ecole nationale Supérieure d’Informatique ESI, Oued Smar Alger , 16309

Seyfeddine Zouana is a Doctor at the High School of Computer Sciences, Algiers (ESI: Ecole Supérieure d’Informatique). He graduated as a computer science engineer and obtained his master’s degree in 2013. His research primarily focuses on data structures.

Downloads

Published

2025-06-18

Issue

Vol. 29 No. 2 (2025): 29(2) 2025

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.