← 返回题目列表
UNSW COMP2521 · 简单

2-3-4 节点 · 值往哪个孩子走

2-3-4 节点 · 值往哪个孩子走

2-3-4 树的一个节点里有 k 个升序的键,把数轴切成 k+1 段,每段对应一个孩子(从 0 编号)。给定一个节点的键和若干查询值,对每个查询值输出它该走的孩子下标。

诀窍很简单:下标 = 有几个键比查询值小。例如节点 [20 | 50]:10 比 0 个键小 → 孩子 0;35 比 1 个键(20)小 → 孩子 1;99 比 2 个键小 → 孩子 2。

这正是查找 / 插入下行时每一步要做的定位。保证查询值都不等于已有的键。

输入

  • 第 1 行:键数 k(1~3)。
  • 第 2 行:k 个升序整数(节点里的键)。
  • 第 3 行:查询个数 q。
  • 第 4 行:q 个查询整数。

输出

  • q 行,每行一个孩子下标(0 ~ k)。

示例:输入 2 / 20 50 / 3 / 10 35 99 → 输出 0 / 1 / 2。