インターバル ツリーの記事で増補ツリーを見て、SWI-Prolog 標準ライブラリのrbtrees.plを見ています。記事には次のように書かれています。
次に、追加の注釈がすべてのノードに追加され、このノードから下のすべての間隔の中で最大の上限値が記録されます。この属性を維持するには、ノードが追加または削除されるたびに、ノードのすべての祖先をボトムアップで更新する必要があります。
この注釈を追加する方法は簡単にわかります。interval を保存したいとします7-45。キーとして 7 を使用し、値にはすべての情報を含む構造体を使用するので、interval(7-45, MaxBelow). しかし、「ノードのすべての祖先を更新する」方法は明確ではありませんrb_insert/4。前のツリーと後のツリーの間で変更されたすべてのノードのリストを取得する方法がわかりません (とにかく、そのようなリストを生成するのはおそらく奇妙で非効率的です)。
でこの構造を構築するこのアプローチを進める方法はありrbtrees.plますか?
ちなみに、rb_emptyインスタンス化されていない変数を空のノードとして使用するのは興味深いことです。これには理由がありますか？
編集：前後のツリーを調べて、前後のブランチを統合して、変更された場所のパスを見つけることができると思います。それは私が求めているパフォーマンスの向上を台無しにするつもりですか?