Partition all numbers between 0 and 100 that are not yet in the above AVL-tree into (the smallest possible number of) intervals such that two numbers in the same interval would be added to the same position in the AVL-tree. Note that every such interval also needs to be maximal in the sense that no other number can be added to it.

For each such interval you need to specify: 1. The interval, e.g., 0-6.

The position in the AVL-tree, where any number in the interval would be inserted. For instance, if any number in the interval would be inserted to the left of 4, write L4, if any number in the interval would be inserted to the right of 4, write R4.

The type of reorganisation that has to be applied after one (any) number in the interval would be inserted into the (original) AVL-tree. There are three possible types of reorganisation:

a. For no reorganisation write N.

b. For a simple rotation write SR.

c. For a double rotation write DR.

For instance, the first interval contains all numbers between 0 and 9, and each of those would be initially inserted to the left of 10 followed by a no reorganisation. Therefore, you would need to write 0-9 L10 N for the first interval.

Note that you should always consider adding the numbers to the original AVL-tree given in the figure, i.e., you never actually apply any reorganisation but only say which reorganisation would need to be employed if a number from the respective interval is inserted into the original AVL-tree.

You should consider the intervals in their natural order. Use each of the following sub-questions to specify all of the above information for one interval. Start with the second interval because the first interval is given as an example.

Give the following:

a)2nd interval

b)3rd interval

c)4th interval

d)5th interval

e)6th interval

f)7th interval

g)8th interval

h)9th interval

i)10th interval

j)11th interval