Was ist der Unterschied zwischen Array und Binärer Suchbaum in der Effizienz?

Ich will wissen, was das beste ist : Array ODER Binary search tree in ( einfügen , löschen , suchen max und min ) und wie kann ich die beiden von Ihnen ?

  • Haben Sie versucht, die Suche für diese Informationen? Es sollte leicht zu finden sein.
  • Meinst du, dass die abstrakte Datenstrukturen Link-Liste und binary search tree?
  • verbessern in welcher Weise? das beste für was? das sind völlig verschiedene Daten-Strukturen, und jeder von Ihnen könnte das 'beste' für eine bestimmte Anwendung.
InformationsquelleAutor Totoo Boo | 2011-12-27
  1. 14

    Einer array ermöglicht random access auf jedes element in ihm. so erhalten Sie das einfügen, löschen und suchen Sie nach einem bestimmten element in O(1) - und max/min, löschen Sie in O(n). [Sie können auch min - /max - O(1) und löschen O(n) statt]. Wenn Sie halten Ihr array sortiert, es wird dazu führen, einfügen/löschen werden O(n), aber Sie werden gewinnen O(logn) finden, und O(1) min/max.

    Einen BST sortiert nach definition, und für eine regelmäßige [unbalanced] BST, erhalten Sie O(n) worst-case Verhalten. Für ausgewogene BST, erhalten Sie O(logn) einfügen/löschen/suchen. Sie können erhalten O(1) min/max jeder, wie für beide.

    Arrays sind in der Regel auch schneller zu iterieren [vorausgesetzt der Reihenfolge der iteration ist nicht wichtig,] weil Sie einen besseren cache Leistung. Auch, im Gegensatz zu BST - die grenzenlose Größe, die von der Natur mit einem array erfordert Umverteilung und kopieren der Daten, wenn das array voll ist.

    Verbesserung eine BST-getan werden kann, indem es ausgewogene - wie AVL oder rot-schwarz-Bäume.

    Was ist besser? es hängt von der Anwendung ab. In der Regel, wenn Sie planen, um die Daten einzufügen und halten Sie Sie sortiert, BST, werden bevorzugt. Wenn random-access-oder iteration ist der Hauptzweck: Sie in der Regel verwenden Sie ein array.

    • Warum ist die findMin/findMax ständige Operationen O(1) für eine ausgewogene BST?
    • Wenn Sie einfügen/entfernen eines Elements aus einer ausgewogenen BST, es ist O(logn) und O(n) für nicht ausgeglichene BST. Sie können erhalten zusätzliche Zeiger min und max sind, die nur dann geändert werden, wenn Sie einfügen/remvoe Elemente von der BST. Die Suche nach einem neuen maximum/minimum ist O(logn) für ausgewogene BST und O(n) für nicht ausgewogen - so gibt es keine performance-Verlust [big O Bedingungen] in diesem Betrieb, und im Sinne von big O pflegen Sie diese Zeiger für "freie"
    • Ah,so du meinst mit extra Zeiger.Aber in diesem Fall ist eine Optimierung, die nicht direkt mit dem BST-algorithmen.So ist es nicht etwas widersprüchlich/irreführend zu behaupten, in einem Vergleich mit einer anderen Datenstruktur (in diesem Fall ein array), die max/min ist O(1) da es nicht standardmäßig?Man muss es implementieren, so dass es
    • Ich habe ausdrücklich gesagt, dass Sie bekommen Sie: You can get O(1) min/max any how for both. Die Idee ist, diese Erweiterung ist "frei" im Sinne von big O notation - und wenn Sie brauchen, min/max: es gibt keinen Grund, es nicht zu tun. Jedoch, im Vergleich zu den nicht-sortierten array [das Thema dieses Threads]: Sie kann nicht beides tun O(1) einfügen O(1) min/max , so ist es wichtig, die Tatsache zu erwähnen, dass man kann bekommen O(1) max/min mit BST für "frei".
    • Vielen Dank für die Erklärung dieser zu mir.+1 von mir
    • Sie sind willkommen, das ist, was SO ist 🙂

    InformationsquelleAutor amit
  2. 13

    Performance-Vergleich von Arrays und Binäre suchbäume:

                     Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

    * vorausgesetzt binäre Suche

    ** erfordert zusätzliche Zeiger auf min und max, sonst ist es in O(log n)

    • Warum ist O(1) finden die min/max-von BST?
    • Jetzt, dass Sie Fragen, ich bin mir nicht sicher, ob es richtig ist. Binäre suchbäume sind sortiert nach definition, aber (abhängig von der Implementierung?) es kann nicht möglich sein, um die min/max in O(1). In diesem Fall wäre es O(log n) statt.
    • Es ist nicht O(1) es sei denn, Ihre Umsetzung hält einen Zeiger auf die min und max Werte.Überprüfen Sie auch die Kommentare in der Antwort von amit
    • Guter Vorschlag, habe ich bearbeitet meine Antwort.
    InformationsquelleAutor Peladao
Schreibe einen Kommentar