Consider an application that frequently inserts data into a BST and even more fr
ID: 3808044 • Letter: C
Question
Consider an application that frequently inserts data into a BST and even more frequently performs searches on these data. Because of the high demand for search operations, this application simply can't afford the worst-case searches of a BST (i.e., (n)). To this end, it frequently has to check the height of the BST so it can rebalance it if necessary. It is your chance to show your value to the company and improve their application.
Your first job is:
a) To implement an operation called TREE-HEIGHT(x) that (efficiently) calculates the height h of a node x in the BST of Chapter 12 (i.e., h=#levels-1);
b) Next, answer what the time and space complexity of your implementation is;
After a few tests though, you realize that your time complexity is still too high for the application. Therefore, you decide to approach the problem from a different perspective. You decide to add an extra field to each node in the BST that stores the height of that node in the tree. That should allow you to look up the tree height in constant time.
So your second job is:
c) To make all necessary changes to TREE-INSERT(T,z) and TREE-DELETE(T,z) to accommodate an extra field for the height of each node;
d) To implement another operation called TREE-HEIGHT-LOOKUP(x) that retrieves the height h of the node x in constant time;
Now, your third and final job is:
e) To evaluate and discuss your 2 approaches by answering: "Which of the 2 applications is more efficient? The one with TREE-HEIGHT(x) or the one with TREE-HEIGHT-LOOKUP(x)?" Explain.
*Tip: Note that by allowing constant time height look-ups, you added some overhead in computing 2 other operations.
Explanation / Answer
a)To compute the tree height, we compute the height of the left subtree and height of right subtree, and return whichever is maximum
Algorithm for TREE_HEIGHT(x)
leftheight=0
rightheight=0
if x == NULL
RETURN 0
else
if x.left!=NULL
left_height=1+TREE_HEIGHT(x.left_child)
endif
if x.left!=NULL
left_height=1+TREE_HEIGHT(x.right_child)
endif
return MAX(left_height,right_height)
endif
b) The above algorithm travels all nodes in the tree every time the height of the tree is needed. So its of O(n). This is too high. So we try to store a variable
'height' in the node along with left and right children. This helps us to just look up the value in the node rather than computing it for all nodes every time.
c) In the insert operation , we need to set adjust the parent's height whenever its less than the actual value. This goes till the point the correct height or bigger height is seen in the parent
or we reach the root node
TREE_INSERT(T,z)
set z.height=0
current=z
parent=z.parent
while parent!=NULL && parent.height < 1+current.height
parent.height=1+current.height
current=parent
parent=current.parent
end while
d) TREE_HEIGHT_LOOKUP(x)
return x.height
e) The application with TREE_HEIGHT_LOOKUP() is better since its of constant time to look up the height of tree. Also computation of height for any node does not require calculation of heights of all nodes in tree. The maximum number of nodes that need recomputation in worst case is O(log n) since we only access the parent and go one level up. So 2nd approach is better for the application.