Wie hoch ist die Laufzeitkomplexität der Java TreeMap firstEntry()-Methode in Big O?

Question

Ich weiß, dass diese Klasse einen Rot-Schwarz-Baum verwendet, aber bedeutet das, dass es O(log(n)) ist, um das kleinste Element zu erhalten oder ist es O(1) oder etwas anderes?

Gracias.

Answer 1

Da es sich um eine binärer Suchbaum muss sie die Höhe des Baums durchqueren (was O(log n) ist), um den ersten (d.h. kleinsten) Eintrag zu erreichen, so dass die Methode tatsächlich O(log n) ist.

Sie können sehen, wie es in OpenJDK implementiert ist aquí .

/**
 * 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;
}

---

Wenn Sie nach einer Struktur suchen, die die Suche nach dem Minimum in konstanter Zeit unterstützt, sollten Sie vielleicht die Verwendung einer Binär-Min-Haufen , wobei der Wurzelknoten dem Minimum entspricht. Beachten Sie, dass dies eine völlig andere Datenstruktur mit einer anderen Semantik ist.