Was ist der Unterschied zwischen Array und binärem Suchbaum in der Effizienz?

Ein Array erlaubt Direktzugriff für jedes Element darin. So erhalten Sie einfügen, löschen und suchen Sie nach einem bestimmten Element in O(1) , und max / min, löschen in O(n) . [Sie können auch max / min O(1) und stattdessen O(n) löschen]. Wenn Sie Ihr Array sortiert halten, wird insert / delete O(n) sein, aber Sie erhalten O(logn) find und O(1) min / max.

Eine BST ist nach Definition sortiert, und bei einer normalen [unsymmetrischen] BST erhalten Sie O(n) worst case-Verhalten. Für balanced BST erhalten Sie O(logn) insert / delete / find. Sie können O(1) min / max irgendein wie für beide erhalten.

Arrays sind in der Regel auch schneller, iterieren [vorausgesetzt, die Reihenfolge der Iteration ist nicht wichtig], da Sie besser Cache Leistung. Im Gegensatz zu BST, dessen Größe von Natur aus unbegrenzt ist, erfordert ein Array die Neuzuweisung und das Kopieren der Daten, wenn das Array voll ist.

Eine BST verbessern kann durch ausgeglichen - wie AVL oder Rot-Schwarz-Bäume .

Was ist besser ? Es hängt von der Anwendung ab. Normalerweise, wenn Sie planen, Daten einzufügen und sortiert zu halten, wird BST bevorzugt. Wenn Direktzugriff oder Iteration der Hauptzweck ist: Du benutzt normalerweise ein Array.

Leistungsvergleich von Arrays und binären Suchbäumen:

* unter der Annahme einer binären Suche

** erfordert extra Zeiger auf min und max, ansonsten ist es O (log n)