Read Chap$6$ notes and answer the following. Your answers should be similar to the worked out examples in the notes.

$1)$ Construct the AVL tree for the following data. You simply show the steps as in the demonstrated example by drawing the graph after each insertion, computing the balance factors and also indicating the types of rotations used and the result of those rotations.

$2)$ Construct a heap for the data below as shown in demonstrated example in the notes.

The data for both the problems is $1,2,8,6,9,5,3,7,4$