Having trouble with this question with binary trees. Ive tried making diagrams but dont understand howr the rotations work or anything: Each friend needs only to keep track of three items of information: their own birthday
(which of course they do not need to write down), the name of someone whose birthday comes earlier in the year than
their own (which they write on a card and keep in their left pocket), and the name of someone whose birthday comes later
in the year (which they write on a card and keep in their right pocket).

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 reorganisation, 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.
COMP2711/8801 Flinders University
Computer Programming 2
Flinders University / College of Science and Engineering 3
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 reorganise the BST so that subsequent SEARCH times are minimised. You don't 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)