競プロ用ライブラリを作る Advent Calendar 2024の15日目です.
BinaryTreeって?
列の情報を木で管理するデータ構造です.
「途中に挿入したり途中の要素を削除するコストが低い配列」として使えます.
仕組み
列の情報を木で管理します.
どういうことかというと, 列$x_1,x_2,...,x_N$と列$y_1,y_2,...,y_M$をくっつけた列$x_1,...,x_N,y_1,...,y_M$を「列$x$の表現と列$y$の表現が子になってる2分木」で表現するということです.
↓の図のように再帰的にデータを表現します
この方法ですが, こういうケースみたいなのが与えられると先頭の要素を見るのに$O(N)$かかってしまい遅いです.
これを解決するに, 偏り過ぎないようにいい感じにバランスを取る必要があります.
バランスをとる方法は色々なのが考案されていますが, 以前再発明したことがあるWeight Balanced Treeというものにしてみます.
これは「片方の子の要素数がもう片方の要素数の3倍未満」を保つようにするんですけど, この基準から外れたら図のように操作すれば上手くいきます
画像: https://commons.wikimedia.org/wiki/File:Tree_Rebalancing.gif
証明は以前やったんですけど, かなり大変だったので省略します.
実装
折角なのでunsafe Rustをゴリゴリに使ってみました. 木の各頂点は自身の要素数を持たず,「左の子の要素数」を持つようにします.
一番根本だけが全体の要素数を持って, そこから探索するときに要素数を逐一調べていく感じです.
末端の要素かそうでないかの情報を減らしてメモリ削減になります.
正直あまり意味はないですが, 折角ライブラリを整備するのでそういうところまで徹底しましょう.
まとめ
いかがでしたか?
明日は便利そうで実際はあんまり使う機会はないものを実装します.