where do we put a member which equals to the root
on the left
or on the right
??
where do we put a member which equals to the root
on the left
or on the right
??
Under my understanding of the traditional BST, you don't put it anywhere (duplicates are not added). If you're in a multimap-ish situation where you've got a key and a value, you would probably use the value to break ties, I guess. But adding a duplicate is a little silly, since you will never find it in a search.
thanks
how can i look for the node which is the least bigger
then some number
amongst all
if i am looking for bigger then 3 in the tree
and i got nodes 4 6 8 9 (tree nodes)
it will pick 4
??
Last edited by transgalactic2; 10-30-2008 at 01:28 PM.
Off the top of my head: I would search for the number. If I found it, take the least element of the right subtree. (If the right subtree is NULL, I'd have to go up a level and do some cases -- if I went left to get my number, then the parent would be the next largest element; if I went right, then I go up another level and do it again. If I don't have another level to go up, my number is maximal.) If I miss, I'd have to do something similar, I would think.
Anyway, it feels a little recursive to me. I would draw some pictures to make sure I got all my cases right.