python - Python: 動的間隔データ構造

Question

間隔のオーバーラップを効率的に計算するための Python コードを探しています。以前は bx-python パッケージの間隔ツリーを使用していましたが、ツリーから間隔を削除する必要があります (または、より良い方法として、それらを変更します)。bx-python ツリーはこれをサポートしていないようです。

ポインタはありますか？

Answer 1

たぶん、すべての交差間隔を保存すると役立つでしょう。

必要なもの：

• すべての区間の結合の境界、
• 各交差点の左側の境界と交差点が作成される間隔のリスト。

交差間隔は左側の境界でのみ表されるため、ツリーに格納できます。メソッドの挿入と削除の間隔は次のようになります（簡略化）：

挿入：新しい間隔の左右の境界の交差間隔を見つけ、これらの交差間隔を2つまたは3つの新しい交差間隔に分割します。交差する間隔ごとに、新しい間隔へのポインタを追加します。

削除：左右の境界の交差間隔を見つけて、前に交差間隔にマージします。削除された間隔へのポインタを削除する間の交差間隔ごとに。