Write the following code in C$++$ In this assignment, we will explore functions that may improve the performance of AVL trees.

Even though AVL trees maintain a balance factor of $1$ that ensures the search complexity stays

close to log$2($n$),$ it may suffer from increased complexity during insertion and deletion if these

operations are done frequently and the number of rotations is high. Two optimizations are

explored in this assignment.

$1.$ Batched Updates:

Batched updates are a technique used to optimize the efficiency of performing multiple

insertions or deletions on a data structure, such as an AVL tree. Rather than applying each update

individually and rebalancing the tree after each operation, batched updates involve queuing

multiple updates and applying them together in a single batch. Here's how batched updates

typically work:

$1.$ Queueing Updates: When a new insertion or deletion operation is requested, instead of

immediately applying it to the AVL tree, the update is added to a queue $($e$.$g$.,$ a queue data

structure$).$

$2.$ Processing Batched Updates: Periodically or when the queue reaches a certain size, the

batched updates are processed together. This involves applying each update in the queue to the

AVL tree sequentially. In this assignment, we will process batched updates when we have $5$ items

in the queue.

$3.$ Rebalancing of the tree: After processing all updates in the batch, the AVL tree is rebalanced

once to ensure that it maintains the AVL property $($i$.$e$.,$ the height difference between the left

and right subtrees of any node is at most $1).$

$2$

$2.$ Lazy Deletion:

Lazy deletion is a technique used to optimize the removal of nodes from a data structure, such

as an AVL tree. Instead of immediately removing a node when a deletion operation is requested,

lazy deletion involves marking the node for deletion and deferring the actual removal until later.

Here's how lazy deletion typically works:

$1.$ Marking Nodes for Deletion: When a deletion operation is requested, instead of immediately

removing the target node from the AVL tree, the node is marked as "deleted" or "inactive." This

typically involves setting a flag or attribute in the node's metadata to indicate its status.

$2.$ Deferred Removal: The actual removal of marked nodes is deferred until a later point, such as

during a rebalancing operation that takes place during insertion. This means that the AVL tree

structure remains unchanged immediately after a deletion operation, and the marked nodes are

still considered part of the tree.

$3.$ Rebalancing and Cleanup: During a rebalancing operation or at a designated cleanup stage, the

AVL tree is traversed, and any marked nodes are removed from the tree. This may involve

updating pointers, adjusting tree structure, and performing any necessary rebalancing steps to

maintain the AVL property.

Your task is to use the code of the AVL tree from the lecture as the skeleton code

for this assignment and modify the insertion and deletion functions to implement

batched updates and lazy deletion. You can use vectors to implement the

insertion queue. You are required to write a main program to demonstrate the

operation of the modified function