問題
空の2-3-4木（次数4のB木。各ノードは最大3キー・最大4子。根以外は最低1キー）に、$N$個の相異なる整数を与えられた順に挿入する。挿入は「途中で満杯ノードに出会ったら先に分裂させてから降りる」トップダウン方式（先取り分裂）で行う。すべての挿入が終わった後の (1) 木の高さ（根を1階として数える）(2) 発生したノード分裂の総回数 を出力せよ。
入力形式
N
a_1 a_2 ... a_N制約
$1 \le N \le 200000$
$a_i$は相異なる整数
入出力例
入力例1
5
1 2 3 4 5出力例1
2
11,2,3挿入後root=[1,2,3]。4挿入直前にrootが満杯なので先取り分裂(1回)。root=[2], 子=[1],[3]。4,5は右の子に入り[3,4,5]。高さ2、分裂1回。
概念図
ヒント（段階的開示）
ヒント1（方向性）
B木は1ノードに複数キーを持てる。挿入時「これから降りようとするノードが既に満杯（キー数3）なら降りる前に必ず分裂させる」ルールを守れば、一度も後戻りせず根から葉まで一直線に降りるだけで正しく挿入できる。
ヒント2（アプローチ）
満杯ノードを分裂すると中央キーが親に押し上げられ左右2子に分かれる。根自体が満杯なら空の新root作成後に分裂（唯一高さが増えるタイミング）。降下中も次に入る子が満杯なら先に分裂してから入る。
ヒント3（誘導）
def insert(root, key):
if len(root.keys) == 3:
new_root = Node(leaf=False)
new_root.children = [root]
split_child(new_root, 0)
root = new_root
node = root
while not node.leaf:
i = bisect_right(node.keys, key)
if len(node.children[i].keys) == 3:
split_child(node, i)
if key > node.keys[i]:
i += 1
node = node.children[i]
insort(node.keys, key)
return root模範解答 (Python)
import sys
import bisect
class Node:
__slots__ = ('keys', 'children', 'leaf')
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
def split_child(parent, i, counter):
child = parent.children[i]
mid_key = child.keys[1]
left = Node(leaf=child.leaf)
right = Node(leaf=child.leaf)
left.keys = child.keys[:1]
right.keys = child.keys[2:]
if not child.leaf:
left.children = child.children[:2]
right.children = child.children[2:]
parent.keys.insert(i, mid_key)
parent.children[i:i + 1] = [left, right]
counter[0] += 1
def insert(root, key, counter):
if len(root.keys) == 3:
new_root = Node(leaf=False)
new_root.children = [root]
split_child(new_root, 0, counter)
root = new_root
node = root
while not node.leaf:
i = bisect.bisect_right(node.keys, key)
if len(node.children[i].keys) == 3:
split_child(node, i, counter)
if key > node.keys[i]:
i += 1
node = node.children[i]
bisect.insort(node.keys, key)
return root
def height(node):
h = 1
while not node.leaf:
h += 1
node = node.children[0]
return h
def main():
data = sys.stdin.read().split()
n = int(data[0])
arr = list(map(int, data[1:1 + n]))
root = Node(leaf=True)
counter = [0]
for key in arr:
root = insert(root, key, counter)
print(height(root))
print(counter[0])
main()Step-by-Step 解説
1満杯ノードとは何か
2-3-4木では1ノードに最大3キー・4子を持てる。3キー持つノードが「満杯」であり、これに迎え入れる直前に必ず分裂させる。
2-3-4木では1ノードに最大3キー・4子を持てる。3キー持つノードが「満杯」であり、これに迎え入れる直前に必ず分裂させる。
2分裂の中身
[k0,k1,k2]を分裂するとk1が親に上がりleft=[k0], right=[k2]の2子ができる。内部ノードなら4子も2つずつに分ける。
[k0,k1,k2]を分裂するとk1が親に上がりleft=[k0], right=[k2]の2子ができる。内部ノードなら4子も2つずつに分ける。
3根の特別扱い
根が満杯の場合は新しい空の根を作ってから分裂する。木の高さが増える唯一のタイミング。
根が満杯の場合は新しい空の根を作ってから分裂する。木の高さが増える唯一のタイミング。
4降下中の先取りチェック
次に入る子が満杯なら先に分裂。分裂で中央値が親に上がるため、keyがその値より大きければ子のインデックスを+1する。
次に入る子が満杯なら先に分裂。分裂で中央値が親に上がるため、keyがその値より大きければ子のインデックスを+1する。
5計算量
後戻りしない先取り分裂方式なので各挿入はO(log N)、全体O(N log N)。
後戻りしない先取り分裂方式なので各挿入はO(log N)、全体O(N log N)。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 根が満杯かのチェックを忘れる | 降下中ノードだけ見ればいいと誤解 | insertの最初に必ず根自体の満杯判定を行う |
| 分裂後に子のインデックス更新を忘れる | 親のキー数・子数の変化を反映しない | key > node.keys[i]ならi+=1して正しい子に進む |
| 葉ノードでもchildrenを操作しようとする | leafフラグを見ずに子リストを触る | child.leafを見てleafなら分割処理をスキップ |
| 分裂回数を挿入回数と混同する | 1回の挿入で複数回分裂しうることの見落とし | 分裂のたびにカウンタをインクリメントする |
次のステップ
- 発展: 各ノードにサブツリーサイズを持たせればB木上でも順序統計クエリ(k番目に小さい要素)にO(log N)で拡張できる
- 次回予告: Interval Tree（拡張BST区間木・被覆区間の判定）