maple tree是B树的优化形式,为了更好的理解maple tree,这里先对B树做一个铺垫学习。

B树的性质

B树是平衡搜索树的一种,对于一个m阶B树它的性质有:

  • 平衡:所有的叶子节点都在一层
  • 有序:节点内有序,左子树都小于它,右子树都大于它
  • 多路:最多m-1个元素,根节点最少1个元素,其余节点最少(m/2上取整 - 1)个元素

而这些性质都是在树的操作上保证的。下面就看看B树的插入和删除操作

插入操作

先找到需要插入的node,此时一定是叶子节点。
插入后,如果节点没有上溢出,则结束。如果上溢出,则进行拆分动作,将多处的元素插入父节点。
再判断父节点。

下面用一张图来观察拆分动作。

假设执行插入后,节点有5个元素,已经上溢出。这时候就要执行拆分,以中间元素B为分割点拆分。

                            idx
                      +---+ +---+
                      | A | | C |
                      +---+ +---+
                     |     |     |
                     c0    c1    c2
                           /
                       /
                   /
               /
        +---+ +---+ +---+ +---+ +---+
        | X | | Y | | B | | J | | K |
        +---+ +---+ +---+ +---+ +---+
       |     |     |     |     |     |
       c10   c11   c12   c20   c21   c22

拆分后,B元素上移到父节点,而右半部分作为子树也插入父节点。

                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c'    c2
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+                       +---+ +---+
        | X | | Y |                       | J | | K |
        +---+ +---+                       +---+ +---+
       |     |     |                     |     |     |
       c10   c11   c12                   c20   c21   c22

删除操作

先找到需要删除的元素,如果该元素不在叶子节点,则找到其后继,并替换。总之确保是在叶子节点上做删除操作。
如果删除后,节点没有下溢出,那么删除操作完成。
此时再判断节点的兄弟,如果兄弟节点元素超过一半,那么就借一个过来。如果兄弟元素也不过,则合并。
如果是合并的,那么就往上走一层,看父节点是否下溢出。

借元素

我们先看看从兄弟节点上借元素的情况。

此时左子树的元素下溢出,我们要做的是把父节点上的元素拿来放到最后,然后把右子树的第一个孩子也拿过来。
然后右子树的第一个元素上移到父节点上。

                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+                       +---+ +---+ +---+ +---+
        | X | | Y |                       | J | | K | | L | | M |
        +---+ +---+                       +---+ +---+ +---+ +---+
       |     |     |                     |     |     |     |     |
       c10   c11   c12                   c20   c21   c22   c23   c24

最后的结果是这样。

                            idx
                      +---+ +---+ +---+
                      | A | | J | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+ +---+                 +---+ +---+ +---+
        | X | | Y | | B |                 | K | | L | | M |
        +---+ +---+ +---+                 +---+ +---+ +---+
       |     |     |     |               |     |     |     |
       c10   c11   c12   c20             c21   c22   c23   c24

合并兄弟

合并兄弟的操作实际是拆分操作的反向操作。

此时,左子树已经下溢出,其兄弟也没有足够的元素。
就需要把父节点的元素拉下来放到最后,然后把兄弟也加到后面。

                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+                             +---+ +---+
        | X |                             | J | | K |
        +---+                             +---+ +---+
       |     |                           |     |     |
       c10   c11                         c20   c21   c22

最后的结果就像这样。

                            idx
                      +---+ +---+
                      | A | | C |
                      +---+ +---+
                     |     |     |
                     c0    c1    c3
                           /
                       /
                   /
               /
        +---+ +---+ +---+ +---+
        | X | | B | | J | | K |
        +---+ +---+ +---+ +---+
       |     |     |     |     |
       c10   c11   c20   c21   c22

原文

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部