Partitioned Trees
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
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 revueLicence 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 →