OJ Board

the problem statement says, a binary search tree is a data structure, which can find a node in O(n log n). Of course this is a true statement (because of the O-symbol), but even with the worst case tree, one can find any node in O(n). If the tree is balanced it's even O(log n).

palmcron wrote:the problem statement says, a binary search tree is a data structure, which can find a node in O(n log n). Of course this is a true statement (because of the O-symbol), but even with the worst case tree, one can find any node in O(n). If the tree is balanced it's even O(log n).

lol, nice mistake . Have you tried to write an e-mail to the problem setter? There is an e-mail address at the end of the problem statement. Hopefully, he'll fix it.

And depending on the leafs, it can be found in the first search. Anyway, as the description is talking about average time, I think that an average time for all possible trees is O(log n), and it looks like it's what the problemsetter meant.

I've changed the description. If i'm wrong (I'm not a data strcture expert) tell me. If there are no replies in one week I'll close the topic.

The current text is

A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v) <label (k) and any node w reachable from its right has label (w) > label (k). It is a search structure which can find a node with label x in O(log n) average time, where n is the size of the tree (number of vertices).


I would suggest changing it to (changes are given in bold font)

A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) < label (k) and any node w in the right subtree of k has label (w) > label (k).

(When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).)


The rationale for the changes:
- The first new text is more correct than "reachable from its left" (and probably more clear too )
- There are degenerate BSTs where the average time to find a node is linear in n. But in this problem we are supposed to count all BSTs, including the degenerate ones. The original formulation is slightly deceiving. That's why it's better to give it a separate paragraph and to put it into parentheses.

I fully agree with misof's suggestion.

I've just changed the description. I didn't put the parenthesis. It was strange as that sentence inside the ()'s is a paragraph itself.

Thanks a lot for this correction!!