A symbolic-arithmetic for teaching double-black node removal in red-black trees
DOI:
https://doi.org/10.31812/educdim.7629Keywords:
red-black tree, double-black node removal, symbolic-algebraic arithmetic, algorithm, tree balance, data structures, computer science educationAbstract
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
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
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2022 Kennedy E. Ehimwenma, Junfeng Wang, Ze Zheng, Hongyu Zhou
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
Accepted 2022-11-28
Published 2022-12-11