Vorteile von verknüpften Listen über binäre Bäume?

Der Titel ist weitgehend selbsterklärend: was sind die Vorteile von verknüpften Listen über binäre Bäume? Der einzige Fall, an den ich denken kann, in dem eine verlinkte Liste ist effizienter für die Iteration über jedes element, in welchem Fall es ist immer noch ziemlich nah. Es sieht aus wie binäre Bäume sind schneller, sowohl den Zugriff auf Daten und das einfügen neuer Elemente. Also warum verwenden Sie eine verknüpfte Liste überhaupt?

Was sind die Vorteile eines binären Baums über ein 17-ary Baum? Wenn 2 besser als 1, dann 17 ist eine ganze Menge besser als 2, richtig? 🙂
Nur dann, wenn du 17 Vergleiche in einem Betrieb.
Oben alles schon erwähnt, verknüpfte Listen sind nützlich für die Durchführung der anderen Datenstrukturen wie stacks und queues.
Was sind die Vorteile von äpfeln über Orangen?
starblue: das fehlen von einzelnen Scheiben macht infix-Verbrauch O(1) anstatt O(n), und die essbare Schale tendenziell niedriger ist der Konstante Faktor, auch.

InformationsquelleAutor Michael Dickens | 2010-01-10

  1. 6

    Wenn der Schwanz von einer verknüpften Liste gespeichert ist, dann einfügen in einer verknüpften Liste ist deutlich schneller als das einfügen in einen binären Baum. Einfügen in einen binären Baum ist O(N) im schlechtesten Fall (O(log N) am besten), wenn es unausgewogen. Wenn es ausgeglichen ist, dann werden die Einfügungen werden in O(log N), aber es gibt Haus halten beteiligt, halten es ausgeglichen. Einfügen in eine verkettete Liste O(1), wenn die Rute gehalten wird.

    Auch, wie BillyONeal erwähnt, einem binären Baum ist in der Regel eine assoziative Struktur, in der Erwägung, dass verketteten Listen nicht.

    Das stimmt für binäre Suche - Baum, aber in dem Allgemeinen Fall einer (unsortierten) - binary tree, Einfügungen sind immer noch O(1) -- einer verknüpften Liste ist, nachdem alle, nur eine Entartete binäre Baum.
    Ein Baum ist nutzlos, wenn etwas ein Begriff der Art nicht angewendet wird. Dies kann nicht eine lexikalische Reihenfolge, vielleicht, aber einige index. In jedem Fall, einen Pfad, die befolgt werden müssen, finden die richtigen Knoten, an dem um einen neuen Wert hinzuzufügen, das bedeutet immer noch O(log N) im besten Fall O(N) im schlimmsten Fall. Eine O(1) einfügen kann nur dann gelten, wenn der Knoten, dem ein Element Hinzugefügt wird, ist unwichtig, aber in diesem Fall, Lookup O(N), und es gibt keine Organisation, um die Daten überhaupt, so dass der overhead von einem Baum kommt mit keinen nutzen.
    Daddy, ist die Platzierung einer verwirrenden Begriff, wenn die Rede von verknüpften Listen. Append ist der O(1) operation, dem einfügen O(n).
    P Papa: Mein compiler hier baut ein AST. Das ist ein Baum, der nicht sortiert ist, indem Sie eine beliebige Taste, aber immer noch sehr nützlich. 🙂
    Da die definition von "Art" ist "in Ordnung", würde ich argumentieren, dass ja, es ist, aber es ist eine sinnlose semantische argument. Der Punkt ist, dass, gegeben ein Grundzustand, ein Baum Durchlaufen werden müssen, zu finden der entsprechenden Stelle, an der ein neues Element hinzufügen. Es müssen einige Konzept "Folgen Sie diesem Pfad bis zu diesem Knoten". Das ist der einzige Vorteil der Bäume und Ihre gesamte raison d ' être. Ein Baum ohne Vorstellung von Ordnung ist bedeutungslos.

    InformationsquelleAutor P Daddy

  2. 3

    Es ist einfacher/schneller zu löschen von Elementen aus einer verketteten Liste im Vergleich zu einem binären Baum, die benötigen könnten einige Operationen zu beheben Baum.

    InformationsquelleAutor tomzx

  3. 2

    Einer verknüpften Liste ist nicht allgemein verwendet als eine assoziative container (LESEN: Nicht als ein Wörterbuch) - nur als literal-Liste von Elementen, die wie ein array. Binäre Bäume Leistung, wenn so eine einfache Daten-Struktur gewünscht ist, ist arm.

    InformationsquelleAutor Billy ONeal

  4. 2

    In der verlinkten Liste sind die Objekte geordnet nach dem container selbst, so dass Sie nicht brauchen, um eine Vergleich-Funktion für die Objekte.

    InformationsquelleAutor Antti Huima

  5. 0

    Eine faire Frage. Ich benutze gerne den container, der die meisten "fest" passt meine Bedürfnisse. Sie können beispielsweise eine Liste verwenden, wenn alles, was Sie brauchen, ist eine Warteschlange ohne wirkliche Konsequenz... aber... die Schlangen sind hoch optimiert für diese eine spezifische Aufgabe, knallen an der front, und das einfügen auf der Rückseite, mit keine zusätzliche Zeiger oder irgendwas. Wenn Sie die entsprechende Klasse, können Sie sicher sein, Sie sind nicht immer alle extra-fluff, auch wenn es die gleichen Big-O. Manchmal die verborgenen Konstanten tun Angelegenheit.

    InformationsquelleAutor mpen

  6. 0

    Meistens kommt es auf Szenario. Wenn Schwanz der verlinkten Liste wird beibehalten, dann einfügen ist schnell in der verlinkten Liste. Die Löschung ist ganz schnell in der verlinkten Liste, aber bei der Suche ist es besser, in die Bäume( in o(log(n) für die Höhe, balance Baum ), während o(n) in der verlinkten Liste.

    InformationsquelleAutor GG.

  7. 0

    Ich nehme an, Sie sprechen über die tatsächliche binäre Suche Bäume, wo der Knoten Hinzugefügt werden unter Verwendung der algorithmen zu maximieren retrieval-Leistung. Im Gegensatz zu einem einfachen Baum, wo jeder Knoten hat maximal 2 Kind-Knoten.

    Einer verknüpften Liste ist oft unsortiert und so hinzufügen von neuen Knoten ist einfach eine O(1) operation, die normalerweise durch das Anhängen der Schwanz der Liste.

    Auf der anderen Seite einen binären Baum gespeichert werden müssen Knoten in einer bestimmten Bestell-Mechanismus (und möglicherweise durchzusetzen Ausgleich), um für eine effizientere Suche/retrieval operation.

    Wenn Ihr Algorithmus NICHT brauchen, um die Elemente abzurufen, sehr effizient, während Sie auch eine effiziente Sortierung der Elemente einer verketteten Liste, ist wahrscheinlich alles, was Sie brauchen.

    Queues und Stacks sind Beispiele für Datenstrukturen, die können glücklich sein, implementiert unter Verwendung einer verknüpften Liste.

    Hinweis: Platzhalter, um eine verkettete Liste ist eine andere (langsamere) - operation als addition/Anhängen. Einfügen erfordert oft Traversierung entlang der Liste, bis Sie die richtige position gefunden ist, O(n) wobei n die Länge der Liste. Ein append ist einfach hinzufügen, um den Schwanz der Liste (daher O(1))

    InformationsquelleAutor Ash

Schreibe einen Kommentar