n 分木 Rope データ構造のランクはキーより左側の部分木を連結した文字列長

前回、「ここまでは二分木なのですが、 B+ 木のような多分木で同様の部分木ランク付けを使おうとするとどうなるのだろうかと考えが進みます。 例えば、 B+ 木にランク付けする用途だけではなく、 文字列データ構造 Rope を n 木で扱う方法の参考になるかもしれません」と書いた後に考えたり調べたりした結果、 Rope ではページ内の二分木構造を反映する必要はないと自分の中で結論をつけました。

H. Boehm, R. Atkinson and M. Plass Ropes: an Alternative to Strings 1995 (PDF) によると、 文字列を二分木で扱う Rope データ構造が 1982 年に登場するより前に、 文字列ではなく 1 次元ベクトルを AVL 木で扱う方法が知られていたとあります。 そのやりかたは D. Knuth The Art of Computer Programming Volume 3 2nd Edition 1998 (以下、 TAOCPと略) の 471 ページに載っています。 そこでは、 要素の並びを AVL 木の行きがけ順で表す方法を解説しています。 TAOCP 図 24 で、 AVL 木にベクトル内での要素位置をキーにランクとして追加してあり、 ランクのつけかたは、 英語版 Wikipedia の Rope の説明に使われている図と同じです。 AVL 木を使ったベクトルと Rope の共通点を探すと、 あるノードに注目すると、 そのノードを根とする部分木の中で、 ノードのベクトル上の位置をランクにしています。 AVL 木の場合は要素位置を 1 から始めているため、 左側をベクトルしたときの長さに 1 を足した値になり、 Rope の場合はゼロから始めるため、 左側を一つの文字列に連結した長さになります。

それを踏まえると、 B+ 木構造を Rope に応用するときは、 ランクを付けたいキーより左側に並ぶ部分木を連結して作成できる文字列の長さにすれば良いと考えられます。 実際、 TAOCP 6.2.4 の練習問題 9 「AVL 木ではなく B 木をベクトルに使う方法を考えよ」の解答 (721ページ) はそれに相当するやりかたになっています。 n 木の Rope は B+ 木のキーをランクにして、 葉のデータを文字列にしたものに相当しますから、 これが正解なのでしょう。 ページ内の二分木の構造を考慮する必要はありません。

例えば、 葉と親ノードを考えて、 先頭の葉に合計長 12 文字があり、 2番めの葉に合計長 9 文字があるとき、 親のランクは 12 と 21 にします。

{{"ab" 2 "cde" 5 "f" 6 "gh" 8 "ijkl"} 12 {"mno" 3 "pgr" 6 "stu"} 21 ...}