java - Java TreeMap firstEntry() メソッドの Big O での実行時の複雑さはどのくらいですか?

Question

このクラスが赤黒木を使用していることは知っていますが、それは O(log(n)) で最小の要素を取得することを意味するのでしょうか、それとも O(1) か何か他のものでしょうか?

ありがとう！

Answer 1

二分探索木であるとすると、最初の (つまり最小の) エントリに到達するためには、木の高さ (O(log n)) をトラバースする必要があるため、実際の方法は O(log n) です。

OpenJDK での実装方法はこちらで確認できます。

/**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

---

一定時間の find-minimum をサポートする構造を探している場合は、ルート ノードが最小値に対応するバイナリ min heapの使用を検討してください。これは、セマンティクスが異なるまったく異なるデータ構造であることに注意してください。