Introduction

This lab is intended to increase your mastery of red-black trees. You can likely complete it in one class period.

Specific requirements

1. Review the Red-Black Tree Rules sheet
2. Devise a sequence of insertions that will trigger each of the situations in the Algorithm at least twice (A, B1, B2, C1, C2, C3). (You may need to do this in more than one tree, as the applet is limited to a depth of four.) Complete this step on paper before moving on to the applet in step 3.
3. Open the RBTree applet & perform the insertions. Note any discrepancies where your predictions from #2 turn out to be inaccurate.
4. Take screenshots after every insertion, and also after each trigger from #2 above. Paste into a Word document (.doc or .docx) and clearly label each. (Hint, if you convert each screenshot to a gif or jpeg before inserting into Word, your file will be much smaller.)