We can try rotation too.
1.We iterate rotating of the left/right sub-tree having greater number of
nodes.
2. if number of keys are :-
ODD-> Equal number of nodes exist on both left and rt subtree of root .Key
at root is the median of the BST..
EVEN->left subtree should have 1 less node than right.Both root node and a
node just below on the rt. sub tree will be the median.
On Sat, May 15, 2010 at 2:31 AM, W Karas <wka...@yahoo.com> wrote:
> On May 14, 3:32 am, divya <sweetdivya....@gmail.com> wrote:
> > please suggest an efficient algo to find the median of a bst
>
> A recursive solution:
>
> unsigned count(node_handle_t base)
> { return(base == null ? 0 : count(left(base)) + 1 +
> count(right(base))); }
>
> val_t max(node_handle_t base)
> { return(right(base) == null ? val(base) : max(right(base))); }
>
> val_t min(node_handle_t base)
> { return(left(base) == null ? val(base) : min(left(base))); }
>
> val_t median_help(
> node_handle_t base,
> unsigned low_count,
> unsigned high_count)
> {
> unsigned left_count, right_count;
>
> left_count = count(left(base));
> right_count = count(right(base));
>
> low_count += left_count;
> high_count += right_count;
>
> if (low_count == high_count)
> return(val(base));
>
> if (low_count == (high_count + 1))
> return((val(base) + max(left(base))) / 2);
>
> if (high_count == (low_count + 1))
> return((val(base) + min(right(base))) / 2);
>
> if (low_count > high_count)
> return(median_help(left(base), low_count - left_count,
> high_count + 1));
>
> /* low_count < high_count */
> return(median_help(right(base), low_count + 1, high_count -
> right_count));
> }
>
> val_t median(node_handle_t root)
> { return(median_help(root, 0, 0)); }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
