[[std::setを使わない代替テクニック]]
現在位置: トップページ » アルゴリズム » データ構造 » 平衡二分探索木 » std::setを使わない代替テクニック
文書の表示
管理サイトマップ

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
programming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2020/06/29] – [配列・特殊アイデア系①] ikatakosprogramming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2024/03/19] (現在) – [std::setを使わない代替テクニック] ikatakos
行 5: 行 5:
 std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる（[[https://cpprefjp.github.io/reference/set/set.html|set - cpprefjp C++日本語リファレンス]] より一部抜粋） std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる（[[https://cpprefjp.github.io/reference/set/set.html|set - cpprefjp C++日本語リファレンス]] より一部抜粋）
  
-^機能  ^概略            ^計算量     ^ +^ 機能                        ^ 概略                                                              ^ 計算量        ^ 
-|insert|集合に要素を追加|$O(\log{N})$| +| insert                      | 集合に要素を追加                                                  | $O(\log{N})$  | 
-|erase |集合から要素を削除|$O(\log{N})$| +| erase                       | 集合から要素を削除                                                | $O(\log{N})$  | 
-|upper_bound \\ lower_bound|ある値より大きい最小の要素の探索|$O(\log{N})$|+| find                        | 値の検索                                                          | $O(\log{N})$  | 
 +| upper_bound \\ lower_bound  | ある値より大きい最小の要素の検索 \\ ある値以上の最小の要素の検索  | $O(\log{N})$  |
  
 Pythonでは標準ライブラリにないし、実装してもリストアクセスの遅さからTLEに直面することがままある。 Pythonでは標準ライブラリにないし、実装してもリストアクセスの遅さからTLEに直面することがままある。
行 16: 行 17:
  
 std::setを使いたいけど使えない……という場合に、代わりになりうる方法をメモ。 std::setを使いたいけど使えない……という場合に、代わりになりうる方法をメモ。
 +
 +<note>
 +2023/08 の言語アップデートにより、AtCoderでは、sortedcontainers ライブラリが入るようになった。
 +これが上記の機能を持っており、十分高速に動作するため、ライブラリにない問題は解消されたといっていい。
 +
 +  * [[https://pypi.org/project/sortedcontainers/|sortedcontainers · PyPI]]
 +
 +ただし、他のコンテストサイトでは基本的に入っていないので、依然として以下の方法が必要になる場合もある。
 +</note>
  
 ===== 代替方法一覧 ===== ===== 代替方法一覧 =====
行 22: 行 32:
  
   * Binary Indexed Tree   * Binary Indexed Tree
-    * 最も汎用性のある代替方法+    * 汎用性の高い代替方法
   * 優先度付きキュー (heapq)   * 優先度付きキュー (heapq)
     * 一定の制約の上で簡単&高速     * 一定の制約の上で簡単&高速
行 28: 行 38:
     * 列挙していけば何か共通点みたいなのが見つかるかも知れない     * 列挙していけば何か共通点みたいなのが見つかるかも知れない
   * %%C++%%コードを埋め込んで外部モジュールとしてコンパイル   * %%C++%%コードを埋め込んで外部モジュールとしてコンパイル
-    * 下記、参考の3つめのリンク参照+    * [[https://nagiss.hateblo.jp/entry/2020/06/28/012528|[Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜]] 
 +    * [[https://github.com/Lgeu/snippet/blob/master/cpp_extension/wrap_cpp_set.py|snippet/wrap_cpp_set.py at master · Lgeu/snippet · GitHub]] 
 +  * 要素アクセスを減らしてPythonでも高速に動く平衡二分木（ピボット木）を使う 
 +    * [[https://qiita.com/Kiri8128/items/6256f8559f0026485d90|平衡二分木を実装する - Qiita]] 
 +  * 平方分割で管理する 
 +    * [[https://github.com/tatyam-prime/SortedSet|GitHub - tatyam-prime/SortedSet]]
  
   * 参考   * 参考
-    * [[https://qiita.com/drken/items/1b7e6e459c24a83bb7fd#2-%E3%81%A4%E3%81%AE-priority_queue|k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita]]+    * [[https://qiita.com/drken/items/1b7e6e459c24a83bb7fd|k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita]]
     * [[https://qiita.com/Salmonize/items/638da118cd621d2628d1|【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita]]     * [[https://qiita.com/Salmonize/items/638da118cd621d2628d1|【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita]]
-    * [[https://nagiss.hateblo.jp/entry/2020/06/28/012528|[Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜]] 
  
  
 ==== Binary Indexed Tree ==== ==== Binary Indexed Tree ====
  
-最も汎用性の高い置き換え。std::setは言うて単純な機能しか持ってないが、こちらなら追加の機能実装も可能。+汎用性の高い置き換え。
  
-  * 集合に、値を追加したり削除したりする 
-  * 任意のタイミングで、小さい方から $k$ 番目の値を答えよ。$k$ は可変である。 
   * 制約   * 制約
-    * 値の取り得る範囲は $1～10^6$（配列を作れる）程度+    * 値は整数限定で、取り得る範囲は $1～10^6$（配列を作れる）程度 
 + 
 +  * できること 
 +    * 値の追加・削除 $O(\log{N})$ 
 +    * $k$ 番目の値を求める $O(\log{N})$ 
 +    * $x$ が存在するか検索 $O(\log{N})$ 
 +    * $x$ より小さい・大きい直近の値を検索 $O(\log{N})$
  
 Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。
 詳細は[[programming_algorithm:data_structure:binary_indexed_tree]]参照。 詳細は[[programming_algorithm:data_structure:binary_indexed_tree]]参照。
 +
 +以下のように置きかえる。
  
   * 値 $x$ を追加 → $bit.add(x, 1)$   * 値 $x$ を追加 → $bit.add(x, 1)$
   * 値 $x$ を削除 → $bit.add(x, -1)$   * 値 $x$ を削除 → $bit.add(x, -1)$
-  * $k$ 番目の値を取得 → 累積和が $k$ 以上になる最小のindexを取得+  * $k$ 番目の値を取得 → $bit.lower\_bound(k)$（累積和が $k$ 以上になる最小のindexを取得） 
 +  * $x$ の検索 → $bit.sum(x)-bit.sum(x-1) \gt 0$ 
 +  * $x$ 以下の最大の値を取得 $bit.lower\_bound(bit.sum(x))$ 
 +  * $x$ 以上の最小の値を取得 $bit.lower\_bound(bit.sum(x - 1) + 1)$ 
 + 
 +$x$ 以下の最大の値が存在しない場合、$1$ が返る。\\ 
 +$x$ 以上の最小の値が存在しない場合、$N+1$ が返る。\\ 
 +（※BITを1-indexedで実装していた場合。lower_boundの実装内容にも依るが） 
 + 
 +そのような操作が発生しうる場合、indexをずらして、$i=1$ は空白要素として $i=2$ から本来の値を入れる、などで本当の値と区別できる。 
 + 
 +=== 例 === 
 + 
 +            累積和               std::set 
 +  初期状態   1 2 3 4 5 6 7 8 
 +            [0 0 0 0 0 0 0 0]    {} 
 +   
 +  5を追加 
 +            [0 0 0 0 1 1 1 1]    {5} 
 +  3を追加 
 +            [0 0 1 1 2 2 2 2]    {3, 5} 
 +   
 +  小さい方から2番目を取得 
 +            [0 0 1 1 2 2 2 2]    {3, 5} 
 +                     ^                            累積和で"2"が始まるiは「5」 
 +   
 +  2,3,7を追加 
 +            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7} 
 +   
 +  4以下の最大の値を取得 
 +            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7} 
 +                   ~                              累積和で 4 の箇所は"3" 
 +                 ^                                累積和で "3" が始まるiは「3」 
 +   
 +  6以上の最小の値を取得 
 +            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7} 
 +                     ~                            累積和で 6-1=5 の箇所は"4" 
 +                         ^                        累積和で 4+1=5 が始まるiは「7」 
 +   
 +  7を削除 
 +            [0 1 3 3 4 4 4 4]    {2, 3, 3, 5} 
 +   
 +  6以上の最小の値を取得 
 +            [0 1 3 3 4 4 4 4]    {2, 3, 3, 5} 
 +                             ^                    存在しない場合、N+1 が返る点には注意
  
-^機能  ^計算量      ^ 
-|insert|$O(\log{N})$| 
-|erase |$O(\log{N})$| 
-|upper_bound \\ lower_bound|$O(\log{N})$| 
  
 === バリエーション === === バリエーション ===
行 80: 行 140:
 ==== 優先度付きキュー ==== ==== 優先度付きキュー ====
  
-  * 値が追加されたり削除されたりする 
-  * 任意のタイミングで、小さい方から $k$ 番目の値を答えよ 
   * 制約   * 制約
-    * $k$ は固定である+    * $k$ 番目の値を取得する、というクエリの $k$ は固定 
 +    * 検索はできない
  
-上記のような制約があれば、2つの優先度付きキューを用いることで代替できる。+  * できること 
 +    * 値の追加 $O(\log{N})$ （削除は一工夫必要、バリエーション参照） 
 +    * $k$ 番目の値を取得 $O(1)$
  
-Binary Indexed Treeでは実現できない、$10^9$ など配列を作るのが厳しい範囲のクエリにも対応できる。+2つの優先度付きキューを用いることで代替できる。 
 + 
 +Binary Indexed Treeでは実現できない、$10^9$ など配列を作るのが厳しい範囲のクエリや、整数値以外にも対応できる。
  
   * lower: 常に値の個数を $k$ 個に保つ優先度付きキュー。大きい方から取り出す   * lower: 常に値の個数を $k$ 個に保つ優先度付きキュー。大きい方から取り出す
行 97: 行 160:
   * $x \gt y$ なら、$x$ をlowerよりpopし、代わりに $y$ をpush。$x$ はupperにpush   * $x \gt y$ なら、$x$ をlowerよりpopし、代わりに $y$ をpush。$x$ はupperにpush
  
-^機能  ^計算量      ^ 
-|insert|$O(\log{N})$| 
-|erase |$O(\log{N})$？ 下記バリエーション参照| 
-|get_k_th|$O(1)$| 
  
 === バリエーション === === バリエーション ===
行 233: 行 292:
  
  
 +
 +==== 配列・特殊アイデア系② ====
 +
 +  * はじめ $1～N$ の整数が1つずつ入った集合がある
 +  * 以下の2つのクエリを処理する
 +    * 1. 整数 $i$ を集合から取り除く
 +    * 2. 現在、$i$ 以上で集合に入っている最小の整数を求める
 +
 +①と似ているが、クエリ2で同じ $i$ について何回も聞かれる点が異なる。\\
 +（①は既に処理が終わった $i$ は更新しないので、その後に書かれている値は正しくないものになっていく）
 +
 +=== std::set解 ===
 +
 +最初、setに $1～N$ の値を全て入れておく。
 +
 +クエリ1に対しては、setから $i$ をdeleteする。\\
 +クエリ2に対しては、lower_boundが使える。
 +
 +または、setに入れる値を値が残っている区間 $[L,R)$ にして、取り除く操作を区間の分割で表現することもできる。
 +
 +=== 代替手法 ===
 +
 +取り除くのみで、加えることはしない場合に限られる。
 +
 +  「整数が存在するか」と
 +  「存在しなかった場合に確認する次の整数」を管理する長さNの配列を用意
 +  
 +  i   1  2  3  4  5  6  7  8  9
 +    [ 1  1  1  1  1  1  1  1  1 ]    0:存在しない  1:する
 +    [ 2  3  4  5  6  7  8  9  x ]    次の整数
 +  
 +  クエリ2: i=7 に対する答え
 +    [ 1  1  1  1  1  1 [1] 1  1 ]    7が存在するのでそのまま7が答え
 +    [ 2  3  4  5  6  7  8  9  x ]    
 +  
 +  クエリ1: i=4,5 を取り除く
 +    [ 1  1  1 [0  0] 1  1  1  1 ]    ←該当位置を0にする
 +    [ 2  3  4  5  6  7  8  9  x ]    ←クエリ1では特に何もせずそのまま
 +  
 +  クエリ2: i=4 に対する答え
 +    [ 1  1  1 [0] 0  1  1  1  1 ]    i=4がないので
 +    [ 2  3  4 [5] 6  7  8  9  x ]    次に確認すべき5を見に行く
 +  
 +    [ 1  1  1  0 [0] 1  1  1  1 ]    i=5もないので
 +    [ 2  3  4  5 [6] 7  8  9  x ]    次の6を見に行く
 +    
 +    [ 1  1  1  0  0 [1] 1  1  1 ]    i=6はあったので、6が答え
 +    [ 2  3  4  5  6  7  8  9  x ]    
 +  
 +    後処理
 +    [ 1  1  1  0  0  1  1  1  1 ]    辿ってきたiについて、
 +    [ 2  3  4 [6  6] 7  8  9  x ]    存在が確認できた整数に更新しておく
 +  
 +  クエリ1: i=6 を取り除く
 +    [ 1  1  1  0  0 [0] 1  1  1 ]    ←該当位置を0にする
 +    [ 2  3  4  6  6  7  8  9  x ]    
 +  
 +  クエリ2: i=4 に対する答え
 +    [ 1  1  1 [0] 0 [0][1] 1  1 ]    同様に4→6→7と辿って、
 +    [ 2  3  4 [6] 6 [7] 8  9  x ]    7があったので7が答え
 +    
 +    後処理
 +    [ 1  1  1  0  0  0  1  1  1 ]
 +    [ 2  3  4 [7] 6 [7] 8  9  x ]    更新
 +
 +一度辿った値についてはスキップできるので、償却するとクエリ2を1回あたり $O(\log{N})$ で行えるようになる。
 +
 +=== バリエーション ===
 +
 +== 値が復活する ==
 +
 +無理。BITなどを使いましょう。
 +
 +
 +
 +==== ピボット木 ====
 +
 +  * [[https://qiita.com/Kiri8128/items/6256f8559f0026485d90|平衡二分木を実装する - Qiita]]
 +
 +上記で紹介されている平衡二分探索木。結構速いみたい。
 +
 +  * 制約
 +    * 載せられるのは整数値のみ
 +      * $1～2^K-1$ までの整数値を入れられて、$K$ は最初に決定する必要がある（後から拡張はやろうと思えばできる）
 +    * 同じ値は複数持てない
 +
 +  * できること（$N=2^K$ として）
 +    * 挿入 $O(\log{N})$
 +    * 削除 $O(\log{N})$
 +    * ある値が存在するかの検索 $O(\log{N})$
 +    * ある値より大きい・小さい直近の値の検索 $O(\log{N})$
 +
 +メリットとして、入れる値が整数なら上限値が $10^9$ などのように大きくても座標圧縮が必要ない。\\
 +（BIT木のように最初に配列を作るのでは無く、挿入ごとにノードインスタンスを作るので）
 +
 +アイデアとしては、各ノードは、自身の位置に応じたpivot値を持つ。
 +
 +たとえば値 $x$ を挿入するとき「上から挿入箇所を辿っていって、pivot値が $x$ と等しいノードに来たら $x$ はそこでFIXし、代わりにそこに入っていた元の値の挿入箇所をその地点から探し始める」ようなことを行う。
 +
 +これにより、高さが最初に決めた $K$ 以上にならないことが保証されるとともに、他の平衡二分探索木で発生する「回転操作」、つまりは左右の子を繋ぎ替えるなど、値の書き換えを減らしている。
 +
 +=== バリエーション ===
 +
 +== 実数値を載せる ==
 +
 +ピボット値を小数範囲に拡張して、$0.5, 0.25, 0.125, ...$ 単位まで探索できるようにする。
 +
 +ただし、探索深さの上限が保証されなくなる。（まぁ、極端に狭い範囲に多くの値が集中しない限り実用的に問題となることは少ないはず）
 +
 +== 複数の整数のTupleを載せる ==
 +
 +bitshiftして1整数にまとめてやる。
 +
 +値の上限が大きくなると計算量も増えるが、例えば上限 $10^6$ の整数を3つ管理しても約 $2^{60}$、$K=60$ なので、そこまで無理なものではない。
 +
 +== 同じ値を持つ ==
 +
 +辞書などで各値の個数を管理して、削除時に個数が"0"にならない限りノードは削除しない、みたいな拡張でいけそう。
 +
 +== $k$ 番目を求める ==
 +
 +ノードに自身の部分木以下のノードの個数を持たせておく。
 +
 +
 +++++ 同じ値を持て、$k$ 番目も求められるようにした |
 +
 +<sxh python>
 +class BalancingPivotTree:
 +    """
 +    元とさせていただいたアイデア・コード
 +    https://qiita.com/Kiri8128/items/6256f8559f0026485d90
 +    ・個数を管理し、多重集合を管理できるようにした
 +    ・K番目を取得できるようにした
 +
 +    Features:
 +    append(v)
 +    delete(v)
 +    get_kth(k)
 +    find_l(v)
 +    find_r(v)
 +    min
 +    max
 +    """
 +
 +    def __init__(self, n):
 +        self.N = n
 +        self.root = self.node(1 << n, 1 << n)
 +        self.count = {1 << n: 1}
 +
 +    def append(self, v):
 +        """ v (0 <= v <= 2^n-2) を追加 """
 +        v += 1
 +
 +        if v in self.count:
 +            self.count[v] += 1
 +        else:
 +            self.count[v] = 1
 +        inc = 1
 +
 +        nd = self.root
 +        while True:
 +            nd.subtree_count += inc
 +            if v == nd.value:
 +                # v がすでに存在する場合に何か処理が必要ならここに書く
 +                return 0
 +            else:
 +                mi, ma = min(v, nd.value), max(v, nd.value)
 +                if mi < nd.pivot:
 +                    if nd.value != ma:
 +                        inc = self.count[mi]
 +                    nd.value = ma
 +                    if nd.left:
 +                        nd = nd.left
 +                        v = mi
 +                    else:
 +                        p = nd.pivot
 +                        nd.left = self.node(mi, p - (p & -p) // 2)
 +                        nd.left.subtree_count = self.count[mi]
 +                        break
 +                else:
 +                    if nd.value != mi:
 +                        inc = self.count[ma]
 +                    nd.value = mi
 +                    if nd.right:
 +                        nd = nd.right
 +                        v = ma
 +                    else:
 +                        p = nd.pivot
 +                        nd.right = self.node(ma, p + (p & -p) // 2)
 +                        nd.right.subtree_count = self.count[ma]
 +                        break
 +
 +    def leftmost(self, nd):
 +        if nd.left: return self.leftmost(nd.left)
 +        return nd
 +
 +    def rightmost(self, nd):
 +        if nd.right: return self.rightmost(nd.right)
 +        return nd
 +
 +    def find_l(self, v):
 +        """ vより真に小さいやつの中での最大値（なければ-1） """
 +        v += 1
 +        nd = self.root
 +        prev = 0
 +        if nd.value < v: prev = nd.value
 +        while True:
 +            if v <= nd.value:
 +                if nd.left:
 +                    nd = nd.left
 +                else:
 +                    return prev - 1
 +            else:
 +                prev = nd.value
 +                if nd.right:
 +                    nd = nd.right
 +                else:
 +                    return prev - 1
 +
 +    def find_r(self, v):
 +        """ vより真に大きいやつの中での最小値（なければRoot） """
 +        v += 1
 +        nd = self.root
 +        prev = 0
 +        if nd.value > v: prev = nd.value
 +        while True:
 +            if v < nd.value:
 +                prev = nd.value
 +                if nd.left:
 +                    nd = nd.left
 +                else:
 +                    return prev - 1
 +            else:
 +                if nd.right:
 +                    nd = nd.right
 +                else:
 +                    return prev - 1
 +
 +    @property
 +    def max(self):
 +        return self.find_l((1 << self.N) - 1)
 +
 +    @property
 +    def min(self):
 +        return self.find_r(-1)
 +
 +    def delete(self, v, nd=None, prev=None, dec=1):
 +        """ 値がvの要素を1個削除（なければ何もしない） """
 +        v += 1
 +
 +        needs_delete = True
 +        if nd is None:
 +            if v not in self.count:
 +                return
 +            elif self.count[v] == 1:
 +                del self.count[v]
 +            else:
 +                self.count[v] -= 1
 +                needs_delete = False
 +            nd = self.root
 +
 +        if prev is None:
 +            prev = nd
 +
 +        while v != nd.value:
 +            prev = nd
 +            if v <= nd.value:
 +                if nd.left:
 +                    nd.subtree_count -= dec
 +                    nd = nd.left
 +                else:
 +                    #####
 +                    return
 +            else:
 +                if nd.right:
 +                    nd.subtree_count -= dec
 +                    nd = nd.right
 +                else:
 +                    #####
 +                    return
 +
 +        nd.subtree_count -= dec
 +        if not needs_delete:
 +            return
 +
 +        if (not nd.left) and (not nd.right):
 +            if not prev.left:
 +                prev.right = None
 +            elif not prev.right:
 +                prev.left = None
 +            else:
 +                if nd.pivot == prev.left.pivot:
 +                    prev.left = None
 +                else:
 +                    prev.right = None
 +
 +        elif nd.right:
 +            # print("type A", v)
 +            nd.value = self.leftmost(nd.right).value
 +            self.delete(nd.value - 1, nd.right, nd, self.count[nd.value])
 +        else:
 +            # print("type B", v)
 +            nd.value = self.rightmost(nd.left).value
 +            self.delete(nd.value - 1, nd.left, nd, self.count[nd.value])
 +
 +    def get_kth(self, k: int):
 +        """
 +        k番目を取得。現存する要素数より大きい数を指定すると-1
 +        :param k:
 +        :return:
 +        """
 +        nd = self.root
 +        if nd.subtree_count - 1 < k:
 +            return -1
 +
 +        while True:
 +            cnt = self.count[nd.value]
 +            if nd.left is None:
 +                if k <= cnt:
 +                    return nd.value - 1
 +                assert nd.right is not None
 +                k -= cnt
 +                nd = nd.right
 +
 +            else:
 +                if nd.left.subtree_count >= k:
 +                    nd = nd.left
 +                elif nd.left.subtree_count + cnt >= k:
 +                    return nd.value - 1
 +                else:
 +                    assert nd.right is not None
 +                    k -= nd.left.subtree_count + cnt
 +                    nd = nd.right
 +
 +    def __contains__(self, v: int) -> bool:
 +        return v + 1 in self.count
 +
 +    class node:
 +        def __init__(self, v, p):
 +            self.value = v
 +            self.pivot = p
 +            self.left = None
 +            self.right = None
 +            self.subtree_count = 1
 +
 +        def __repr__(self):
 +            lch = self.left.value - 1 if self.left else -1
 +            rch = self.right.value - 1 if self.right else -1
 +            return f'({self.value - 1}, {self.pivot}, {lch}, {rch}, {self.subtree_count})'
 +
 +    def debug(self):
 +
 +        def debug_node(nd):
 +            re = []
 +            if nd.left:
 +                re += debug_node(nd.left)
 +            if nd.value: re.append(str(nd))
 +            if nd.right:
 +                re += debug_node(nd.right)
 +            return re
 +
 +        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])
 +        print('Debug ', self.count)
 +
 +    def debug_list(self):
 +        def debug_node(nd):
 +            re = []
 +            if nd.left:
 +                re += debug_node(nd.left)
 +            if nd.value:
 +                re.extend([nd.value - 1] * self.count[nd.value])
 +            if nd.right:
 +                re += debug_node(nd.right)
 +            return re
 +
 +        return debug_node(self.root)[:-1]
 +
 +    def debug_count(self, nd=None):
 +        if nd is None:
 +            nd = self.root
 +        lch = nd.left.subtree_count if nd.left is not None else 0
 +        rch = nd.right.subtree_count if nd.right is not None else 0
 +        if nd.subtree_count != lch + rch + self.count[nd.value]:
 +            print('NG!!', nd, lch, rch, self.count[nd.value])
 +            print(self.debug_list())
 +            print(self.count)
 +        if lch != 0:
 +            self.debug_count(nd.left)
 +        if rch != 0:
 +            self.debug_count(nd.right)
 +
 +
 +bpt = BalancingPivotTree(5)  # 0-30の要素を入れられる
 +bpt.append(3)
 +bpt.append(20)
 +bpt.append(5)
 +bpt.append(10)
 +bpt.append(5)
 +bpt.append(13)
 +bpt.append(20)
 +bpt.append(3)
 +
 +print(bpt.debug_list())
 +assert (3 in bpt) == True
 +assert (4 in bpt) == False
 +assert (5 in bpt) == True
 +assert bpt.find_l(12) == 10
 +assert bpt.find_l(13) == 10
 +assert bpt.find_l(14) == 13
 +assert bpt.find_r(3) == 5
 +assert bpt.find_r(4) == 5
 +assert bpt.find_r(5) == 10
 +assert bpt.find_r(6) == 10
 +assert bpt.min == 3
 +assert bpt.max == 20
 +assert bpt.get_kth(1) == 3
 +assert bpt.get_kth(2) == 3
 +assert bpt.get_kth(3) == 5
 +assert bpt.get_kth(4) == 5
 +assert bpt.get_kth(5) == 10
 +assert bpt.get_kth(6) == 13
 +assert bpt.get_kth(7) == 20
 +assert bpt.get_kth(8) == 20
 +assert bpt.get_kth(9) == -1
 +
 +bpt.delete(20)
 +print(bpt.debug_list())
 +bpt.delete(3)
 +print(bpt.debug_list())
 +bpt.delete(10)
 +print(bpt.debug_list())
 +bpt.delete(20)
 +print(bpt.debug_list())
 +bpt.delete(3)
 +print(bpt.debug_list())
 +bpt.delete(5)
 +print(bpt.debug_list())
 +
 +assert bpt.find_l(5) == -1
 +assert bpt.find_l(6) == 5
 +assert bpt.find_r(12) == 13
 +assert bpt.find_r(13) == 31
 +assert bpt.min == 5
 +assert bpt.max == 13
 +assert bpt.get_kth(1) == 5
 +assert bpt.get_kth(2) == 13
 +assert bpt.get_kth(3) == -1
 +
 +print()
 +
 +# 愚直チェック
 +from random import randrange
 +from bisect import insort
 +
 +bpt = BalancingPivotTree(6)  # 0 ～ 62 までの要素を入れられるピボット木
 +S = []
 +for _ in range(10000):
 +    a = randrange(63)
 +    if randrange(2) == 0:
 +        print(f'append {a}')
 +        bpt.append(a)
 +        insort(S, a)
 +    else:
 +        print(f'delete {a}')
 +        bpt.delete(a)
 +        if a in S:
 +            S.remove(a)
 +
 +    if bpt.debug_list() != S:
 +        print('NG!! Arrays are not same.')
 +        print('BT:', bpt.debug_list())
 +        print('LS:', S)
 +
 +    elif len(S) > 0:
 +        k = randrange(len(S))
 +        bpt_k = bpt.get_kth(k + 1)
 +        if bpt_k != S[k]:
 +            print(f'NG!! k({k + 1})th item is wrong.')
 +            print(f'BT: {bpt_k} vs LS: {S[k]}')
 +
 +        bpt.debug_count()
 +
 +print("END")
 +</sxh>
 +
 +++++
 +
 +==== 平方分割で管理 ====
 +
 +  * [[https://github.com/tatyam-prime/SortedSet|GitHub - tatyam-prime/SortedSet]]
 +
 +そもそも単なるリスト（配列）でも、ソートされていれば検索は二分探索を使えば $O(\log{N})$ でいける。\\
 +計算量的に問題となるのは、ソート状態を保ちつつの要素の挿入や削除。要素を1つずつずらすのに $O(N)$ かかる。
 +
 +  [ 2  3  5  9 ]     4 を挿入
 +           ↘ ↘
 +  [ 2  3  4  5  9 ]  入ってる要素数、または後ろにある要素数だけ値のコピーが発生
 +
 +これを、「$\sqrt{N}$ 個のリストに $\sqrt{N}$ 個の要素が入った状態」として管理することで、
 +挿入・削除を平均 $O(\sqrt{N})$ にしてしまおうというアイデア。
 +
 +どのリストに入っているかの検索に新たなコストが発生するものの、そこそこ高速に動作する。
 +
 +挿入・削除を繰り返すと徐々に要素数にばらつきが出てくるので、定期的に再構築する。
 +
 +またデータ型が整数値など単純なものであれば、listを使うよりarray.arrayを使った方が高速に動作する？
 +
 +  * [[https://docs.python.org/ja/3/library/array.html|array --- 効率のよい数値アレイ — Python ドキュメント]]
 +
 +
 +メリットとして、巨大な値、小数値、タプル、その他も大小が定義できれば、そのまま入れられる。
  
programming_algorithm/data_structure/balancing_binary_search_tree/tree_free.1593447843.txt.gz · 最終更新: 2020/06/29 by ikatakos
文書の表示
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0