P3) Suppose that you are given an array of integers A, which is sorted in ascend
ID: 3701065 • Letter: P
Question
P3) Suppose that you are given an array of integers A, which is sorted in ascending order. You need to construct a Binary Search Tree T for A. As we learned in class, the sequential insertions with these sorted integers may result a very tall and unbalanced tree called spine, which we want to avoid. (30 points) (a) Explain why spine is undesired in Binary Search Tree. tb) Then, describe your idea how to minimize the height of the tree (in other words, make your tree balanced) when you construct T'fromAExplanation / Answer
/*Do like the solution*/
a) The concept of binary search tree is to minimise the search time from linear to log(n) but in case of spine the BST behaves like an array which does not make use of the property of BST and worst case of search becomes O(n) time instead of O(log(n)).
b) Height can be minimised by balancing height of each node in the BST i.e, by making AVL tree which uses the concept of balance factor in which the balance factor of each node is from -1 to 1 that is height of left subtree minus height of right subtree if the balance factor of a node do not fall in range from -1 to 1 then that subtree is rotated to make it balnced this keeps the search time of any element O(log(n)) time in worst case.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.