data-structures - 插入 2-3 树

Question

我不确定我是否正确理解了 2-3 树的插入过程。假设我有树：

我想将值 95 插入其中，这是正确的新树吗？

Answer 1

是的，这是正确的。

插入 95 会将 3 个孩子放在最右边的叶子中（不允许）

        40 
      /    \
    20     60, 80
   / \     /   | \
 10  30   50  70 90,95,100 <- not valid

叶子中的 3 个节点使 95 移动到父节点，但现在父节点中有 3 个节点：

        40 
      /    \
    20      60,80,95 <- not valid
   /  \     /   |  \
  10  30   50  70 90,100

向上移动 95 会导致父节点分裂：

        40 
      /    \
    20       80
   /  \    /    \
  10  30  60     95
          / \   /  \
        50  70 90  100 valid

Answer 2

我认为你错了。您违反了关于 2-3 树的一个事实：所有叶子都具有相同的深度。参考： http: //pages.cs.wisc.edu/~vernon/cs367/notes/10.23TREE.html#operations

这是我想到的插入痕迹：

如果这不正确，请告诉我。

Answer 3

这是不正确的。2-3 树的高度是一致的，因此您将拆分父级而不是子级。