algorithm - インターバルツリーからノードを削除する方法

Question

ウィキペディアでインターバルツリーについて読んでいます。deleteでメソッドを実装する方法を知っている人はいますJavaか? 削除アルゴリズムへのリンクはhttp://en.wikipedia.org/wiki/Interval_tree#Deletionです

Answer 1

Centered interval tree アプローチ (使用したリンクが指す場所) を使用した削除の疑似コードは次のようになると思います。

deleteInterval(Node n, Interval i)
{
  n.intervalsDesc.remove(i)
  n.intervalsAsc.remove(i)
  if (i.end < n.value && n.leftChild != null) deleteInterval(n.leftChild, i)
  if (i.begin > n.value && n.rightChild != null) deleteInterval(n.rightChild, i)
}