data-structures - 2-3-4 树高不平衡

Question

我观察到 2-3-4 树的高度可能会根据节点的插入顺序而有所不同。

例如 1,2,3,4,5,6,7,8,9,10 将产生高度为 2 的树

按此顺序插入时：

例如 1, 5, 10, 2, 3, 8, 9, 4, 7, 8 将产生高度为 1 的树

这是 2-3-4 树的正常属性吗？在这种情况下，按顺序插入节点将产生一棵非常不平衡的树。我认为2-3-4树应该是平衡树？

谢谢。

Answer 1

我观察到 2-3-4 树的高度可能会根据节点的插入顺序而有所不同。

2-3-4 树的插入算法将“在路上”的 4 个节点拆分为叶节点，因为它们不能获取另一个项目。这允许插入一次完成，并且树保持平衡。

Answer 2

平衡树通常意味着它的高度是 O(logn)。

一个有效的 B 树（包括 2-3-4 树）有以下限制：

1. 所有非根节点至少有 [m/2] 个元素。

2. 所有的叶子都在相同的高度。

有了这两个限制，一个有效的 B-Tree 被证明具有 O(logn) 高度。

Answer 3

2-3-4 树确实是“平衡”树，因为树的高度永远不会超过相对于节点数量的某个固定界限（如果每个节点中恰好有两个值，则为 O(log n ））。这里的术语“平衡”应该与“不平衡”形成对比，“不平衡”是一棵高度相对于节点数量“大”的树。例如，这棵树是高度不平衡的：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

我认为您假设“平衡”一词的意思是“尽可能紧凑”，但事实并非如此。绝对有可能将多个不同的插入顺序放入 2-3-4 树中产生不同高度的树，其中一些树的高度低于其他树。但是，与树中的节点总数相比，可实现的最大可能高度并不算太大，因此 2-3-4 树确实被认为是平衡树。

希望这可以帮助！