如何在这个2-3树中插入7

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│ │
        └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘