2-3-4 tree height imbalanced

Question

I observed that the height of a 2-3-4 tree can be different depending of the order of insertion of nodes.

e.g. 1,2,3,4,5,6,7,8,9,10 will yield a tree of height 2

While inserting in this order:

e.g. 1, 5, 10, 2, 3, 8, 9, 4, 7, 8 will yield a tree of height 1

Is this a normal property of a 2-3-4 tree? Inserting nodes in sequence will yield a very imbalanced tree in that case. I thought 2-3-4 trees should be balanced trees?

Thanks.

Answer 1

2-3-4 trees are indeed "balanced" trees in the sense that the height of the tree never exceeds some fixed bound relative to the number of nodes (which, if each node has exactly two values in it, is O(log n)). The term "balanced" here should be contrasted with "imbalanced," which would be a tree in which the height is "large" relative to the number of nodes. For example, this tree is highly imbalanced:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

I think that you are assuming that the term "balanced" means "as compact as possible," which is not the case. It is absolutely possible to have multiple different insertion orders into a 2-3-4 tree produce trees of different height, some of which will have lower heights than others. However, the maximum possible height achievable is not too great compared to the total number of nodes in the tree, and therefore 2-3-4 trees are indeed considered balanced trees.

Hope this helps!

Answer 2

a balanced tree usually means it's height is O(logn).

a vaild B-Trees (including 2-3-4 Tree) have the following limits:

1. all non-root node have at least [m/2] elements.

2. all leaves are in the same height.

with this two limits, a valid B-Tree is proved to have O(logn) height.

Answer 3

I observed that the height of a 2-3-4 tree can be different depending of the order of insertion of nodes.

The insertion algorithm for 2-3-4 trees splits 4-nodes "on the way" to the leaf node, since they cannot take another item. This allows insertion to be done in one pass and the tree remains balanced.