Student Name: 13. Describe the procedure for removing a value from a binary sear
ID: 3709752 • Letter: S
Question
Student Name: 13. Describe the procedure for removing a value from a binary search tree when the value to be removed has two "children". 14. What is the minimum height of a binary tree containing n items 15. What is the maximum height of a binary tree (unbalanced) containing n items? 16. Adding, removing, and finding values in a binary search tree have the Big-O value for performance in time. List the best case and the worst case performance for adding a value to a balanced and ordinary (unbalanced) binary tree. Hint: They are different! 17. When adding to an ordinary (unbalanced) binary tree, under what conditions does the worst case occur? 18. In a binary search tree, while attempting to find a value, how does the program determine that the value is not in the tree? 19. In a binary search tree, if an "in order" traversal of the tree is performed and each value is printed as it is encountered, would the values be printed in sorted, or unsorted order? 20. What is the purpose of the Visitor interface and the classes that implement it in the binary tree program we built in class? 21. Does your name appear in the heading of this page? If not, put it there.Explanation / Answer
Solution:
Note: The first four subparts have been answered as per Chegg guidelines, please repost others.
13)
When the value to be removed has two children then what we will do is we will replace the value with its immediate predecessor or immediate successor and then we will remove the value from the tree.
In this way, the property of BST won't be violated.
14)
The minimum height can be achieved only when the tree is a complete binary tree or full tree.
then the height can be O(log n)
15)
Maximum height will be produced when the tree is either left skewed or right skewed then the tree will have the hight O(n).
16)
Best cases will happen when the tree is balanced. here the height will be O(log n)
In the worst case, the height of the tree will be O(n)
Insertion:
Best case: O(1)
Worst case: O(n)
Search:
Best case: O(1)
Worst case: O(n), O(log n) when the tree is balanced
Delete:
Best case: O(1)
Worst case: O(n), O(log n) when the tree is balanced
basically to delete we need to find the element first which needs to be deleted.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Best case: O(log n)
Worst case: O(n)
Best case: O(log n)
Worst case: O(n)
Best case: O(log n)
Worst case: O(n)
Best case: O(log n)
Worst case: O(n)
Best case: O(log n)
Worst case: O(n)
Best case: O(log n)
Worst case: O(n)