Due to the print book page limit, we cannot inlcude all good CheckPoint questions in the physical book. The CheckPoint on this Website may contain extra questions not printed in the book. The questions in some sections may have been reordered as a result. Nevertheless, it is easy to find the CheckPoint questions in the book on this Website. Please send suggestions and errata to Dr. Liang at y.daniel.liang@gmail.com. Indicate the book, edition, and question number in your email. Thanks!

Chapter 43 Check Point Questions

Section 43.2
▼43.2.1
What is a red-black tree? What is an external node? What is black-depth?
▼43.2.2
Describe the properties of a red-black tree.
▼43.2.3
How do you convert a red-black tree to a 2-4 tree? Is the conversion unique?
▼43.2.4
How do you convert a 2-4 tree to a red-black tree? Is the conversion unique?
Section 43.5
▼43.5.1
What are the data fields in RBTreeNode?
▼43.5.2
How do you insert an element into a red-black tree and how do you fix the double-red violation?
▼43.5.3
How do you delete an element from a red-black tree and how do you fix the double-black problem?
▼43.5.4
Show the change of the tree when inserting 1, 2, 3, 4, 10, 9, 7, 5, 8, 6 into it, in this order.
▼43.5.5
For the tree built in the preceding question, show the change of the tree after deleting 1, 2, 3, 4, 10, 9, 7, 5, 8, 6 from it in this order.