CODEWITHSUNDEEP
b-tree
neuromancer
neuromancer

Reputation: 55479

What will this B-tree look like?

The B-tree is of order 4, meaning that a node can hold 4 pointers, and 3 keys.

The following is inserted: A G I Y

Since they can't all fit in one node, I know that the node will split. So I know there's going to be a root node with 2 child nodes after these things are inserted, but I don't know exactly what they'll look like.

Upvotes: 3

Views: 386

Answers (2)

Janus Troelsen
Janus Troelsen

Reputation: 21270

Here's an animation of the operations:

http://ysangkok.github.io/js-clrs-btree/btree.html#{"actions":[["initTree",{"keys":[]},2],["insert","A"],["insert","G"],["insert","I"],["insert","Y"]]}

The second parameter to "initTree" is the order, but using another defintion. The maximum number of keys in this program is 2*order-1. So I set the order to 2 and it matches your example.

Upvotes: 1

Corey
Corey

Reputation: 3205

A

A is inserted

AG

G is inserted

AGI

I is inserted

  G
 / \
A   I

While inserting Y the node is full, split into 2 nodes and pass up the middle, G

  G
 / \
A   IY

Y is inserted

Upvotes: 3

Related Questions