CODEWITHSUNDEEP
data-structuresb-tree
monkey
monkey

Reputation: 591

Number of nodes in a B-Tree

How many nodes does a resulting B-Tree(min degree 2) have if I insert numbers from 1 to n in order?

I tried inserting nodes from 1 to 20 there was a series for the number of nodes coming but i could not generalize it.

Can anyone please help me derive the formula for this.

Upvotes: 0

Views: 3369

Answers (1)

Diptendu
Diptendu

Reputation: 2158

It will depend on the order of the B-Tree. The order of a BTree is the maximum number of children nodes a non-leaf node may hold (which is one more than the minimum number of keys such a node could hold).

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

  1. Every node has at most m children.
  2. Every non-leaf node (except root) has at least ⌈m⁄2⌉ children.
  3. The root has at least two children if it is not a leaf node.
  4. A non-leaf node with k children contains k−1 keys.
  5. All leaves appear in the same level, and internal vertices carry no information.

So in your case when you are inserting 20 keys if the order is m then based on the conditions mentioned above you can derive a set of inequalities that describes the possible value of m. But there is no equality formula that says the number of internal nodes in a B-Tree.

Upvotes: 2

Related Questions