Accès ouvert · CC BY

Partitioned Trees

Article scientifique 2023 Sciences mathématiques et statistiques Anglais

Résumé

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 and deletion 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.

Citer ce document

Meguellati, F. M., Zegour, D. E., & Zouana, S. (2023). Partitioned Trees. Research Square. https://doi.org/10.21203/rs.3.rs-2876941/v1

Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)

Accès au document

Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter

Voir l'article sur le site de la revue

Licence et provenance

Licence : CC BY

Notice moissonnée depuis OpenAlex le 26/09/2026. Le document reste hébergé par sa source.
Voir le document à la source →

Statistiques

Consultations (hors robots) : 9

Téléchargements (hors robots) : 0

Méthode de comptage