data-structures - 指定されたキー以上の最小の要素を返し、キーを減らすことができる効率的なデータ構造

Question

次の操作を可能にする効率的な (log n) データ構造はありますか?

• 指定されたキー以上の最小の要素を返します
• この要素をより小さな要素と交換し、それに応じて構造を再配置します

要素の数は既知であり、存続期間中は変更されません。

Answer 1

赤黒木のようなバランスの取れた二分木を実装できます

赤黒木には、検索、挿入、および削除の時間の複雑さが O(log(n)) あります。

特定のキー以上の最小の要素を返すには、いくつかの変更を加える必要があります。しかし、基本的な動作は、私が推測するこのデータ構造によって提供されます。