We saw in class that given a binary search tree with n elements, we can output t
ID: 673138 • Letter: W
Question
We saw in class that given a binary search tree with n elements, we can output the elements in sorted order using a 0(n) in-order tree walk. Use this fact and the (nlogn) lower bound on the number of comparisons needed to sort n elements, to prove a lower bound on the number of comparisons needed to build a binary search tree from a set of n elements. Give an algorithm that traverses the tree and stores on each node the height of that node in the tree. Show how to maintain this information when you insert or delete nodes. Argue the correctness and analyze the complexity of your algorithm.Explanation / Answer
Answer 1: Given there are n elements. Using these elements a Binary search tree is built.
To output the elements in the binary search tree takes O(n) order by using inorder tree walk.
If an inorder tree walk of a binary tree algorithm takes O(n) comparisons to sort the n elements then, there must be O(n) comparisons to sort all the n elements.
So, which means to sort the elements it takes only O(n) comparisons.
This is a contradiction. For any sorting algorithm of n elements it takes at most O(n logn) comparisons.
Thus, the lower bound of sorting n elements in a binary search tree takes Omega(n logn ).
Answer 2:
In order to maintain the height of the mode with respect to node information while inserting and deleting of the node, then, the node class need to contain one more variable to maintain the height of the node. Like the node class contains, a data variable, height variable, and a node reference variable.
In insertion, when a node is added, automatically all the nodes height value should also be updated.
Similarly, in deletion, when is node is deleted, the rest of the nodes height also should be updated.
Thus, the height of the node can be maintained along with the node information.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.