{"ref":null,"ref_type":"repository","master_branch":"master","description":" Requirement: BST, AVL and Splay Trees This assignment is for building and practicing with different tree structures. 1. First, write a TreePrint class that will allow you to print a BST (Max 26 - 1 = 63 nodes) given a sequence of numbers between 10 and 99. You may want to consider a matrix of x-y coordinates of line #s representing level #s as and horizontal position representing each node at the level. One example is shown below- however, you may use any different way to print your tree. Example of a Tree Output (also shown with the entire dot matrix): 00 == == == 00 == == == == ==== 00 00 00 00 ======== 00 00 00 00 00 00 00 00 ================ 0000 0000 0000 0000 0000 0000 0000 0000 ================================ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ￼ Write a program to do the following: BST Tree 2. For given lower and upper limits and number of nodes, generate a random sequence of unique numbers and then build a binary search tree and print it. 3. Delete values when requested. To show the output- you may show deleting any 2 keys in succession from your initial sequence- and then printing the tree after each deletion. AVL Tree 4. Build an AVL tree from the initial random sequence generated above. You will need to check the height balance after each insertion and adjust the heights by single or double rotations. Print the tree after each insertion and after each height balance operation. When you rebalance the tree- caption it with the type of rotation (L, R, LR or RL): (e.g. LR rotation: nodes 56, 45, 58) 5. Delete values from this AVL tree. Show an example of 2 successive deletions from the initial tree in the output. Remember- since the one rotation may not fix the imbalance- you need to recheck the height balance after the rotation and continue towards the root till the tree is balanced. Print the resulting tree with proper caption after each rotation operation). Splay Tree 6. Starting from the initial random sequence- generate a splay tree. 7. Delete keys from the Splay tree. Show an example of 2 successive delete operations on the initial Splay tree. Print the tree after each deletion along with the list of rotations performed.","pusher_type":"user"}