Fries_I23

🎮Gaming, 🎬Movies, 💻Coding, and so on✨✨✨

分类:

这篇博客会在 “算法学习 - 多叉树树 (Multi-Way Tree) 与 2-3 树 (2-3 Tree)” 的基础上继续探讨另一种多叉树结构: 2-3-4树, 并尝试将操作总结并运用于 n 路平衡树 中.

2-3-4 树

2-3-4 树 就是在 2-3 树 的基础上, 增加了 4-Node 节点, 其完整性质如下:

  1. 2-Node, 即一个节点只包含一个 Key, 同时只能为叶子节点或者同时存在左右孩子. 左子树上的任一节点 l 都需要满足: x > l, 右子树上的任一节点 y 都需要满足: x <= z;
  2. 3-Node, 即一个节点包含两个 Key, 同时只能为叶子节点或者同时存在三个孩子. 节点与子树之间需要满足: l < x <= c < y <= r | l∈{左子树}, c∈{中间子树}, r∈{右子树}
  3. 4-Node, 即一个节点包含三个 Key, 同时只能为叶子节点或者同时存在四个孩子. 节点与子树之间需要满足: l < x <= c1 < y <= c2 < z <= r | l∈{第一子树}, c1∈{第二子树}, c2∈{第三子树}, r∈{第四子树}
  4. 所有节点都是 2-Node, 3-Node 或是 4-Node
  5. 所有叶子节点都在同一个 layer, 也就是说任意 layer 的子树高度都是相同.
// 2-Node
    |
    x             |
  /  \    或      x
 l    r

// 3-Node
      |
    x   y                  |
  /   |   \      或      x   y
 l    c    r

// 4-Node
        |
    x   y   z                 |
  /   |   |   \      或    x  y  z
 l   c1   c2    r

2-3-4 树相关操作

2-3-4 树 的各种操作都与 2-3 树 高度类似, 比如:

  • 插入操作都在插入叶子节点后考察节点是否溢出, 溢出后则分裂节点 (对于 5-Node 而言, 中间两个 key 中任一作为父节点分裂都可) 并与上一级合并, 然后沿着树递归执行到树所有性质都满足或者形成新的 root (此时树的高度 +1) 即可.
  • 删除操作也类似, 为:
    1. 将删除路径上的节点转变为删除一个叶子节点中的值.
    2. 对于删除后为 Null 节点的情况, 考察兄弟节点, 如果兄弟节点有多余的节点 (不是 2-Node) 就进行 Adopt, 否则进行 Merge, 直到消除 Null 节点或形成了新的 root 为止 (此时树的高度 -1).

我们可以从上面总结出多路平衡树 (Multiway Balanced Tree) 的性质与操作.

多路查找树 (Multiway Search Tree) 的性质

一个 M-Way 查找树, 应该满足如下性质:

  1. (2-n)-Node, 即一个节点包含 1 到 n-1 个 Key, 同时只能为叶子节点或者同时存在 k | 2<=k<=n,k∈Z 个孩子, 且:
    1. 最多存在 n-1 个 Key, 有{k1, K2, ... kn-1};
    2. 存在 0 或 n 个子树, 设 cx 为夹在 kx-1 与 kx 子树中的任一节点, 则有 {c1, c2, ... cn};
    3. 节点与子树之间需要满足: k1 < c1 <= k2 < c2 <= ... < cn-1 <= kn-1 < cn.
  2. 所有节点都是 (2-n)-Node 中的任意一种.
  3. 所有叶子节点都在同一个 layer, 也就是说任意 layer 的子树高度都是相同.

多路查找树 (Multiway Search Tree) 相关操作

root 开始, 查找 k:

  • 在当前 Node 内与其中的值进行比较:
    • 如果有 Node(ki) == k, 则查找结束 (FOUND);
    • 否则选择合适的一个子树递归上面的步骤;
  • 如果叶子节点也不存在相等的 k, 则查找结束 (未找到);

最小值 (Minimum) 与 最大值 (Maximum)

对于最小值, 从 root 开始: 一直沿着最左子树向下, 直到叶子节点, 返回;

对于最大值, 从 root 开始: 一直沿着最右子树向下, 直到叶子节点, 返回;

后继节点 (Successor)

对于一个节点值 (k) 的后继节点 ks:

  • 如果 k 存在一个相对自己右侧的子树, 则找到子树的最小值即可;
  • 如果 k 所在节点为叶子节点, 则:
    • 如果 k 右侧还有其他值, 则该值即为后继结点;
    • 否则向上考察 k 的父节点 Node(kp):
      • 如果 k 所在节点对于 k 的父节点而言不是最右侧节点, 则返回该节点子树右侧的值即可.
      • 否则继续向上递归;
      • 如果已经没有父节点, 说明已经到了 root 节点, 此时:
        • 如果开始最右侧子树或者 root 本身就一个节点, 则没有后继节点;
        • 否则直接查找 root 右子树的最小值即可.

前驱节点的查找步骤与后继节点类似, 这里就不过多说明.

插入 (Insert)

对于在一颗 n 路查找树 中插入一个值 k:

  1. 从 root 开始查找最适合插入 k 的 叶子节点, 并将 k 插入, 此时获得一个 2-(n+1) Node;
  2. 针对 n+1 Node 需要自下而上进行性质修复.
    • 将该 Node 分裂为 floor((n+1)/2) 与 ceil((n+1)/2) 两个符合性质的 Node, 并与分裂前 Node 的父节点 N(kp) 进行合并;
    • 合并后如果 N(kp) 符合性质, 则完成插入.
    • 否则继续分类该节点, 并递归直到符合性质或者 root 节点被分裂.
    • 如果 root 节点分裂, 则树的高度 +1, 并形成了新的 root 节点.
// Split
   ...                  ...  y
  /   \                /   |   \
pl    xyz      -->    p1   x    z

删除 (Delete)

对于在一颗 n 路查找树 中删除一个值 k:

  1. 先找到 k 所在的节点:
    • 如果 k 所在节点为叶子节点, 则直接删除;
    • 否则找到 以 k 为 root 中序遍历的后继结点 x (x 一定是叶子结点), 将 x 替换 k, 并删除原先的 x;
  2. 考察删除后的节点 N(a):
    • 如果 N(a) 还满足性质 (存在多余的值), 则删除成功.
    • 否则 N(a) 此时为一个 Null 节点 (1-Node), 此时需要自底而上修复性质, 考察该节点的兄弟节点 N(b):
      • N(b) 为 3-(n+1) 数量的节点, 此时使用 Adopt 从兄弟节点 “拿” 一个节点过来即可.
      • 否则将两个节点进行 Merge, 形成一个新的 1-Node 并与父节点进行合并. (类似于插入分裂的反操作), 执行完成后考察父节点:
        • 父节点已经满足性质, 则删除完成.
        • 父节点变为 1-Node 则递归重复上述合并过程, 直到满足性质或者 root 节点被合并.
      • 如果 root 节点被合并, 则树的高度 -1, 并形成了新的 root 节点.
// Split
   ...                  ...  y
  /   \                /   |   \
pl    xyz      -->    p1   x    z

// Adopt
  ... p ...                ... b1 ...
    /   \           ->       /   \
 null   b1, b2              p     b2
 |     /   |   \          /  \    /  \
 m   bl   bc    br       m   bl  bc   br

// Merge
  ... p ...              ... null ...
    /   \                     |
  null   b       -->        p   b
   |    /  \              /   |   \
   m   bl   br           m    bl   br