Re: B tree
- From: "maverickcool@xxxxxxxxx" <maverickcool@xxxxxxxxx>
- Date: Wed, 13 Aug 2008 21:15:14 -0700 (PDT)
On Aug 14, 6:21 am, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
On Aug 13, 12:58 pm, "maverickc...@xxxxxxxxx" <maverickc...@xxxxxxxxx>
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
.
- References:
- B tree
- From: maverickcool@xxxxxxxxx
- Re: B tree
- From: Tegiri Nenashi
- B tree
- Prev by Date: Re: B tree
- Next by Date: Re: This year's Godel Prize
- Previous by thread: Re: B tree
- Next by thread: This year's Godel Prize
- Index(es):
Relevant Pages
|
