This Task is about AVL tree and you need to write the code by C++

An AVL tree is a binary search tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by at most 1. To implement an AVL tree, we maintain an extra attribute in each node: x:h is the height of node x. As for any other binary search tree T , we assume that T:root points to the root node.

1. Write the pseudocode for RIGHT-ROTATE (Hint: Its symmetric to LEFT-ROTATE)

2. To insert into an AVL tree, we first place a node into the appropriate place in binary search tree order. Afterward, the tree might no longer be height balanced. Specifically, the heights of the left and right children of some nodes might differ by 2. Describe a procedure BALANCE(x), which takes a subtree rooted at x whose left and right children are height balanced and have heights that differ by at most 2, i.e., |x.right.h - x.left.h|

3. Using part (b), describe a recursive procedure AVL-INSERT(x; z) that takes a node x within an AVL tree and a newly created node z (whose key has already been filled in), and adds z to the subtree rooted at x, maintaining the property that x is the root of an AVL tree. As in TREE-INSERT from the previous class, assume that z.key has already been filled in and that z.left = NIL and z.right = NIL; also assume that z.h = 0. Thus, to insert the node z into the AVL tree T , we call AVL-INSERT(T.root, z).

Test your code on the following sequence of characters:

H, I, J, B, A, E, C, F, D, G, K, L

Example Output:

Please finish this task by C++(code

E B F-1 D 0 Final AVL Tree 0 (Balanced)