如何将 7 插入到这棵 2-3 树中

Question

我正在尝试将元素 7 插入到这棵 2-3 树中（见图）：

既然包含6和9的节点已经满了，我应该把7移到6和9的父节点上，但是那个节点也已经满了，那怎么办？

Answer 1

你是正确的，叶子 (6, 9) 已满，必须在插入 7 时拆分。这意味着中间值（当时为 7）必须插入父节点（本例中为根节点） ).正如您正确注意到的那样，该节点 (2, 5) 也已满。所以……它也必须分裂。考虑 7 时，中间值为 5，必须“向上”移动。由于没有“up”，所以会形成一个新的根节点：

如果我们可视化中间的违规状态，我们会在插入过程中得到：

              ┌───┬───┐
              │ 2 │ 5 │
              └───┴───┘
             /    |    \
         ┌─┬─┐  ┌─┬─┐  ┌─┬─┬─┐
         │1│ │  │3│4│  │6│7│9│ (overflow)
         └─┴─┘  └─┴─┘  └─┴─┴─┘

然后7向上移动：

              ┌───┬───┬───┐
              │ 2 │ 5 │ 7 │ (overflow)
              └───┴───┴───┘
             /    |   |    \
         ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
         │1│ │ │3│4│ │6│ │ │9│ │ 
         └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘

然后5上移：

                   ┌─┬─┐
                   │5│ │
                   └─┴─┘ 
                  /   \
             ┌─┬─┐     ┌─┬─┐
             │2│ │     │7│ │
             └─┴─┘     └─┴─┘
            /   \     /   \
        ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
        │1│ │ │3│4│ │6│ │ │9│ │
        └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘

如何将 7 插入到这棵 2-3 树中

How to insert 7 into this 2-3 tree

algorithm

binary-tree

binary-search-tree