Search code examples
calgorithmgraphb-tree

Can a B tree have more solutions?

I have this values

10,15,20,25,30,33,38,40,43,45,50

and then I insert 34

I tried 2 generators
https://s3.amazonaws.com/learneroo/visual-algorithms/BTree.html
http://ysangkok.github.io/js-clrs-btree/btree.html and they gave me different results

On paper I tried to create the tree inserting those consecutive values 1 by1 and get a totally different result.

If the elements were in random order would the result be the same?

My result is this enter image description here

The problem is when on the right I have 38|40|45 and I add 50 I have to put 40 a level higher but in the internet generators they also put 33 a level down and I don't see why

Solution

  • Can a B tree have more solutions?

    I think you're asking whether there can be more than one one way to store a given set of keys in a b-tree, but you have already answered that yourself. Both of the generated examples you present contain the same keys and are valid 1-3 b-trees. The first is also a valid 1-2 b-tree. With the correction, your attempt is also a valid 1-3 b-tree.

    Note well that there are different flavors of b-tree, based on how many keys the internal nodes are permitted to contain, and also that even binary trees, with which you may be more familiar, afford many different structures for the same set of two or more keys.

    If the elements were in random order would the result be the same?

    Very likely so, yes, but that's not a question of the b-tree form and structure, but rather about the implementation of the software used to construct and maintain it.

    You seem confused that

    in the internet generators they also put 33 a level down and I don't see why

    , but we can only speculate about the implementation of the software supporting those trees. It's unlikely that anyone here can tell you with certainty why they produce the particular b-tree forms they do, but those forms are valid, and so, now, is yours.