The programming language is C or C++; test your code before submission using the gcc or g++ compiler. Do not change the given interface.

Take the height-balanced tree code, and replace the key field by a field int leaves. That field should contain the number of leaves below the node, so n->leaves = 1 if n is a leaf, and n->leaves =n->left->leaves + n->right->leaves else. The leaves field must be updated after an insertion or deletion for all nodes on the path from the root to the changed leaf, and after a rotation for the changed nodes.

(1) replace the find function by object t *find by number(tree node t *tree, int k); which returns the object stored in the k-th leaf from left (start counting with the leftmost leaf as 1);

(2) replace the insert function by void insert by number(tree node t *tree, int k, object t *new obj); which inserts new obj in a new k-th leaf, moving all leaves above it one step to the right (without renumbering), and

(3) replace the delete function by object t * delete by number(tree node t *tree, int k); which deletes (and returns) the object stored in the k-th leaf, moving all leaves above it one step to the left (without renumbering).