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.
Rashakil Fol
Super Senior Demiposter
2,658 posts since Jun 2005
Reputation Points: 1,135
Solved Threads: 177
>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.
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
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.
Rashakil Fol
Super Senior Demiposter
2,658 posts since Jun 2005
Reputation Points: 1,135
Solved Threads: 177
