Homework 3
Due: Tuesday, 3/27/2022, by 8:00amOverview
Do your own work for this assignment; do not work with others. Consult the resources provided and your professor for help if you need it. Please type your answers. Use good grammar, correct spelling, and complete sentences.
This assignment will be submitted on iLearn by the deadline and you will bring a physical printed copy at the beginning of class whenever that is for your section. Homework turned in after the deadline will not be accepted. Homework turned in after I have collected it will lose 20%. Please do not email late homework to your professor.
Any code you write should "just work" if the professor types it in and compiles and runs it.
Total points: 60.
Each problem (not including the extra credit) is worth 10 points.
Assignment
- 1. Exercise 4.19 from your book. Show the tree after each insertion (before rebalancing), point out each imbalance (when they occur), and show the tree after rebalancing (if it is necessary).
-
2. Show how the following AVL-balanced tree will change after removing each
of the following nodes: 17, 13, 20, and 2. After removing each node, it
should remain removed for the rest of the exercise. Make sure that your
changes are clear.
- 3. Exercise 4.27 from your book. Like the previous problem, show the tree after each access. For each rotation, clearly indicate its type, location in the tree, and direction(s) of rotation.
-
4. Extra credit: For the BSTNode class from project 3, write a
function called duplicate() with the following signature:
BSTNode duplicate() { // - }This function should return a deep copy of the node it is called on and the entire subtree below it. Using recursion, I can write this function in one or two lines. Try for the simplest function possible, but make sure it's correct - test it! - 5. Exercise 6.2 from your book. For part (a), show a tree representation and an array representation for each insertion. For part (b), show the final result as a tree and as an array.
- 6. Exercise 6.3 from your book. Use the answer you got from part (a) of exercise 6.2, and show the array and the tree representation after each deleteMin.
- 7. Exercise 6.6 from your book.
- 8. Extra credit: Exercise 6.12 from your book. You should turn in your code as well as your timing results.
- 9. Extra credit: Read the 2022 Developer Survey by StackOverflow. Write about something you learned from it. I am particularly interested in knowing what fact or statistic has changed your perception about something, e.g. salary, gender, languages, frameworks, ethics, etc. Write about what you thought in the past and what made you reconsider or changed your mind. For this, submit a short essay between 150 and 250 words as part of your homework.