Teaching Red-Black Trees under the Memory-Safety Critique of C++

Abstract

Red-black trees are among the most difficult topics in an undergraduate C++ programming course, and the sustained public criticism of C++ over memory safety raises a practical question for the instructor: how should the structure be implemented in teaching material now that raw owning pointers are widely regarded as obsolete? This paper examines several candidate instructional implementations of the red-black tree, from the classical formulation with raw pointers and a sentinel node, through an ownership-explicit formulation in which child edges are held by smart pointers and the parent edge remains a non-owning raw pointer, to a formulation in which the awkward two-child deletion case is reduced to the simple one-child case by copying the successor's payload. The central observation is that the red-black tree is precisely the structure at which the single-owner discipline expressed by a unique smart pointer does not fit cleanly: the algorithm is a graph of owning child edges and non-owning parent back-edges whose rearrangement, in the two-child deletion case, briefly leaves a node owned by nothing, the very condition smart pointers are meant to prevent. Rather than concealing this difficulty, the approach proposed here places it at the centre of the lesson: students attempt the smart-pointer version, analyse why it resists a clean solution, and are then shown the payload-copy reduction as the resolution. Refined over three successive cohorts and accompanied by a post-course questionnaire, the approach was associated with reduced reported difficulty with the memory-management aspects of the topic and an improved ability to explain why the structure resists a single-owner model and to justify the choice between the ordered and unordered associative containers of the standard library. Because the cohorts are small, these outcomes are offered as a curricular proposal grounded in teaching experience rather than as a demonstrated effect. The paper concludes that red-black trees should be retained as core content and that the memory-safety critique of C++ strengthens the case for teaching them, provided smart pointers are introduced not as a solution but as a deliberately staged failure that makes ownership reasoning visible.