Generate a random sequence from Random.org and explain how the AVL Tree changes by drawing the AVL Tree in detail at each step.

Step 1 (Insertion)

Assume an empty AVL Tree.

Generate a random sequence.

(https://www.random.org/sequences/?min=1&max=100&col=1&format=html&rnd=new)

Insert the first 10 numbers from the sequence.

For each number insertion, describe the graph after insertion, and the graph after rebalancing (if possible).

- If imbalance does not occur during insertion, the result tree in which the number is inserted is displayed.

- If imbalance is detected during insertion, write what imbalance occurred and explain how you performed rebalancing. (Please write detailed explanations)

After inserting 10 numbers, if there was imbalances less than 2 times, insert 2 more numbers that cause imbalance.

Step 2 (Deletion)

Repeatedly delete root in the tree where all numbers are inserted.

- In every deletion, if an imbalance is not detected during deletion, the result tree in which the number is deleted is displayed.

- In every deletion, if imbalance is detected during deletion, please explain what imbalance occurred and how you rebalanced it.

After deleting all numbers, if there wasn’t any imbalance, do Step 3, too.

Step 3 (Deletion – optional step based on the result of Step 2)

During step 2, if there wasn’t any imbalance, delete numbers which occur imbalances from the tree after Step 1. Then show the imbalance and rebalancing. (at least one rebalancing)

Caution

- If you draw just changes of the tree without any explanation, possibly you will get up to 50% of this assignment.

Submission:

- Submit one file. (pdf, word, pptx, and so on)

- You can create a report using a computer such as PowerPoint or Word.

- When hand-drawn in a note, it must be clear and readable. (If the instructor or TA cannot understand the content, points will be deducted)

- For handwriting, scan or take a photo and submit it as a single document file. (pdf format is preferred)