Insert the following numbers in the given sequence in an AVL tree

Homework #5 CS 351.001 Spring 2024 Data Structure II 50 Points Due: 05/02/2024, 11:59 PM 1. Insert the following numbers in the given sequence in an AVL tree. Show each step of insertion and rotation. Calculate the balance factor of each node of the tree after every insertion to check whether the tree is balanced. If it is unbalanced, mention the case (i.e., LL, RR, LR, or RL) and show the direction of rotations. Do not skip any step. Show the intermediate trees for LR and RL cases, if applicable. Draw all steps of the AVL tree. Do not use any online resources to draw the AVL tree. Draw the tree on paper. Look at the example below: (15 points) 52, 36, 31, 1, 9, 78, 33, 40, 39, 6 Example: Insert the following numbers in an AVL tree: 35, 47, 51 a) 35 35 b) 47 35 47 c) 51 47 35 47 35 RR case 51 51 2. Show every step of inserting, into an initially empty order-5 B-tree, entries with keys (4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12, 41, 73). (16 Points) 3. Draw Edge List Structure, Adjacency List Structure, and Adjacency Matrix Structure representation of the following graph: (3 X 3 = 9 Points) 4. Find the spanning trees of the following graph by Depth First Search traversal. Choose D as the source vertex. Show each step. (10 Points) On the Western Online Homework 5 page, upload the .docx/ .pdf files for Q1, Q2, Q3, and Q4. You can draw the AVL tree, B-tree, and graph on paper, take photos, and paste those photos into a Word file. Write your name on each page of the answer sheets for Q1 to Q4. Please note that points will be deducted if the name is not written on each page of the answer sheets.