Partitioned Trees

Autores/as

  • 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

Palabras clave:

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

Resumen

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.

Biografía del autor/a

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.

Descargas

Publicado

2025-06-18

Número

Vol. 29 Núm. 2 (2025): 29(2) 2025

Sección

Artículos

Licencia

Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.

Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.

El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.

Esta Transferencia está sujeta a las siguientes reservas:

  • Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
  • Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.