1
$\begingroup$

I am studying B-trees and reading Introduction to Algorithms by Cormen et al.

Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree.

enter image description here

I understand that for a B-tree of order $m$, the tree has 5 properties:

  1. Every node has at most $m$ children.
  2. Every internal node except the root has at least $\left\lceil \frac{m}{2}\right \rceil$ children.
  3. Every non-leaf node has at least two children.
  4. All leaves appear on the same level and carry no information.
  5. A non-leaf node with $k$ children contains $k−1$ keys.

Based on this however, I wasn't sure if you could just tell the order of a given tree. To me, it seems this looks like it could be order 4,5, or 6. By the $\left\lceil \frac{m}{2}\right \rceil$ criteria, 6 would be the most since 6/2 = 3 and therefore anything larger would automatically mean that this criteria wouldn't be satisfied for the node with keys D,H.

Is the order of a B-tree unique? If so, what is the order of this B-tree?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Good question.

You have given the answer. A B-tree of order $4$ can also be a B-tree of order $5$ or $6$. So, "the order" of a B-tree may not be unique.

Knuth, who gave the definition of B-tree as in the question, avoids the problem of non-uniqueness by defining the order to be the maximum number of children of a node, which is one more than the maximum number of keys. [1]

So, according to Knuth, the order of the B-tree in the question is $4$.

[1] Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison-Wesley, ISBN 0-201-89685-0. Section 6.2.4: Multiway Trees, pp. 481–491.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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