1. An AVL Tree is a special type of Binary Search Tree (BST) that it is height balanced. By height balanced I meanthat the height of every nodes left and right subtrees differ by at most one. This is enough to guarantee that a AVLtree with n nodes has a height no worst than Θ( log2 n ). Therefore, insertions, deletions, and search are in the worstcase Θ( log2 n ). An example of an AVL tree with integer keys is shown below. The height of each node is shown.50 30 609 34 32 47800000 1 2 1 3 Each AVL-tree node usually stores a balance factor in addition to its key and data. The balance factor keeps track ofthe relative height difference between its left and right subtrees.a) Label each node in the above AVL tree with one of the following balance factors:  ‘EQ’ if its left and right subtrees are the same height ‘TL’ if its left subtree is one taller than its right subtree ‘TR’ if its right subtree is one taller than its left subtreeb) We start an add operation by adding the new item into the AVL as leaves just like we did for Binary Search Trees(BSTs). Add the key 90 to the above tree?c) Identify the node “closest up the tree" from the inserted node (90) that no longer satisfies the height balancedproperty of an AVL tree. This node is called the pivot node. Label the pivot node above.d) Consider the subtree whose root is the pivot node. How could we rearrange this subtree to restore the AVL heightbalanced property of AVL tree? (Draw the rearranged tree below)Data Structures (810:052) Lecture 19 Name:________________Lecture 19B Page 12. Typically, the addition of a new key into an AVL requires the following steps: compare the new key with the current tree node’s key (as we did in the addHelper function inside the addmethod in the BST) to determine whether to recursively add the new key into the left or right subtree add the new key as a leaf as the base case(s) to the recursion as the recursion “unwinds” (i.e., after you return from the recursive call) adjust the balance factors of the nodes onthe search path from the new node back up to the root of the tree. To aid in adjusting the balance factors, we'llmodify the addHelper function so that it returns True if the subtree got taller and False otherwise. as the recursion “unwinds” if we encounter a pivot node (as in question (c) above) we perform one or two“rotations” to restore the AVL tree’s height-balanced property.For example, consider the previous example of adding 90 to the AVL tree. Before the addition, the pivot node wasalready “TR” (tall right - right subtree had a height one greater than its left subtree). After inserting 90, the pivot’sright subtree had a height 2 more than its left subtree which violates the AVL tree’s height-balance property. Thisproblem is handled with a left rotation about the pivot as shown in the following generalized diagram:Before the addition:After the addition, but before rotation:After left rotation at pivot:A AAB BB'TR' 'TR''EQ''EQ' 'TR''EQ'from parent from parentfrom parentTTTT TTT TT 3 3 2 1 1 1 3 2 2 heightheightheightheight heightheightheight heightheight n n n - 1 n - 1 n - 1 n - 1 n - 1 n - 1 n - 1newnewnodenodeRecursion has unwound to pivot (B's balance factor was already adjusted before the pivot is foundand indicated a taller subtree!RotateLeft atPivot as the recursion unwinds)a) Assuming the same initial AVL tree (upper, left-hand of above diagram) if the new node would have increased theheight of T2 (instead of T3), would a left rotation about the node A have rebalanced the AVL tree?Data Structures (810:052) Lecture 19 Name:________________Lecture 19B Page 2Before the addition, if the pivot node was already “TR” (tall right) and if the new node is inserted into the left subtreeof the pivot node's right child, then we must do two rotations to restore the AVL-tree’s height-balance property. Before the addition:After the addition, but before first rotation:After right rotation at B, but before left rotation at pivot:After the left rotation at pivot andfrom parent from parentfrom parentfrom parentT TTTT TTTT TTTT TTT 2R 2R 2R 2R 2L 2L 2L 2L 1 1 1 1 3 3 3 3 height heightheightheightheight heightheightheightheight heightheightheightheight heightheightheight n - 2 n - 1 n - 1 n - 1 n - 2 n - 2 n - 2 n - 2 n - 1 n - 1 n - 1 n - 1 n - 1 n - 1 n - 1 n - 1newnewnewnodenodenodeRecursion has unwound to pivot B's & C's balance factors have already been adjusted before and indicated a taller subtree!Rotate1st RotateLeft atRight atPivot Node BC CCCB BBBA AAA'EQ' 'TR''TR''EQ''EQ' 'TL''TL''EQ''TR' 'TR''TR''TL' the pivot was foundbalance factors adjusted correctly:b) Suppose that the new node was added into the right subtree of the pivot’s right child, i.e., inserted in T2L insteadT2R, then the same two rotations would restore the AVL-tree’s height-balance property. However, what should thebalance factors of nodes A, B, and C be after the rotations?Data Structures (810:052) Lecture 19 Name:________________Lecture 19B Page 3Consider the BinaryTreeAVL class that inherits and extends the BinaryTree class to include balance factors.from binarytree import *class BinaryTreeAVL(BinaryTree): def __init__(self, item, balance = 'EQ'): BinaryTree.__init__(self, item) self._balance = balance def getBalance(self): return self._balance def setBalance(self, newBalance): self._balance = newBalance def __str__(self): """Returns a string representation of the tree rotated 90 degrees to the left.""" def strHelper(tree, level): result = "" if not tree.isEmpty(): result += strHelper(tree.getRight(), level + 1) result += "| " * level result += str(tree.getRoot())+ " : " + tree.getBalance() + "\n" result += strHelper(tree.getLeft(), level + 1) return result return strHelper(self, 0)Now let’s consider the partial AVL class code that inherits from the BST class:class AVL(BST): def __init__(self): BST.__init__(self) def add(self, newItem): """Adds newItem to the tree.""" # Helper function to search for item's position def addHelper(tree): def rotateLeft(tree): newTree = BinaryTreeAVL(tree.getRoot()) newTree.setLeft(tree.getLeft()) newTree.setRight(tree.getRight().getLeft()) newTree.setBalance(tree.getBalance())