bst complexity

[hider]

hi
please i am confused with bst complexity

what is the complexity for
balanced
search
insert
delete
-------------
unbalanced
seach
insert
delete

please help and correct me if i am doing things wrong

thanx

[Rashakil Fol]

hi
please i am confused with bst complexity

what is the complexity for

Wait a second. You can't ask for a complexity without giving us algorithms. You've only explained the function of the algorithms, not the implementation. You haven't asked if you want a worst-case, average-case, or best-case value.

Generally speaking, the worst-case runtime for sanely-written search, insertion, and deletion algorithms is O(h), where h is the height of the tree.

[hider]

hi

well if you noticed from the start i said i am confused. there are many cases and i need some one to explain all the cases yes i need to know best worst and average for all

now for balanced
B - O(1)
A - LOG(N)
W - 0(N)

UNbalanced
B - ?
A - ?
W - 0(N)

for search balanced BAW (MEANS BEST AVERAGE WORST)?
for insert balanced BAW= ?
for DELETE balanced BAW= ?

......

I APPRECIATE YOUR HELP IF YOU HAVE A LIST OR A SITE EXPLAIN ALL THE CASES.
THNAX

I HAVE AMIDTERM IN 4 DAYS.

[Narue]

>now for balanced
>B - O(1)
>A - LOG(N)
>W - 0(N)
You're not thinking in terms of scalability. The best case performance for a balanced binary search tree during search operations is O(log N), so is the average and worst case, which is why balanced trees are so desirable. Insertion and deletion strategies can vary from the naive and inefficient to the complicated and fast, so the cases can vary from O(N) or worse to O(log N). Assuming a decent balancing strategy like AVL, you can expect search, insertion, and deletion to be O(log N). But that depends heavily on the quality of the implementation.

Unbalanced binary search trees are harder because the performance relies on the order in which data arrives or is deleted. But in general terms, the worst case of an unbalanced tree is O(N) and the best case is O(log N). The average case varies between O(N) and O(log N) for degenerate sequences and random sequences, respectively.

[Rashakil Fol]

Narue must mean a different thing by best case then (than what I usually mean).

Given one way to interpret the term, the best case for search is O(1) in both the balanced and unbalanced cases. This happens when the root node contains what we're looking for. The best case for insertion and deletion in a balanced tree is still O(log n).

The best case for insertion, and deletion in an unbalanced tree is O(1).

If you average the runtime of these operations over all the keys in the tree, and measure this runtime, then Narue's statements are correct, and that is probably the measurement she was implying.

Anyway, this message is for the other poster, not Narue, since Narue knows what she's talking about. (Hopefully, now hider also knows what Narue's talking about.) Anyway, hider, you'll have to decipher what they mean on your midterm as to what they are measuring when discussing runtimes.

[lakshmivenkat]

Hi,
I raed in one of the book that the worst case time complexity of binary search tress is 0(h).but I want to know what is thw best case and average case time complexity.

[thoughtcoder]

Do something thinking and figure it out for yourself.