Introduction to Red-Black Tree

Zoom link

Passcode:  419518

CSE Teaching Faculty Candidate

Abstract:  We will be discussing the major properties and the definition of the red-black tree in this lecture. A red–black tree is one kind of binary search tree. Each node stores an extra bit of
information representing “color” (“red” or “black”). This extra bit is used to ensure that the tree remains approximately balanced during insertions and deletions. That is why we also call the red-black tree as self-balancing binary search tree.

We will also discuss the algorithms for insertion and deletion operations in a red-black tree
and the asymptotic analysis for these operations. When the tree is modified either with an
insertion or deletion operation, the new tree is rearranged and reset with new colors to restore
the coloring properties that constrain how unbalanced the tree can become in the worst case.

I will show the code snippets to implement the algorithm. If time permits, I will try to
demonstrate an implementation of the algorithm in object oriented programming style with
C++.

Bio:  Nasheen Nur is a Ph.D. Candidate in the Department of Software and Information System at the University of North Carolina at Charlotte (UNCC). With her thesis advisor Dr. Wenwen Dou, she has developed concept-oriented visualization models and user interface techniques such as knowledge graph-embeddings and visualizations for explainable artificial intelligence (XAI). Her research focuses on applied machine learning, XAI, natural language processing, visualization, network analytics, and computer science education. Funded by NSF EAGER 2018-2021, her research has been published or presented at the ACM International Conferences and the International Conference on Intelligence User Interfaces among others. She was a Data Science Intern at the Pacific Northwest National Laboratory in 2018. Before Ph.D., she earned a B.Sc in Computer Science and Engineering at Bangladesh University of Engineering & Technology. Her entrepreneurial experience includes designing a prototype of an analytical tool for analyzing students’ behavior with temporal analytics and explainable artificial intelligence. This interactive tool iteratively involves the student advisers in the knowledge discovery process along with the data scientists to understand students’ patterns of success or failure.