Sを整数の動的セットとします。 n = | S |とする。 Sのデータ構造を に記述すると、必要な性能保証を備えたSの次の操作がサポートされます。trailingalの順にavlツリー
•新しい要素をO（log n）時間に挿入します。
•O（log n）時間内にSから要素を削除します。
•1≤k≤nを満たす任意のkに対して、O（k）時間内にSのk個の最小要素を報告します。
あなたの構造は常にO（n）スペースを消費しなければなりません。
私は単純にAVLツリーを構築し、最初の3つの要素を横断的に印刷するためにプリフォームできますか？
あなたの提案された解決策は、O（k）時間では機能しません。順序通りのトラバーサルを開始するには、O（log n）時間がかかります。 1つの要素を見つけた後で停止しても、最も左の葉に最初に到達する必要があります。
私は2つの解決策を考えることができます。
はskip-listを使用し、それはO（n個のログ）の挿入や削除を持っており、基礎となるリストがソートされます。しかし、挿入および削除の時間の複雑さは平均であり、最悪の場合ではない。
変更されたAVL-treeを使用し、一番左のノードに専用のポインタを置き、挿入および削除時にそれを更新します。また、ノードは親ノードへのポインタを持たなければならないので、一番左のノードから順に探索を行うことができます。または、threaded treeを使用します。
メモリが不足しているときの親参照を戻す方法の代わりに、[threaded trees]（https://en.wikipedia.org/wiki/Threaded_binary_tree） - 左端および/または右端の_node_（葉ではない） ） 必要に応じて。 – greybeard
@greybeardあなたのコメント –
で編集していただきありがとうございます。余分なポインタがスペースの制約に違反していましたか？ – 101ldaniels
O（n）スペースを使用する優先キューを使用します。挿入と削除は両方ともO（log n）操作です。 Find-minはO（1）で、その後にremove-min（O（k））が3回繰り返されます。
です（https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times）remove min is O（log n ） –
あなたは正しいです。私の悪い。私は愚かではないことを私に思い出させるためにここに答えを残す。 – user448810
IVEが保存することを決定し、ルートに最もノードポインタを左に更新され、すべての挿入時に
ので、すべてのノードで、前任者と後継者へのポインタは、それが挿入およびO（LOGN）のためにO（LOGN）のコスト+ O （logn）+ O（logn）= O（logn）
これらのポインタは、O（1）に挿入した後に影響を受けるノードポインタの更新も可能にします。 ）をそれぞれ前任者または後継者に移動し、O（1）にポインタを更新する
ルートに最も左のノードへのポインタを持つポインタは、travell O（1）が存在し、その後、O（k）時間内に後続ノードを走査して最初のk個のノードを印刷する。
'AVLツリーを単純に構築して、最初の3つの要素を順序通りのトラバーサルを使って印刷できますか？これは100万要素でどれくらいの時間を要しますか？百万人？ [Googolplex]（https://en.wikipedia.org/wiki/Googolplex）？ – greybeard
標準的な答えは、バランスのとれたスレッドバイナリ検索ツリーです。これは、リーフノードでNULLポインタを使用するBBSTです。これらは、ソートされた順序でリンクされたリストの近くのノードに接続します。それは、挿入または削除（ノードタッチごとに一定の時間）ごとにO（ログn）だけの追加時間でポインタを維持できることがあります。 O（k）時間に最初のk個のノードをリストの先頭からたどることでリストすることができます。 http：// adtinfoにはかなり美しい実装があります。org/ – Gene