Consider the example of a left-leaning-red-black BST below. Find a specific example where a single insertion requires at least four rotations, and the inserted key ends up at the root of the tree. Draw the initial tree (just after the inserted key has been attached as a leaf with a red edge) and also draw the final tree (after all the rotations and color flips are done). Be sure to indicate which edges are red (you may use thick edges to represent red). Please draw out each step separately, do not combine steps without explanation.

Leftleaning red-black BSTs (Guibas-Sedgewick 1979 and Sedgewick 2007) 1. Represent 2-3 tree as a BST. 2. Use "internal" left-leaning links as "glue" for 3-nodes. 3-node larger key is root greater a and bthan b greater than b than a etwee than a a a red links "glue nodes within a 3-node black links connect 2-nodes and 3-nodes 2-3 tree corresponding red-black BST