using python

Read the submission instruction in the blackboard and strictly follow it. Q1. [10] AVL Tree Generate an AVL tree by inserting the following keys (in the given order) into an initially empty AVL tree: 10, 40, 25, 35, 30, 45. Draw an AVL tree after the insertion of each key, one by one. Q2. [10] AVL Tree Draw the AVL tree after the removal of the key 20 from the AVL tree below. In the given tree, (a) specify three nodes z,y,x where a balance is broken, its tallest child and its tallest grandchild, respectively; then, (b) draw an AVL after each rotation to yield the final AVL tree. SO 40 78 62 88 55 70 Q3. [45] Implementation of AVL tree operations. For Q1-Q2, implement the operations (insert, remove, restructure, etc.) of AVL tree in Python. Print the resulting tree from the root in the following format: (a key of node: a depth of node, a height of node, a key of parent, a key of left-child, a key of right-child, a height of the node), e.g.) (50:0, 4. null40, 78). Since AVL tree is a balanced Binary Search Tree, you may be able to reuse (or modify) your Python codes of certain functions from HW 2. In the main program, invoke the functions such as AVL-Insert(10), AVL-Insert(40)... AVL-Remove(20), then print the result of the final tree. In the 'print' statement include the proper description of output as well as the results e.g.) print("Q1. Insertion of 10:", vikey, v.depth, ..... Viheight) Run your program and insert the image of your output. Q5. [10] Red Blade Tree Generate a Red-Black tree by inserting the following keys (in the given order) into an initially empty RB-Tree: 10,40, 25, 35, 30, 45. Show the changes of RB-tree after each insertion of a key, ane by one. 06. [20] Red-Blad Tree 1) [5] Draw the Red-Black tree after the insertion of 40 into the RB-tree above. 2) [5] Draw the RB-tree after the insertion of 35 into the resulting RB-tree in 1). 3] [10] In the RB-Tree in the figure, draw the resulting RB-tree after deleting a key 90. For each operation, specify a color of a node and show the essential steps of restructuring/recoloring of RB-tree to yield the final tree. Q6. [45] Implement the operations of Red-Black tree in Q5. Print the resulting tree in the form of (la key of the node, color): depth of a node height of a node, (a key of parent, color). (a key of left- child, color), (a key of right-child, color)) eg) [(80.3). 1.3. (50,B)(65.R). (90. B)) Similarly, you may be able to reuse your Python codes of certain operations from HW 2. In the main program, invoke the functions such as RB-Insert(40), RB-Insert(35), or RB-Remove(90) then print the result of the final tree. In the print statement, include the proper description of output as well as the result: eg.) print"Q5. Insertion of 40:"(v.key. v.color..depth. Verighit. Wright.color, Run your program and insert the image of your output