Unterschied zwischen einer LinkedList und einem binären Suchbaum

https://stackoverflow.com/questions/270080

06-07-2019
|

Frage

Was sind die wichtigsten Unterschiede zwischen einer verknüpften Liste und einem BinarySearchTree? Ist BST nur eine Möglichkeit, eine LinkedList aufrechtzuerhalten? Mein Lehrer sprach über LinkedList und dann BST aber did't sie vergleichen oder nicht sagen, wenn einer über den anderen bevorzugen. Dies ist wahrscheinlich eine dumme Frage, aber ich bin wirklich verwirrt. Ich würde es begrüßen, wenn jemand dies auf einfache Weise klären kann.

Lösung

verlinkte Liste:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

Binary Baum:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

In einer verknüpften Liste, werden die Elemente zusammen durch einen einzigen nächsten Zeiger verknüpft. In einem Binärbaum kann jeder Knoten 0, 1 oder 2 untergeordnete Knoten, wobei (im Fall eines binären Suchbaumes) der Schlüssel des linken Knotens ist kleiner als der Schlüssel des Knotens und der Schlüssel des rechten Knoten ist mehr als der Knoten. Solange der Baum ausgeglichen ist, die searchpath jedes Element ist viel kürzer als die in einer verknüpften Liste.

Suchpfade:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

Durch die größeren Strukturen die durchschnittliche Suchpfad wird signifikant kleiner:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

Andere Tipps

binärer Suchbaum ist ein binärer Baum, bei dem jeder interner Knoten x ein Element speichert, so dass das Element in dem linken Teilbaum von gespeichert x sind kleiner als oder gleich x und Elemente im rechten Teilbaum von x größer oder gleich x .

Nun wird eine verlinkte Liste besteht aus einer Folge von Knoten, von denen jeder beliebigen Wert und einer oder zwei Referenzen zeigt auf den nächsten und / oder vorherigen Knoten.

In der Informatik ein binären Suchbaum (BST) eine binären Baum ist Datenstruktur, die hat die folgenden Eigenschaften:

jeder Knoten (Element in dem Baum) hat einen eindeutigen Wert;
sowohl die linke und rechte Teilbäume müssen auch binäre Suchbäume sein;
der linke Unterbaum eines Knotens enthält nur Werte kleiner als der Wert des Knotens;
die rechte Teilbaum eines Knotens enthält nur Werte größer oder gleich dem Wert des Knotens.

In der Informatik ein verkettete Liste ist eine der grundlegenden Datenstrukturen und kann sein verwendet, um andere Datenstrukturen zu implementieren.

So ein binärer Suchbaum ist ein abstraktes Konzept, das mit einer verknüpften Liste oder ein Array implementiert werden kann. Während die verkettete Liste ist eine grundlegende Datenstruktur.

Ich würde sagen, die Hauptunterschied besteht darin, dass ein binärer Suchbaum sortiert ist. Wenn Sie in einen binären Suchbaum einzufügen, wo diese Elemente am Ende im Speicher gespeichert wird, ist eine Funktion ihres Wertes. Mit einer verknüpften Liste, werden die Elemente in die Liste unabhängig von ihrem Wert blind hinzugefügt.

Gleich können Sie einige Kompromisse: Verkettete Listen Einsetzfolge bewahren und Kuvertieren ist weniger teuer Binäre Suchbäume sind in der Regel auf der Suche schneller

Eine verkettete Liste ist eine laufende Nummer von „Knoten“ miteinander verknüpft, dh:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

Ein binärer Suchbaum verwendet eine ähnliche Knotenstruktur, sondern an den nächsten Knoten zu verknüpfen, es verbindet zwei untergeordnete Knoten:

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
}

spezifische Regeln durch folgende, wenn neue Knoten zu einem BST hinzufügen, können Sie eine Datenstruktur erstellen, die sehr schnell zu durchqueren. Andere Antworten hier haben diese Regeln detailliert, ich wollte nur den Unterschied zwischen Knotenklassen auf Codeebene zeigen.

Es ist wichtig zu beachten, dass, wenn Sie sortieren Daten in ein BST einzufügen, Sie mit einer verknüpften Liste landen werden, und Sie verlieren den Vorteil, einen Baum verwendet wird.

Aus diesem Grund, ein LinkedList ist eine O (N) Traversal-Datenstruktur, während ein BST ist ein O (N) Traversal-Datenstruktur im schlimmsten Fall, und ein O (log N) im besten Fall.

Verknüpfte Listen und BSTs tun haben nicht wirklich viel gemeinsam, außer dass sie beide Datenstrukturen sind, die als Container fungieren. Verknüpfte Listen im Grunde können Sie Elemente effizient an jedem Ort einzusetzen und zu entfernen in der Liste, während die Reihenfolge der Liste. Diese Liste wird mit Zeigern von einem Element zum nächsten implementiert (und oft vorherigen).

binärer Suchbaum auf der anderen Seite ist ein Datum Struktur einer höheren Abstraktions (dh es ist nicht angegeben wie diese intern implementiert ist), die für eine effiziente Suche (dh um ein bestimmtes Element finden Sie nicht bei allen Elementen suchen.

Beachten Sie, dass eine verknüpfte Liste gedacht als eine degenerierte Binärbaum werden kann, das heißt ein Baum, in dem alle Knoten nur ein Kind haben.

Es ist eigentlich ziemlich einfach. Eine verkettete Liste ist nur ein Bündel von Elementen zusammengekettet, in keiner bestimmten Reihenfolge. Sie können sich als wirklich dünn Baum daran denken, die nie Zweige:

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (das letzte ist eine ascii-art Versuch einer abschließenden Null)

Ein binärer Suchbaum unterscheidet sich in zwei Arten: das binäre Teil bedeutet, dass jeder Knoten 2 Kinder, nicht nur eine, und die Suchteil bedeutet, dass diese Kinder sind so angeordnet Suche zu beschleunigen - nur kleinere Gegenstände nach links, und nur größer nach rechts:

9 hat kein linkes Kind und 1, 2 und 12 sind "Blätter" - sie haben keine Verzweigungen

Sinn?

Für die meisten „Lookup“ Arten von Anwendungen ist ein BST besser. Aber nur „eine Liste der Dinge zu halten mit später beschäftigen First-In-First-Out oder Last-In-First-Out“ Arten von Dingen, eine verknüpfte Liste könnte gut funktionieren.

Das Problem mit einer verknüpften Liste innerhalb sie sucht (ob für den Abruf oder einfügen).

Für eine einzelne verkettete Liste, haben Sie an der Spitze zu starten und die Suche nacheinander das gewünschte Element zu finden. Um zu vermeiden, die gesamte Liste zu scannen, müssen Sie zusätzliche Verweise auf Knoten in der Liste, in diesem Fall, es ist nicht mehr eine einfache verknüpfte Liste.

Ein Binärbaum ermöglicht eine schnelle Suche und Einführung von Natur aus sortierte und befahrbar zu sein.

Eine Alternative, die ich in der Vergangenheit erfolgreich verwendet haben, ist ein skiplist. Dies stellt so etwas wie eine verknüpfte Liste, aber mit zusätzlichen Referenzen Suchleistung vergleichbar mit einem binären Baum zu ermöglichen.

Eine verkettete Liste ist nur, dass ... eine Liste. Es ist linear; jeder Knoten einen Verweis auf den nächsten Knoten (und die vorherigen, wenn Sie von einer doppelt verketteten Liste zu sprechen sind). Ein Baum verzweigt --- jeder Knoten einen Verweis auf verschiedene untergeordnete Knoten. Ein binärer Baum ist ein Sonderfall, bei dem jeder Knoten nur zwei Kinder hat. So wird in einer verknüpften Liste, jeder Knoten einen vorherigen Knoten und einen nächsten Knoten, und in einem binären Baum ein Knoten hat ein linkes Kind, rechtes Kind und Eltern.

Diese Beziehungen können bidirektional sein oder unidirektional, je nachdem, wie Sie benötigen, um die Struktur zu durchqueren können.

Sie haben Ähnlichkeiten, aber der Hauptunterschied besteht darin, dass ein binärer Suchbaum ausgelegt ist, eine effiziente Suche nach einem Element oder „Schlüssel“.

Unterstützung

Ein binärer Suchbaum, wie eine doppelt verknüpfte Liste, verweist auf zwei andere Elemente in der Struktur. Wenn jedoch Elemente die Struktur hinzugefügt, und nicht nur sie zum Ende der Liste angehängt wird, wird der binäre Baum neu organisiert, so dass Elemente auf den „linken“ Knoten verbunden sind kleiner als der aktuelle Knoten und Elemente auf den „richtigen“ verlinkt sind Knoten sind größer als der aktuelle Knoten.

In einer einfachen Implementierung wird das neue Element gegenüber dem ersten Elemente der Struktur (die Wurzel des Baumes). Wenn es weniger ist, wird die „linke“ Verzweigung genommen, da sonst der „richtige“ Zweig untersucht wird. Dies setzt sich mit jedem Knoten, bis ein Zweig als leer gefunden wird; das neue Element füllt diese Position.

Mit diesem einfachen Ansatz, wenn Elemente hinzugefügt werden, um, am Ende mit einer verknüpften Liste (mit gleicher Leistung). Verschiedene Algorithmen existieren ein gewisses Maß an Gleichgewicht im Baum zu halten, die durch Knoten neu anordnen. Zum Beispiel, AVL-Bäume machen die meiste Arbeit den Baum so ausgeglichen wie möglich zu halten, die besten Suchzeiten zu geben. Rot-Schwarz-Bäume nicht halten den Baum als ausgeglichen, in etwas langsamer suchen resultierende, aber nicht weniger Arbeit im Durchschnitt als Schlüssel eingefügt oder entfernt werden.

verkettete Liste ist gerade lineare Daten mit benachbarten Knoten miteinander verbunden sind z.B. A-> B-> C. Sie können es als gerade Zaun betrachten.

BST ist eine hierarchische Struktur wie ein Baum mit dem Hauptstamm mit Niederlassungen und die Zweige in-wiederum zu anderen Zweigen verbunden und so weiter. Das „Binary“ Wort bedeutet hier jeder Zweig auf maximal zwei Zweige verbunden ist.

Sie verwenden verknüpfte Liste gerade Daten mit jedem Element nur darstellen zu maximal einem Punkt verbunden ist; während Sie können BST verwenden um ein Element zwei Elemente zu verbinden. Sie können BST verwenden, um ein Daten wie Stammbaum darzustellen, aber das wird n-ary Suchbaum werden, da es kann für jede Person mehr als zwei Kinder sein.

Ein binärer Suchbaum kann in jede Art und Weise implementiert werden, es muss nicht eine verknüpfte Liste verwenden.

Eine verkettete Liste ist einfach eine Struktur, die Knoten und Zeiger / Verweise auf andere Knoten innerhalb eines Knotens enthält. den Kopfknoten einer Liste gegeben, können Sie zu jedem anderen Knoten in einer verknüpften Liste sehen. Doppelt verknüpfte Listen haben zwei Zeiger / Referenzen: der normale Bezug auf den nächsten Knoten, sondern auch einen Verweis auf den vorherigen Knoten. Wenn der letzte Knoten in einer doppelt verketteten Liste des ersten Knotens in der Liste als den nächsten Knoten verweist, und der erste Knoten verweist auf den letzten Knoten als seinen vorherigen Knoten, wird gesagt eine kreisförmige Liste sein.

Ein binärer Suchbaum ist ein Baum, dessen Eingang in zwei auf einem binären Suchvergleichsalgorithmus basierten grob gleiche Hälften aufspaltet. So braucht es nur sehr wenige Suchen ein Element zu finden. wenn man einen Baum mit 1-10 hat zum Beispiel, und man benötigte für drei, zuerst das Element an der Spitze suchen würde prüfen, wahrscheinlich eine 5 oder 6. Drei als wären weniger, so dass nur die erste Hälfte der Baum würde dann überprüft werden. Wenn der nächste Wert 3 ist, haben Sie es, sonst wird ein Vergleich durchgeführt wird, usw., bis er entweder nicht gefunden wird oder seine Daten zurückgegeben werden. So ist der Baum schnell für die Suche, aber nicht nessecarily schnell zum Einfügen oder Löschen. Diese sind sehr grobe Beschreibungen.

verlinkte Liste aus Wikipedia und Binary Search Baum , auch von wikipedia.

Sie sind völlig unterschiedliche Datenstrukturen.

Eine verkettete Liste ist eine Sequenz von Elemente, wobei jedes Element mit dem nächsten verbunden ist, und in dem Fall einer doppelt verknüpften Liste, die vorherigen.

Ein binärer Suchbaum ist etwas ganz anderes. Es hat einen Wurzelknoten, der Wurzelknoten hat zwei untergeordnete Knoten auf, und jedes Kind-Knoten kann bis zu zwei Kinder haben Notizen usw. usw. Es ist eine ziemlich clevere Datenstruktur ist, aber es wäre etwas langweilig sei es hier zu erklären. Schauen Sie sich die Wikipedia Artikel anzu auf sie.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow