What is the difference btw "Order" and "Degree" in terms of Tree data structure

Question

B-Tree Definition they use the 'order' term in :

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.
...

and 'Degree' is defined in Tree terms as:

Degree – number of sub trees of a node.

so, are they same thing? I cannot feel any difference.

Answer 1

Degree represents the lower bound on the number of children a node in the B Tree can have (except for the root). i.e the minimum number of children possible. Whereas the Order represents the upper bound on the number of children. ie. the maximum number possible.

B Tree properties with respect to the Order

NOTE: Wikipedia also states these

B Tree Properties with respect to the Degree

B Tree Properties with respect to Degree

NOTE: These can also be found in the CLRS book

Answer 2

A B-tree is a specific type of tree which, among other things, has a maximum number of children per node. The order of a B-tree is that maximum. A Binary Search Tree, for example, has an order of 2.

The degree of a node is the number of children it has. So every node of a B-tree has a degree greater than or equal to zero and less than or equal to the order of the B-tree.

A tree doesn't have a "degree," except in that its nodes have degrees. So a tree has a maximum degree and a minimum degree, referring to the maximum and minimum degrees of its nodes.

Similar question here.

I hope that helps!

Answer 3

There are two popular definitions of a B-tree where:

• Knuth Order (Order) is used by Knuth's definition
• CLRS Degree (Degree) is used in the definition in Cormen et al in Introduction to Algorithms (CLRS)

Both the Knuth order and the CLRS degree measure: min <= children <= max, the minimum and maximum children, (min, max), each internal node in the tree is allowed to have. Both definitions agree that the min can't be less than max/2:

Knuth Order, k |  (min,max)  | CLRS Degree, t
---------------|-------------|---------------
     0         |      -      |        –
     1         |      –      |        –
     2         |      –      |        –
     3         |    (2,3)    |        –
     4         |    (2,4)    |      t = 2
     5         |    (3,5)    |        –
     6         |    (3,6)    |      t = 3
     7         |    (4,7)    |        –
     8         |    (4,8)    |      t = 4
     9         |    (5,9)    |        –
     10        |    (5,10)   |      t = 5

Key similarities / differences:

• The Knuth order k is an index counting the maximum number of children. A Knuth order of k means every node must have a max = k, and a min = ceil(k/2). For example, (3,6) is a B-tree of Knuth order 6.
• The CLRS degree t is an index counting the minimum number of children. A CLRS degree of t means every node must have a min = t and a max = 2t. For example, (3,6) is a B-tree of CLRS degree 3
• In both definitions, it is the case the min = ceil(max / 2) and max = 2 * min.

• In both definitions, it is the case that the number of keys is equal to the number of children minus one. So both the Knuth order and the CLRS degree are technically also counting minimum and maximum keys – as well as simultaneously counting the minimum and maximum children.

• Knuth's definition allows trees (min,max), where max an is odd integer, but CLRS's definition ignores them. Any tree of the form (t, 2t-1) is invalid by CLRS's definition. For example a tree with (min,max) = (5,9) is a valid via Knuth's definition but invalid via CLRS's definition.

---

Interesting asides:

• Both definitions include 2-3-4 trees, which are trees with (min, max) = (2,4). It is a B-tree with Knuth order k = 4 and it's a CLRS B-tree with degree t = 2. These trees are closely related to Red-Black Trees.
• Only Knuth's definition includes 2-3 trees, where (min, max) = (2,3). A 2-3 tree is a Knuth B-tree with Knuth order k = 3. It is not a valid CLRS B-tree. It's a shame that CLRS don't include this tree because they are closely related to AA trees.