QUESTION 2: Knowing that Sally's BST could become inefficient, you have devised a Repair Over-Time Acknowledgement To Enquiries procedure (ROTATE for short), which Sally can use to rearrange friends in the BST. The procedure comes in two variations: ROTATE-L and ROTATE-R.

You have drafted the following email, which Sally can send to people who need to use the ROTATE-L procedure to change one of their friends. If she needs someone to use the mirror-image ROTATE-R procedure, she would substitute the words in bold with the words in parenthesis.

Dear My BST needs reorganization, and I need your help. Please call the friend I have asked you to change and pass on the following instructions: Call your right-pocket (left-pocket) friend, ask them the name of their current left-pocket (right-pocket) friend, and tell them to replace that name with yours. Then tell me your friend's name and replace their name on the card in your pocket with the one they reported to you. When you have finished the call to your friend, replace their name on the card in your pocket with the name they reported.

For example, if Sally emailed Harry asking him to change his right-pocket friend using ROTATE-R, he would call Marge and pass on the instructions above. Marge would then call John (her left-pocket friend), who will report that his current right-pocket friend is nobody and then make Marge his new right-pocket friend. Marge would therefore replace her left-pocket friend with nobody and report John's name to Harry. Finally, Harry would make John his new right-pocket friend.

Sally has sent you a record of the order in which she INSERT-ed friends into her BST. (Note that in this case, Hananah starts out being the best friend, as she is added first. The best friend will not necessarily be the same person throughout the lifetime of the BST.) Name Birthday Hannah 8 August Georgie 7 July Dani 4 April Callum 3 March Feroz 6 June Abby 1 January Ben 2 February Ethan 5 May

Draw a diagram of Sally's current BST and compile a list of the sequence of ROTATE emails Sally would need to send in order to reorganize the BST so that subsequent SEARCH times are minimized. You dont need to include the full text of the emails, but your list should indicate who to send the email to, which friend needs to be changed, and which form of ROTATE to use. Include intermediate diagrams showing the effect of each rotation on the BST. Note that it may be necessary for Sally herself to change her best friend using a ROTATE. Further Explanation: These operations correspond to the standard rotate operations that are defined for a binary search tree. For this question and also the next one, you are asked to create diagrams to illustrate what happens as the tree is rotated. These diagrams do not need to be created with software; images/photos of neat hand-drawn diagrams are fine.

You should draw the initial state of the BST after all of the friends have been added, in the order shown above. Next, you should provide a diagram to show the effect of every rotation applied in order to balance the tree. For this question, you should finish with a balanced tree that provides optimal efficiency for inserting and searching (i.e. not using the AVL definition of a balanced tree, which will be used in question 3)

QUESTION 3: You have heard about a scheme called Automatic Variation Levelling (AVL), which will make sure that Sally's BST never becomes inefficient. AVL works by making sure that the maximum number of relayed calls needed to answer a SEARCH via the left-pocket friend and the right-pocket friend are about the same. Devise a modification to the INSERT procedure that will implement AVL so that Sally never has to manually reorganize her BST again. Illustrate your scheme's performance by INSERT-ing the same series of friends as listed in Question 2 above and showing that the BST remains efficient. Include intermediate diagrams showing the effect of each rotation on the BST. Further Explanation: For question 3, you should show how the tree will be continually balanced using the AVL algorithm. Your answer here will include the sequence of diagrams illustrating each step, as before. Note that question 2 and 3 ask for different things. In question 2, all of the friends are first added to a binary search tree, and then after that, we perform a series of rotations to balance the tree. In question 3, we add the friends in one-by-one and perform tree rotations as we go along, whenever this is required by the AVL algorithm.

Can you please help me with this questions, and yeah please give me full process like from insertion to the end of process like balanced tree and give detail explanation so that I can understand it properly .

In QUESTION 2 do not have to use AVL method to balance the tree instead of that you can use it in the question 3 and please give me every details of this process and please start from the insertion process .

and make sure the answer can understandable for every one so it will help me and someone else also, and do not use another platform to answer please