data-structurestree2-3-4-tree

2-3-4 tree height imbalanced

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.

Solution

  • 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!