Was ist die beste Art der Umsetzung Baum : LinkedList - Array

Ich bin auf eine Prüfung vorbereiten, eine der Fragen, die ich gestoßen bin, ist : was ist der beste Weg zur Umsetzung Baum, LinkedList oder ein Array ist.

Wahrscheinlich:
- Array verwendet 1 Adresse
- LinkedList verwenden Sie zwei Adressen.

Verwendung von LinkedList, fügen wir den Wert, den wir benötigen (wir perfekt verwalten den Speicher), aber die meisten likey Verwendung von O(N) für den Zugriff auf dieses element, während in der Reihe, es O(1).

Wie soll ich diese Frage beantworten ? Oder sollte ich einfach sagen, dass ist subjektiv.

Es hängt davon ab, ist der Baum ein BST?
Wir müssen auch wissen, Dinge wie, welche Sprache wir arbeiten. I. E. ist es eine Sprache mit Pointern? Welche Art von Baum, oder ist es nur zu Fragen, für wie generisch implementieren einen Knoten der Klasse (wenn die Sprache den Klassen)?
Wenn es ist ein binärer Baum, dann verwenden Sie verknüpfte Liste. Wenn es einen BTree mit einem branching-Faktor als B können Sie speichern die Schlüssel in einem Knoten in einem array und der Kind-Zeiger, die als verknüpfte Liste.
Ja ! Es ist ein Binärer Suchbaum. Sie sagte in C/Python.

InformationsquelleAutor user3378649 | 2014-03-10

data-structures

1

Für eine Binary Search Tree, die Antwort wäre auf jeden Fall ein array ( zumindest hoffentlich ein erweiterbares array, wie ein vector<> so sind Sie nicht beschränkt auf eine Feste Größe). Ich werde tun, eine Analyse der gemeinsamen Operationen, vorausgesetzt, der Baum ist ausgeglichen.

Abfrage

In einer BST-Knoten müssen die Zeiger auf linken und rechten Kindern und ist auch sehr Häufig auf den parent-Zeigern. In einem array Implementierung, der "Zeiger" können Sie einfach integer-Indizes in dem array ( das würde bedeuten das array speichern Node Objekte). So suchen die Eltern und die Kinder eines Knoten ist konstant, da die Indizierung in dem array konstant ist. O(1). Eine verkettete Liste Implementierung würde wahrscheinlich benötigen, um auch speichern Sie einen Verweis auf die position zu, wo Ihre Vorfahren/Kinder sind, so dass eine O(N) Durchlauf durch die Liste, um die gewünschten Referenzen.

Suche

Ab der root, array[0] Suche wäre ein O(log N) Betrieb. Die Suche würde einfach anrufen/Holen Sie sich die info der Kinder pro Knoten ist O(1) Menge der Arbeit, etwa O(log N) - mal, so O(log N) für die Suche in einem array.

Einer verknüpften Liste erfordern würde, ist eine O(N) Durchlaufen die Daten, um die erforderlichen Links - /rechts-Zeiger und kann auch durchgeführt werden in O(log N) Schritte, damit die eine O(n log n) Suche in verknüpften Listen.

Einfügen

Arrays ähnlich sein würden Suche, außer zusätzliche O(1) Konstante Zeit für Zeiger-Zuweisungen. So O(log N) einfügen.

Verketteten Listen wäre auch ähnlich wie Ihre Suche routine, außer mit einer zusätzlichen O(n) Zeit für die Justage der Zeiger, so O(n log n)

Löschen

Arrays wäre auch ähnlich Suche, außer, dass Sie mehr nehmen könnte, als ein Einzelzimmer O(log n) Faktor zu löschen, da Sie zu durchqueren wieder auf den Baum, aber es ist immer noch O(log n).

Verketteten Listen würde auch der O(n log n) plus mehr O(n log n) für aufwärts fahren. So O(n log n) für verknüpfte Listen als gut.

Abschluss

Sollte die Antwort ziemlich klar jetzt 🙂 Plus mit arrays erhalten Sie den Vorteil der besseren caching als verkettete Listen. Plus, einige Derivate des binären suchbäume, wie heaps (in der Regel min-heaps/max-heaps) sind Häufig vertreten, wie arrays,

Ich hoffe, das hilft 🙂
- Danke Mann! Sie sind GENIAL 🙂
- Ich bin froh, dass ich helfen konnte 🙂 viel Glück mit der Prüfung!
- In der Größenänderung von arrays, dauert es O(N) für das einfügen im schlimmsten Fall. Wenn Sie bei der Implementierung eines array-basierte Daten zu Struktur, ist es immer begleitet von einem resizing-Funktion, wie viele Elemente eingefügt werden, ist nicht vorgegeben.
- Guter Punkt @chettyharish , aber dann kann ich etwas tun, wie Tisch-Verdoppelung, um die Zuordnungen effizienter. Und wie ich schon am Ende, arrays zwischengespeichert werden kann, besser als verkettete Listen.
- Yep arrays sind immer die besten, obwohl die Tabelle verdoppeln würde erfordern das kopieren aller Elemente von der vorherigen array, so dass es eine O(N) - operation.
- Sollten Sie nicht über eine verknüpfte Struktur für einen binären Suchbaum? Legen Sie schieben würde alles runter vom index und in den großen Baum, der Auswirkungen haben wird.
- Hi, ich verstehe nicht, warum eine verlinkte Liste binären Suche Baum O(n log n) bei der Suche? Im schlechtesten Fall ist O(n) (die Knoten sind alle auf einer Seite) und in der Regel ist es in O(log n). Auch verstehe ich nicht, warum einfügen und löschen ist nicht O(log n) zu? Nur ein Elternteil den Zeiger geändert werden muss. Wie kommt es, es ist O(n) zu ändern Zeiger?
- Wollen Erklärung. Danke!!! @Alejandro
InformationsquelleAutor Alejandro
-2

Einer array ist, was ich nennen möchte ein grundlegender Typ. Das heißt, es ist im Grunde das Betriebssystem auf dem raw-Speicher des Systems. Sie können wickeln Sie einen grundlegenden array mit einer Klasse hinzufügen, um Dinge wie out-of-bounds-Schutz, aber du bist noch zu haben, die raw-Unterstützung für den Zugriff auf/Indizierung in einen block von Speicher, in etwas, das nicht Montage.

Für eine (einfach) verkettete Liste, in python würde es so Aussehen:
```
 class Entry(object):
       def __init__(self, value, child = None)
           self.child = child
           self.value = value

 class LinkedList(object):
       def __init__(self, root_entry = None):
           self.root = root_entry
           self.tail = self.root
           self.size = 1 if root_entry else 0

       def add_entry(value):
           new_entry  = Entry(value)
           if size:
              self.tail.child = new_entry
           else:
              self.root = new_entry
           self.tail = new_entry
           self.size +=1

       ...
```
Und so weiter, können Sie sehen, dass für die meisten Vorgänge, die Sie einfach Durchlaufen die Stamm-Kinder, bis Sie erhalten, wo Sie sein möchten. Einfügen eines Elements bedeutet einfach einbauen, dass man den Eintrag Kind mit den neuen Eintrag und setzen Sie den neuen Eintrag Kind auf das alte Kind (und increment size)

In der Regel für einfach verknüpfte Listen-element insertion O(1) wenn Sie bereits den alten Eintrag (der Sie für die meisten Iteratoren) oder am Heck/root. Suche nach einem element mit index O(n), wie Sie benötigen zum Durchlaufen der Liste, und Iteratoren können nur down die Liste (ist von index = 0 zu index = size-1.

Im Grunde alle diese Informationen kann untersucht werden, indem Sie einfach die Lektüre des entsprechenden wikipedia-Einträge. Diese sind alle ziemlich grundlegende Typen, die haben schon eine sehr lange Zeit.
- Sie sind nicht die Beantwortung der Frage: geben Sie Allgemeine Informationen über die LinkedList und BST.
- Das ist genau das, was seine Frage ist, what is the best way to implement tree, LinkedList or Array. Best ist eine sehr subjektive Sache. Case in point, size für eine verknüpfte Liste ist nicht erforderlich, um O(1) (und in der Tat ist nicht in mehreren Implementierungen), der vor C++11 standard. Die Begründung ist, dass du einfügen von Elementen sehr viel häufiger als die Abfrage einer Liste der Größe, also warum sollten Sie zahlen den Preis für die Führung size up-to-date-element einfügen?
InformationsquelleAutor aruisdante

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.