2a i) What is the time taken to insert a new key k into a binary search tree (BS

Question

2a i) What is the time taken to insert a new key k into a binary search tree (BST) containing N keys, where k is not already in the tree, in the best case and the worst case? Explain your answer What is the time taken for the operation described in (i), in the case of a BST that has the same shape (exactly the same parent-child relationships) as a red-black tree containing the same keys? Explain your answer. ii) ii) Given a red-black tree containing N keys and an identically shaped BST containing the same keys, as in (ii) above, and a new key k as in (i), would you expect it to take longer to insert k into the binary search tree or into the red-black tree? Assume that all operations common to both insert procedures take the same time. Your answer should explain why the longer insertion takes longer, and how much extra time is taken, in notation. b i) What is collision resolution in hash tables and why is it necessary?

Explanation / Answer

Solution:

2 a)

i)

In the best case we will have a complete bionary tree whose height is know to be O(log n)

and the insertion is done at the leaf node in a binary search tree, this means that the best case insertion will take at least O(log n) time, where n is the number of vertices in the tree.

in the worst case,

we will be having a left-skewed tree and right-skewed tree whose height is of n size

so in the worst case in such tree it will take O(n) time.

ii)

In this case both the cases, best case and the worst case will take O(log n) time to insert

since the tree is balanced and a balanced binary search tree is closed to a complete binary search tree whose height is known to be log n.

iii)

In this case, since both the red-black tree and the BST are identically alike, which means the height of the tree is log n

Now adding a new key k

it would not take any longer and it will be O(n)

b

i)

collision resolution is a technique in which we use the hash functions creatively to try and minimize the number of collisions as much as possible.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.