Difference between B Trees and 2-3-4 Trees

Question

Hi, Could someone please explain to me the difference between B Trees and 2-3-4 Trees? And also how would you find the maximum and minimum height of each? Thanks

Answer 1

I can't do any better than just add a link to wikipedia: http://en.wikipedia.org/wiki/2-3-4_tree

Answer 2

...a link to Wikipedia and a quote:

"2-3-4 trees are B-trees of order 4."

A 2-3-4 is a B-tree.
It is called 2-3-4 tree because the number of children for a non-leaf, non-root node is 2,3 or 4.
Had it been 6, it could have been called a 3-4-5-6 tree, or 3-6 tree for short.
Since the minimum number of children is half of the maximum, one can just usually skip the former and talk about a B-tree of order m.
The order of a B-tree is defined as the maximum number of children a node can have.
In a 2-3-4 tree, as we have seen, the maximum is 4.

It's worst and best-case height is given by the general formula for B-trees.
Best case: log_mn. (all nodes are full)
Worst case: log_m/2n. (all nodes are half-empty)
Where

• m is the order of the tree - the maximum number of children a node can have, in this case, 4 - and
• n is the number of entries in the tree

"B tree can have an order of any number " - yes, but for a particular subclass of B-trees, you fix that number in advance. It's like talking about butterflies in general vs talking about the Monarch butterfly. B-trees are a class of data structures, just like butterflies are a class of insects. Monarch butterflies are a subclass of butterflies, just like 2-3-4 trees are a subclass of B-trees.

Answer 3

Randomly descend the tree until you reach a leaf. All leaves are the same depth, so this depth is both the maximum and minimum depth of the leaves.