International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 11, No. 1, 8 Apr. 2025
Cover page and Table of Contents: PDF (size: 2295KB)
An Extended Symbolic-Arithmetic Model for Teaching Double-Black Removal with Rotation in Red-Black Trees
PDF (2295KB), PP.1-30
Views: 0 Downloads: 0
Author(s)
Kennedy E Ehimwenma
1,*
Hongyu Zhou
1
Junfeng Wang
1
Ze Zheng
1
Index Terms
Data Structures, Symbolic Arithmetic, Algorithm, Red-Black Tree, Double-Black Removal, Node Rotation, Tree Balance, Computer Science Education
Abstract
Double-black (DB) nodes have no place in red-black (RB) trees. So when DB nodes are formed, they are immediately removed. The removal of DB nodes that cause rotation and recoloring of other connected nodes poses greater challenges in the teaching and learning of RB trees. To ease this difficulty, this paper extends our previous work on the symbolic arithmetic algebraic (SA) method for removing DB nodes. The SA operations that are given as, Red + Black = Black; Black - Black = Red; Black + Black = DB; and DB – Black = Black removes DB nodes and rebalances black heights in RB trees. By extension, this paper projects three SA mathematical equations, namely, general symbolic arithmetic rule, ∆_([DB,r,p]); partial symbolic arithmetic rule1, ∂_([DB,p])^'; and partial symbolic arithmetic rule2, ∂_([r])^''. The removal of a DB node ultimately affects black heights in RB trees. To balance black heights using the SA equations, all the RB tree cases, namely, LR, RL, LL, and RR, were considered in this work; and the position of the nodes connected directly or indirectly to the DB node was also tested. In this study, to balance a RB tree, the issues considered w.r.t. the different cases of the RB tree were i) whether a DB node has an inner, outer, or both inner and outer black nephews; or ii) ) whether a DB node has an inner, outer or both inner and outer red nephews. The nephews r and x in this work are the children of the sibling s to a DB, and further up the tree, the parent p of a DB is their grandparent g. Thus, r and x have indirect relationships to a DB at the point of formation of the DB node. The novelty of the SA equations is in their effectiveness in the removal of DB that involves rotation of nodes as well as the recoloring of nodes along any simple path so as to balance black heights in a tree. Our SA methods assert when, where, and how to remove a DB node and the nodes to recolor. As shown in this work, the SA algorithms have been demonstrated to be faster in performance w.r.t. to the number of steps taken to balance a RB tree when compared to the traditional RB algorithm for DB removal. The simplified and systematic approach of the SA methods has enhanced student learning and understanding of DB node removal in RB trees.
Cite This Paper
Kennedy E. Ehimwenma, Hongyu Zhou, Junfeng Wang, Ze Zheng, "An Extended Symbolic-Arithmetic Model for Teaching Double-Black Removal with Rotation in Red-Black Trees", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.11, No.1, pp. 1-30, 2025. DOI: 10.5815/ijmsc.2025.01.01
Reference
[1]Y. D. Liang, Introduction to Java programming and data structures, 11th ed., United Kingdom: Pearson Education, 2019.
[2]M. T. Goodrich, R. Tamassia and M. H. Goldwasser, Data structures and algorithms in Java, John Wiley & Sons, 2014.
[3]C. Sanderson and R. Curtin, "A user-friendly hybrid sparse matrix class in C++," in In International Congress on Mathematical Software, Cham, July 2018.
[4]K. E. Ehimwenma, J. Wang, Z. Zheng and H. Zhou, "A symbolic-arithmetic for teaching double-black node removal in red-black trees," Educational Dimension, vol. 59, pp. 112-129, 2022.
[5]Wikipedia, "Red-black tree," [Online]. Available: http://www2.cs.ccu.edu.tw/~tmh104u/hw-9.html. [Accessed 7th July 2023].
[6]Z. D. Eddine, "Improving the Red-Black tree delete algorithm," 2021.
[7]S. Kahrs, "Red-black trees with types," Journal of functional programming, vol. 11, no. 4, pp. 425-432, 2001.
[8]E. Fredriksson, "Reducing CPU scheduler latency in Linux," Thesis, UMEA University, 2022.
[9]F. Xhakaj and C. W. Liew, "A new approach to teaching red black tree," in In Proceedings of the 2015 ACM Conference on Innovation and Technology in Computer Science Education, 2015.
[10]D. Galles, "Red Black Tree," 2011. [Online]. Available: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html. [Accessed 04 04 2022].
[11]S. Hanke, "The performance of concurrent red-black tree algorithms," in International Workshop on Algorithm Engineering, 1999.
[12]L. Qiaoyu, L. Jianwei and X. Yubin, "Performance analysis of data organization of the real-time memory database based on red-black tree," In 2010 International Conference on Computing, Control and Industrial Engineering, vol. 1, pp. 428-430, 2010.
[13]H. Zhang and Q. Liang, "Red-black tree used for arranging virtual memory area of Linux," in In 2010 International Conference on Management and Service Science, 2010.
[14]J. Li, Y. Xu and H. Guo, "Memory organization in a real-time database based on red-black tree structure," In Fifth World Congress on Intelligent Control and Automation (IEEE Cat. No. 04EX788) , vol. 5, pp. 3971-3974, June 2004.
[15]M. Jeong and E. Lee, "A Swapping Red-black Tree for Wear-leveling of Non-volatile Memory," The Journal of the Institute of Internet, Broadcasting and Communication, vol. 19, no. 6, pp. 139-144, 2019.
[16]S. L. Deshpande, "Tree-Based Approaches for Improving Energy Efficiency and Life Time of Wireless Sensor Networks (WSN): A Survey and Future Scope for Research," Singapore, 2020.
[17]M. Hasanzadeh, B. Alizadeh and F. Baroughi, "The cardinality constrained inverse center location problems on tree networks with edge length augmentation," Theoretical Computer Science, vol. 865, pp. 12-33, 2021.
[18]W. L. Chun and N. Huy, Using an Intelligent Tutoring System to Teach Red Black Trees., 2019.
[19]D. Wu, P. Guo, C. Zhang, C. Hou, Q. Wang and Z. Yang, "Research and Practice of Data Structure Curriculum Reform Based on Outcome-Based Education and Chaoxing Platform," International Journal of Information and Education Technology, vol. 11, no. 8, 2021.
[20]Z. Seidametova, "Some methods for improving data structure teaching efficiency," Educational Dimension, vol. 58, pp. 164-175, 2022.
[21]J. King, "Combining Theory and Practice in Data Structures & Algorithms Course Projects: An Experience Report," in Proceedings of the 52nd ACM Technical Symposium on Computer Science Education, NY, USA, March 2021.
[22]T. Nipkow, "Teaching algorithms and data structures with a proof assistant (invited talk)," in Proceedings of the 10th ACM SIGPLAN International Conference on Certified Programs and Proofs, Denmark, January 2021.
[23]L. Bounif and D. E. Zegour, "A revisited representation of the red-black tree," International Journal of Computer Aided Engineering and Technology, vol. 16, no. 1, pp. 95-118, 2022.
[24]K. Ghiasi-Shirazi, T. Ghandi, A. Taghizadeh and A. Rahimi-Baigi, "A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm.," June 2022.
[25]R. Sedgewick, " Left-leaning red-black trees," In Dagstuhl Workshop on Data Structures, vol. 17, Sept 2008.
[26]D. Galles, "Red Black Tree Visualization," 2011. [Online]. Available: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html. [Accessed 04 04 2022].
[27]S. T. Mueller, E. S. Veinott, R. R. Hoffman, G. Klein, L. Alam, T. Mamun and W. J. Clancey, "Principles of explanation in human-AI systems.," 2021.
[28]J. J. B. Vial, A concurrent red black tree, Pontificia Universidad Catolica de Chile , 2012.
[29]K. Germane and M. Might, "Deletion: The curse of the red-black tree," Journal of Functional Programming, vol. 24, no. 4, pp. 423-433, 2014.