ノードの削除と挿入に少なくとも Log(n) の複雑さを保証できるデータ構造と、最大 (または最小) 値を検索するために O(1) または償却 Log(n) に近いものを探しています。
挿入された最大値 (または最小値) を記憶するように修正されたセルフバランス BST (どれ?) を使用することを考えていました。
なにか提案を？
申し訳ありませんが、質問を編集する必要があります...もちろん、自己バランス型の BST では、log(n) で最大値と最小値を検索できますが、O(1) に向けてもっと何かを考えていました。
ほぼすべての自己平衡 BST (赤黒、AVL など) を使用できます。
最小値と最大値を追跡すると、それらを取得するためのクエリに O(1) かかります。
最小値と最大値は挿入と削除でのみ変更できるため、これらの操作を実行するときに基本的に再決定できます (O(log n) で) (それらの実行時間は O(log n) のままです)。
ただし、クエリを受信し、最後のクエリ以降に挿入または削除があった場合は、最小値または最大値を再決定することをお勧めします。
それについてもっと賢くなることも可能です。これまで左にしか行っていない場合は最小であり、右にしか行っていない場合は最大です。挿入するときは、必要に応じて最小値/最大値を置き換えてください。削除するときは、削除されたノードからツリー内を見回して、新しい最小値/最大値を見つけてください。