Consider the approaches to dealing with equal keys in a Binary Search Tree, desc

Question

Consider the approaches to dealing with equal keys in a Binary Search Tree, described in CLRS, 12-1:b,c, pages 303-304. What is the worst-case asymptotic time (with respect to n) needed to insert n copies each (in turn) of the numbers 1 through n. For example, if n = 10, then there we will be inserting ten 1's followed by ten 2's followed by ten 3's, ... ten 10's.

CLRS 12-1

b.Keep a boolean flag x:b at node x, and set x to either x:left or x:right based on the value of x:b, which alternates between FALSE and TRUE each time we visit x while inserting a node with the same key as x.

c.Keep a list of nodes with equal keys at x, and insert into the list.   

Explanation / Answer

The wrost case asymptotic time for binary search tree is O(n).

The tree can a unbalance tree in worst case.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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