Learning objectives:

• Show understanding of red-black trees, a common data structure for efficiently implementing search

• Write code that correctly manipulates trees

• Analyze the complexity of an operation on balanced trees

(This is adapted from Problem 14-2 in Introduction to Algorithms by Cormen, Leiserson, and Rivest (first edition), pages 278-279.) I recommend reviewing the materials on red-black trees (chapter 3.3) and Lecture 9 from Sedgewick's site before continuing. (note: if the Sedgewick lecture is paywalled, you can find it for free by searching for "sedgewick balanced search trees coursera.")

NOTE: This project requires extensively editing the starter code available here (which is just a lightly edited version of Sedgewick's rb-tree implementation).

Your task is to implement the following operation on red-black trees:

Assignment