リミットオーダーブック：購入/売りオーダーリストを維持するためのデータ構造

Question

私は買い/売り注文リストを含む制限オーダーブックを作成したいと考えています。買い注文リストでは、最も高い買い値はリストの最初にあり、売り注文リストでは最も低い売り値がリストの最初にあるはずです。新しく注文する場合は、リストに挿入するための適切な場所を取得したいと考えています。

現在、私は挿入する線形検索を使用していますが、それは順序数百万人のための非常に高いですO（n）の時間がかかります。

O（log n）以下の時間でソートされたリンクリストにノードを挿入できるデータ構造はありますか？

Answer 1

ノードをO（log n）以下の時間でソートされたリンクリストに挿入しますか？

これは不可能です。 （一度にのみminまたはmaxをしたい場合）は、データを保存するために二分探索木または分ヒープを使用することができますしかし

。バランスの取れたバイナリ検索ツリーを使用すると、データを並べ替えて保存するだけでなく、O（log n）時間に挿入/削除することができます。