Consider a binary search tree that contains n nodes with keys 1, 2, 3, .. ., n.
ID: 3795714 • Letter: C
Question
Consider a binary search tree that contains n nodes with keys 1, 2, 3, .. ., n. The shape of the tree depends on the order in which the keys have been inserted in the tree. In what order should the keys be inserted into the binary search tree to obtain a tree with minimal height ? On the tree obtained in a, what would be the worst-case running time of a find, insert, or remove operation? Use the big-Oh notation. In what order should the keys be inserted into the binary search tree to obtain a tree with maximal height? On the tree obtained in c, what would be the worst-case running time of a find, insert, or remove operation? Use the big-Oh notation.Explanation / Answer
4)
a) Let keys of the nodes are a,2,….n. To obtain a tree with minimal height, insert the nodes in following
order
This will divide the whole list into parts ,I,e
left list : 1.. m-1 and right list : m+1….n
Example: Lets keys are [1,2,3,4,5,6,7,8,9,10,11,12,13,14]
Median: 7
Insert 7:
left list: [1,2,3,4,5,6] right list: [8,9,10,11,12,13,14] Proceeding through left list, median =3
Insert 3
left list: [1,2] right list: [4,5,6] . Proceeding through left list, median =1
Insert 1
Left list: empty, right list: [2]. No left list, proceed through right list: median 2
Insert 2
Empty left list and empty right list. Proceed through right list of previous node I,e 3.
List: [4,5, 6] , median 6
Insert 5
Left list : [4] Right List: [6]
Insert 4
Insert 6
Proceed through right list of 7 I,e [8,9,10,11,12,13,14]
Repeat same steps as above
Insert 11 , Insert 9, Insert 8, Insert 8 Insert 10, Insert 13, Insert 12, Insert 14
So the order of insertion is 7,3,1,2,5,4,6,11,9,8,10,13,12,14
-----------------------------------------------------------
4. B)
Now the obtained tree is balanced, Its height will be O(logn),
So Worst case running time of
FIND operation:
If the searched node is present in any of the leaves, It takes a maximum of O(logn) time to complete.
INSERT Operation:
As the tree balanced ,to insert a node in the tree, It must traverse a single path from root to the appropriate leaf node and then insert the node. To traverse the tree ,again it requires O(logn) time on worst case
REMOVE operation:
To remove a node , first find the location of that node and them make some alteration/change in order to fix the position of parent and child of the deleted node.
In worst case if the node present at leaves, a O(logn) time is required to find it. And the O(1) tim,e required to fix the position. So a total of O(logn)+O(1) = O(logn) time is required
----------------------------------------------------------------------------
4.C)
--------------------------------------
4. c) Let keys of the nodes are a,2,….n. To obtain a tree with maximal height, insert the nodes in following
order
As the keys are already in sorted in ascending order
Simple insert the nodes in that order,
[Notes: inserting nodes in descending order also makes the tree maximum height
So order of insertion is [ 1,2,3,4,5,6,7,8,9,10, ……… n]
------------------------------------- --------------------------------------------------
4. d)
-------------------------------------------------------------------
Now the obtained tree is skewed to right.
So Worst case running time of
FIND operation:
As all the node are present to the right to its parent, If the searched node is present at the last right child node(leaf), It must traverse entire node present in the tree. A number of node is n, It takes O(n) time for FIND operation.
INSERT Operation:
Worst case occurs if the node to be inserted is greater the n. To insert it we must traverse the entire tree to find inserting node parent and the insert the node. So it requires O(n) time
REMOVE operation:
To remove a node , first find the location of that node and them make some alteration/change in order to fix the position of parent and child of the deleted node.
In worst case if we remove the node with key n. (the leaf node). It is present at last child node of the tree.To find it , n number of comparison is needed. So REMOVE Operation takes O(n) time
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.