Randomized Binary Search Tree
-
ABC170 Eの解説で
-
順序付き多重集合は C++ の multiset などを用いることで高速に処理することができます。
- と書かれていたため、C++のmultisetに相当するものはPythonだと何?と話題になった
- Pythonでmultiset heapqを使ってなんとかするケースが多い
- Pythonの標準ライブラリには平衡二分木がない
- 自前ライブラリとして持っておくといいのでは…という気持ちになった
-
-
ノードをオブジェクトとして作ってるような実装は全般的に筋悪
- オブジェクトの生成コストが高いので。
- 配列で実装してnumbaでコンパイルする方針で作る
-
ABC170Eで AC した
--- 開発