Given two B-trees of some order $m$ - $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$. What is the fastest way to create a new tree that is the union of both $T_1,T_2$?

My current solution is naive in a sense that I create an array and insert all $T_1$ elements, than all $T_2$ elements. As a result I have a sorted array which I can create a new tree off of with a cost of $n \log n$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.

  • $\begingroup$ This isn't an answer, but for B+-trees, by far the easiest solution is to do a merge of the leaf nodes, and then build the branch nodes. $\endgroup$
    – Pseudonym
    May 5 '20 at 2:04

It is great that you have obtained a sorted array, which runs in $O(n)$ time.

Once we have $n$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $O(n)$. In particular, we can build a $B$-tree in $O(n)$ time.

Here is an example. Suppose the sorted array is $$[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17]$$ and we want to build a $2$-$4$ $B$-tree. Split the array into groups of $2$ numbers, except that last group that could be $2$ or $3$ numbers. $$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12\}, \{13,14\}, \{15,16, 17\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12, 13\}, \{14,15,16, 17\}.$$

Label the groups successively as $g_1, g_2, \cdots, g_7$. Let $g_1$ be the root of the tree. Let the left child of $g_i$ be $g_{2i}$ if $2i\le n$ and the right child of $g_i$ be $g_{2i+1}$ if $2i+1\le n$. Now we have a complete binary tree where

  • each node contains at least 2 number, and
  • each internal node has 2 children.

That means, it is a $2$-$4$ $B$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.

  • 1
    $\begingroup$ While it is correct that every kind of "nice" tree, including $B$-tree can be built in $O(n)$ given a sorted array, my $B$-tree is not fully correct. (I would like to spend more time to explore whether there is a $O(\log n)$ way in the case of $y>x$ for every pair $x\in T_1$ and $y\in T_2$ as well.) $\endgroup$
    – John L.
    May 5 '20 at 13:51
  • 1
    $\begingroup$ Yes, $O(\log n)$ can be done, easily ...updating ... Drawing graphs is time-consuming ... $\endgroup$
    – John L.
    May 7 '20 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.