Re: B tree
- From: Tegiri Nenashi <TegiriNenashi@xxxxxxxxx>
- Date: Wed, 13 Aug 2008 20:21:34 -0700 (PDT)
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.
.
- Follow-Ups:
- Re: B tree
- From: maverickcool@xxxxxxxxx
- Re: B tree
- References:
- B tree
- From: maverickcool@xxxxxxxxx
- B tree
- Prev by Date: This year's Godel Prize
- Next by Date: Re: B tree
- Previous by thread: B tree
- Next by thread: Re: B tree
- Index(es):
Relevant Pages
|
