フリーリストからのアロケーション
「アロケーションの基本」では、予約済み区間のリストAと全体区間[s, t]を与えて、(d, x)を残りの部分からアロケートする方法を説明した。ここでは、リストに空き区間が保持されている状況でのアロケートを考える。
包含（inclusion）関係
α=[a, b;x]、β=[c, d;y]として、次が成立すれば α⊆β。
- c≦a
- b≦d
- x≦y
これが（重み付き）区間の包含関係。四角形のイメージで考えれば自明だろう。
α=[a, b;x]のとき、a＜a1＜b であるa1を取って、[a, a1;x], [a1, b;x]の2つの区間に分けることを分割という。より一般に、a=a0, a1, ..., an=b を使った分割が考えられる。分割は縮約のちょうど逆の操作になる。
準備ができたので、αは重み付き区間、Bが[β1, ..., βn]というリストのとき、α⊆A の定義を考える。リストBは正規化されているとする。適当なi（1≦i≦n）があって、α⊆βiなら当然に α⊆B だが、それより少し一般化した定義を与える。
- αの適当な分割α1, α2, ..., αkがあって、どのαiも、Bの要素である区間に含まれるなら α⊆B 。
これも、図形イメージで考えると割と当たり前。
包含の判定
与えられた区間αと（正規な）リストBに対して、α⊆B を判断するのはめんどくさい。正直に定義に従うと、αの分割が必要になる（ことがある）。αの分割を避けるため、Bのほうに細工をしておく方法がある。
β=[c, d;y]とβ'=[c', d':y']が接合（あるいは隣接）しているとは、d = c' なこと。正規なリストが与えられと、簡単なアルゴリズムで隣接している区間をグループにまとめられる。例えば、[α, β, γ, δ]で、αとβ、βとγが隣接していて、他に隣接する対がないとき、[[α, β, γ], δ] という入れ子のリストを作れる。
上記[α, β, γ]のように、隣接している成分からなるリストは、図形的には連結成分を表す。今までの表現では、2次元領域を“縦に割って”表現してきたが、連結成分なら横割りにもできる。「縦割り表現→横割り表現」の操作を各連結成分に施す。この変換操作はコストがかかるが、包含の判定のときには便利になる。詳細は割愛、図を描いて考えればわかるはず。
フリーリストとアロケーション
重み付き区間[a, b;x]を、「xだけ使用されていて、1-xの空きがある状況」だと解釈する。特に[a, b;0]は区間[a, b]が完全に（100%）空いていることを示す。重み付き区間α1, ..., αnからなるリストA=[α1, ..., αn]を空きを記述するフリーリストだとする。
(d, x)が与えられたとき、(d, x)の実現である区間αがあり、α⊆Aのとき、(d, x)はフリーリストAからアロケート可能という。
予約（使用）リストとフリーリストとの関係
予約または使用されている区間のリストA=[α1, ..., αn]と、全体区間[s, t]が与えられると、それから簡単にフリーリストを構成できる。
リスト[α1, ..., αn]の要素を順に見ていく。隣り合う２つの区間[a, b;x], [c, d:y]がb＜cのとき、ギャップがあるという。ギャップがあるとは、接合（隣接）してないことである。ギャップがあるとき、ギャップ区間に重さ0を与えた区間を挿入することによりギャップを埋めることができる。すべてのギャップを埋めたリストを作る。
リスト[α1, ..., αn]は、既にギャップが埋められ、全体区間[s, t]を覆い尽くしているとする（重さが0の部分があってもよい）。各区間の重みxを1-xに置き換えるとフリーリストができる。このフリーリストをもとにアロケーションをしてもよい。
