区間木
数直線上に n 個の区間があるとき、これらを表すデータ構造を構築し、別の点や区間とオーバーラップする全ての区間を効率的に検索したいとする。
まず、全ての区間が含まれる範囲を特定し、その中央の x_center で分割する(x_center で分割するのは、木構造をなるべく平衡にするため)。これによって、区間は3種類に分類される。x_center の左側にある区間群を S_left、x_center の右側にある区間群を S_right、x_center にオーバーラップする区間群を S_center とする。
S_left と S_right に属する区間群は同様の方式で再帰的に分割していき、左右に区間が全く残らない状態にする。
S_center に属する区間群(中央点にオーバーラップしている区間群)は、区間木内のノードにリンクされた別のデータ構造に格納される。このデータ構造は2つのリストから構成されていて、1つは区間群を始点でソートしたリスト、もう1つは区間群を終点でソートしたリストである。
結果として構築される2分木のノードには、以下のようなデータが格納される。
中央点の位置
区間全体が中央点の左側にある区間群に対応したノードへのポインタ
区間全体が中央点の右側にある区間群に対応したノードへのポインタ
中心点とオーバーラップする全区間を始点でソートしたリスト
中心点とオーバーラップする全区間を終点でソートしたリスト