B tree

#1 08-13-2008, 03:58 PM

hi all
i'm learning data structures and i have a question regarding b-trees.
suppose we have 2 B-trees: A and B, both of order m. one has a keys
and the other b keys. we know that all the keys in A are smaller than
the keys in B.
how can we make one B tree of order m out of both of them in
O(log(max(a,b))?

#2 08-13-2008, 11:21 PM

On Aug 13, 12:58*pm, "maverickc...@gmail.com" <maverickc...@gmail.com>
wrote:
> hi all
> i'm learning data structures and i have a question regarding b-trees.
> suppose we have 2 B-trees: A and B, both of order m. one has a keys
> and the other b keys. we know that all the keys in A are smaller than
> the keys *in B.
> how can we make one B tree of order m out of both of them in
> *O(log(max(a,b))?

Without loss of generality assume b < a. The idea is to insert the
root of B at the appropriate level of A and rebalance A. That would
take log(a) effort. Then, since root of B is placed at ther correct
level the combined tree A+B is balanced.

#3 08-14-2008, 12:15 AM

On Aug 14, 6:21*am, Tegiri Nenashi <TegiriNena...@gmail.com> wrote:
> On Aug 13, 12:58*pm, "maverickc...@gmail.com" <maverickc...@gmail.com>
> wrote:
>
> > hi all
> > i'm learning data structures and i have a question regarding b-trees.
> > suppose we have 2 B-trees: A and B, both of order m. one has a keys
> > and the other b keys. we know that all the keys in A are smaller than
> > the keys *in B.
> > how can we make one B tree of order m out of both of them in
> > *O(log(max(a,b))?
>
> Without loss of generality assume b < a. The idea is to insert the
> root of B at the appropriate level of A and rebalance A. That would
> take log(a) effort. Then, since root of B is placed at ther correct
> level the combined tree A+B is balanced.

thanks

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode