A symbolic-arithmetic for teaching double-black node removal in red-black trees

Kennedy E. Ehimwenma; Junfeng Wang; Ze Zheng; Hongyu Zhou

doi:10.31812/educdim.7629

Authors

Kennedy E. Ehimwenma Wenzhou-Kean University https://orcid.org/0000-0002-7616-9342
Junfeng Wang Wenzhou-Kean University
Ze Zheng Wenzhou-Kean University
Hongyu Zhou Wenzhou-Kean University

DOI:

https://doi.org/10.31812/educdim.7629

Keywords:

red-black tree, double-black node removal, symbolic-algebraic arithmetic, algorithm, tree balance, data structures, computer science education

Abstract

A red-black (RB) tree is a data structure with red and black nodes coloration. The red and black color of nodes make up the principal component for balancing a RB tree. A balanced tree has an equal number of black nodes on any simple path. But when a black leaf node is deleted, a double-black (DB) node is formed, thus, causing a reduction in black heights and the tree becomes unbalanced. Rebalancing a RB tree with a DB node is a fairly complex process. Teaching and learning the removal of DB nodes is also challenging. This paper introduces a simplified novel method which is a symbolic-algebraic arithmetic procedure for the removal of DB nodes and the rebalancing of black heights in RB trees. This simplified approach has enhanced student learning of the DB node removal in RB trees. Feedback from students showed the learnability, workability and acceptance of the symbolic-algebraic method in balancing RB trees after a delete operation.

Downloads

Download data is not yet available.

Abstract views: 619 / PDF views: 109

References

Besa, J., Eterovic, Y.: A concurrent red–black tree. Journal of Parallel and Distributed Computing 73(4), 434–449 (2013), ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2012.12.010 DOI: https://doi.org/10.1016/j.jpdc.2012.12.010

Bounif, L., Zegour, D.E.: A revisited representation of the red-black tree. International Journal of Computer Aided Engineering and Technology 16(1), 95–118 (2022), https://doi.org/10.1504/IJCAET.2022.119541 DOI: https://doi.org/10.1504/IJCAET.2022.119541

Fredriksson, E.: Reducing CPU scheduler latency in Linux. Bachelor thesis, Umeå University (2022), URL http://www.diva-portal.se/smash/get/diva2:1630380/FULLTEXT01.pdf

Galles, D.: Red Black Tree Visualization (2011), URL https://www.cs.usfca.edu/∼galles/visualization/RedBlack.html

Germane, K., Might, M.: Deletion: The curse of the red-black tree. Journal of Functional Programming 24(4), 423–433 (2014), https://doi.org/10.1017/S0956796814000227 DOI: https://doi.org/10.1017/S0956796814000227

Ghiasi-Shirazi, K., Ghandi, T., Taghizadeh, A., Rahimi-Baigi, A.: Revisiting 2-3 Red-Black Trees with a Pedagogically Sound yet Efficient Deletion Algorithm: The Parity-Seeking Delete Algorithm (Jun 2022), https://doi.org/10.48550/ARXIV.2004.04344, URL https://arxiv.org/abs/2004.04344

Goodrich, M.T., Tamassia, R., Goldwasser, M.H.: Data Structures and Algorithms in Java. John Wiley & Sons, 6 edn. (2014), ISBN 978-1-118-77133-4

Hanke, S.: The Performance of Concurrent Red-Black Tree Algorithms. In: Vitter, J.S., Zaroliagis, C.D. (eds.) Algorithm Engineering, pp. 286–300, Springer Berlin Heidelberg, Berlin, Heidelberg (1999), ISBN 978-3-540-48318-2, https://doi.org/10.1007/3-540-48318-7 23 DOI: https://doi.org/10.1007/3-540-48318-7

Hasanzadeh, M., Alizadeh, B., Baroughi, F.: The cardinality constrained inverse center location problems on tree networks with edge length augmentation. Theoretical Computer Science 865, 12–33 (2021), ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2021.02.026 DOI: https://doi.org/10.1016/j.tcs.2021.02.026

Jeong, M., Lee, E.: A Swapping Red-black Tree for Wear-leveling of Nonvolatile Memory. The Journal of the Institute of Internet, Broadcasting and Communication 19(6), 139–144 (Dec 2019), https://doi.org/10.7236/JIIBC.2019.19.6.139

Kahrs, S.: Red-black trees with types. Journal of Functional Programming 11(4), 425–432 (2001), https://doi.org/10.1017/S0956796801004026 DOI: https://doi.org/10.1017/S0956796801004026

King, J.: 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, p. 959–965, SIGCSE ’21, Association for Computing Machinery, New York, NY, USA (2021), ISBN 9781450380621, https://doi.org/10.1145/3408877.3432476 DOI: https://doi.org/10.1145/3408877.3432476

Li, J., Xu, Y., Guo, H.: 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 Vol.5 (2004), https://doi.org/10.1109/WCICA.2004.1342243 DOI: https://doi.org/10.1109/WCICA.2004.1342243

Liang, Y.D.: Introduction to Java Programming, Brief Version, Global Edition. Pearson Education, 11 edn. (2018)

Liew, C.W., Nguyen, H.: Using an Intelligent Tutoring System to Teach Red Black Trees. In: Proceedings of the 50th ACM Technical Symposium on Computer Science Education, p. 1280, SIGCSE ’19, Association for Computing Machinery, New York, NY, USA (2019), ISBN 9781450358903, https://doi.org/10.1145/3287324.3293823 DOI: https://doi.org/10.1145/3287324.3293823

Nipkow, T.: 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, p. 1–3, CPP 2021,18 Association for Computing Machinery, New York, NY, USA (2021), ISBN 9781450382991, https://doi.org/10.1145/3437992.3439910 DOI: https://doi.org/10.1145/3437992.3439910

Pranesh, Deshpande, S.L.: Tree-Based Approaches for Improving Energy Efficiency and Life Time of Wireless Sensor Networks (WSN): A Survey and Future Scope for Research. In: Ranganathan, G., Chen, J., Rocha, Á. (eds.) Inventive Communication and Computational Technologies, pp. 583–590, Springer Singapore, Singapore (2020), ISBN 978-981-15-0146-3, https://doi.org/10.1007/978-981-15-0146-3 55 DOI: https://doi.org/10.1007/978-981-15-0146-3_55

Qiaoyu, L., Jianwei, L., Yubin, X.: 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), https://doi.org/10.1109/CCIE.2010.113 DOI: https://doi.org/10.1109/CCIE.2010.113

Sanderson, C., Curtin, R.: A User-Friendly Hybrid Sparse Matrix Class in C++. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) Mathematical Software – ICMS 2018, pp. 422–430, Springer International Publishing, Cham (2018), ISBN 978-3-319-96418-8, https://doi.org/10.1007/978-3-319-96418-8 50 DOI: https://doi.org/10.1007/978-3-319-96418-8_50

Sedgewick, R.: Left-leaning Red-Black Trees. In: Dagstuhl Workshop on Data Structures, vol. 17 (Sep 2008), URL https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf

Seidametova, Z.: Some methods for improving data structure teaching efficiency. Educational Dimension 58, 164–175 (Jun 2022), https://doi.org/10.31812/educdim.4509 DOI: https://doi.org/10.31812/educdim.4509

Wu, D., Guo, P., Zhang, C., Hou, C., Wang, Q., Yang, Z.: Research and Practice of Data Structure Curriculum Reform Based on Outcome-Based Education and Chaoxing Platform. International Journal of Information and Education Technology 11(8), 375–380 (2021), ISSN 2010-3689, https://doi.org/10.18178/ijiet.2021.11.8.1537 DOI: https://doi.org/10.18178/ijiet.2021.11.8.1537

Xhakaj, F., Liew, C.W.: A New Approach To Teaching Red Black Tree. In: Proceedings of the 2015 ACM Conference on Innovation and Technology in Computer Science Education, p. 278–283, ITiCSE ’15, Association for Computing Machinery, New York, NY, USA (2015), ISBN 9781450334402, https://doi.org/10.1145/2729094.2742624 DOI: https://doi.org/10.1145/2729094.2742624

Zegour, D.E.: Improving the Red-Black tree delete algorithm (Jul 2022), https://doi.org/10.21203/rs.3.rs-1194654/v3 DOI: https://doi.org/10.21203/rs.3.rs-1194654/v3

Zhang, H., Liang, Q.: Red-Black Tree Used for Arranging Virtual Memory Area of Linux. In: 2010 International Conference on Management and Service Science, pp. 1–3 (2010), https://doi.org/10.1109/ICMSS.2010.5575666 DOI: https://doi.org/10.1109/ICMSS.2010.5575666