平衡二分探索木の実装(AVLtree) C++のstd::map、std::setのようなもの 木の大きさ（削除済みノードを含む）をnとして insert(key, val) : 要素の追加、置換 O(log n) search(key) : 要素の検索 O(log n) delete(key) : 要素の削除 O(log n) lower_bound(key) : key以上の最小の要素 O(log n) upper_bound(key) : keyより大きい〃 O(log n) len() : 木の頂点数取得 O(1) deleteは配列から実際に要素を削除しているわけではないので、配列はどんどん大きくなっていく O(n)でcleanupする関数を書いてもいいかも
visualizerつけました 数以外の順序を扱いたいので compare関数をつけました perlでの<=>の逆みたいな関数ですね 高速化はしてないです 本当は赤黒木が欲しかった デバッグとかは全部GPTにやってもらいました LibraryCheckerでverifyはしたつもり (64分木のやつ) WAは出なかったので大丈夫でしょう (RE(MLE),TLEは出た)
