前回の記事では方法 1 について記述しました。 今回はそれを発展させた方法 2 について記述します。 方針 方法 2 では、方法 1 の状態からさらに、子ノードが 1 個のノードを省略します。 下図は、クエリ (1) によりインデックス の値が更新されたときの例で…

概要 通常のセグメント木では、管理対象の列の項数 を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 を要し、1 回のクエリあたり時間計算量 を要する。 したがって、 として利用できる値には計算機資源上の制限があり、列のインデ…

重み平衡二分木 (weight-balanced binary trees) を C# で実装したライブラリ WBTrees (GitHub) の初版 v1.0 をリリースしました。 主な機能は次の通りです： (1) インデックスによる操作 (取得・更新・挿入・削除) をすべて 時間でできる List WBList<T> クラ</t>…