#$1.$ Ex$.4\mathrm{.}5\mathrm{.}3-$ Consider the insertion of items with the following keys $($in the given order$)$ into an initially empty AVL tree: $0,2,4,6,8,10,12,14,16,18.$ Draw the final tree that results.

#$2.$ Ex$.4\mathrm{.}5\mathrm{.}4--$ A certain Professor Amongus claims that the order in which a fixed set of elements is inserted into an AVL tree does not matter$-$the same tree results every time. Give a small example that proves Professor Amongus wrong.

#$3.$ Ex$.4\mathrm{.}5\mathrm{.}12-$ Draw the AVL tree resulting from the insertion of an item with key $62$ into the AVL tree of Figure $4\mathrm{.}3\mathrm{.}3$

Links to an external site.b$.($Use the link in ZyBooks$)$

#$4.$ Ex$.4\mathrm{.}5\mathrm{.}15-$ Draw an example red$-$black tree that is not an AVL tree. Your tree should have at least $6$ nodes, but no more than $16.$

#$5.$ Ex$.4\mathrm{.}5\mathrm{.}34-$ Show that the nodes of any AVL tree T can be colored "red" and "black" so that T becomes a red$-$black tree.

#$6.$ Ex$.4\mathrm{.}5\mathrm{.}43-$ Suppose you are working for a fast$-$growing startup company, which we will call "FastCo," and it is your job to write a software package that can maintain the set, $E,$ of all the employees working for FastCo. In particular, your software has to maintain, for each employee, $x$ in $E,$ the vital information about $x,$ such as his or her name and address, as well as the number of shares of stock in FastCo that the CEO has promised to $x.$ When an employee first joins FastCo they start out with $0$ shares of stock. Every Friday afternoon, the CEO hosts a party for all the FastCo employees and kicks things off by promising every employee that they are getting $y$ more shares of stock, where the value of $y$ tends to be different every Friday. Describe how to implement this software so that it can simultaneously achieve the following goals:

The time to insert or remove an employee in $E$ should be $O(logn),$ where $n$ is the number of employees in $E.$

Your system must be able to list all the employees in $E$ in alphabetical order in $O(n)$ time, showing, for each $x$ in $E,$ the number of shares of FastCo the CEO has promised to $x.$

Your software must be able to process each Friday promise from the CEO in $O(1)$ time, to reflect the fact that everyone working for FastCo on that day is being promised $y$ more shares of stock. $($Your system needs to be this fast so that processing this update doesn't make you miss too much of the party.$)$