Größe
Vergleiche

Operation Durchschnitt Schlechtester Fall

Mehr Informationen über Datenstrukturen

Datenstruktur-Visualisierer

Eine Datenstruktur ist eine Art, Daten so abzulegen, dass die häufigsten Fragen schnell beantwortet sind. Wählen Sie eine von elf klassischen Strukturen, vom Stapel bis zum Rot-Schwarz-Baum, geben Sie einen Wert ein und drücken Sie eine Operation. Jeder Schritt läuft auf dem Bildschirm ab: welcher Knoten verglichen wird, welcher Verweis sich ändert, warum ein Baum rotiert oder ein Wert aufsteigt, mit einem Satz, der benennt, was geschieht. Die Kacheln zählen die Arbeit jeder Operation, und eine Tabelle nennt ihre Laufzeit. Wählen Sie eine Struktur, geben Sie einen Wert ein und drücken Sie eine Operation. Jede Operation läuft Schritt für Schritt ab: Die hervorgehobenen Knoten zeigen, was verglichen, verschoben oder geändert wird, und die Zeile unter dem Bild sagt, was passiert und warum. Mit Zurück, Schritt, Abspielen und Ende gehen Sie die Schritte noch einmal durch. Zufällig füllen und Leeren beginnen von vorn, Rückgängig nimmt eine Operation zurück. Die Kacheln zeigen die Größe, die Höhe von Bäumen, die Arbeit der letzten Operation (Vergleiche, Sondierungen oder verfolgte Elternverweise) und eine Kennzahl, die für die Struktur zählt; die Tabelle nennt die Laufzeit jeder Operation.

Wie es funktioniert

  1. Wählen Sie eine Struktur, etwa einen binären Suchbaum, eine Hashtabelle oder einen Trie. Sie beginnt mit zufälligem Inhalt; Zufällig füllen und Leeren fangen neu an.
  2. Geben Sie einen Wert ein und drücken Sie eine Operation: Push, Einreihen, Einfügen, Löschen, Suchen, einen Durchlauf, Union oder Find. Die Schritte laufen von selbst ab; Zurück, Schritt, Abspielen und Ende gehen sie noch einmal durch.
  3. Lesen Sie in der Zeile unter dem Bild, was jeder Schritt tut, beobachten Sie in den Kacheln Größe, Höhe und Arbeit der letzten Operation und vergleichen Sie die Laufzeiten in der Tabelle.

Listen, Stapel und Warteschlangen

Die einfachsten Strukturen halten Elemente in einer Reihe. Ein Stapel arbeitet nur an einem Ende, das zuletzt hineingelegte Element kommt also zuerst heraus, wie bei einem Tellerstapel; eine Warteschlange fügt hinten an und entnimmt vorn, wie eine Schlange am Schalter. Die Warteschlange hier liegt in einem Ringpuffer: Anfang und Ende wandern um ein festes Array und laufen über dessen Ende hinaus wieder vorn weiter, und wenn er voll ist, werden die Elemente in einen doppelt so großen kopiert. Eine verkettete Liste verbindet Knoten über Zeiger, Einfügen am Kopf kostet also nichts, aber um das Ende oder einen Index zu finden, muss man den Verweisen einzeln folgen.

Bäume, Heaps, Hashtabellen und Mengen

Ein binärer Suchbaum hält kleinere Werte links und größere rechts, sodass eine Suche die Kandidaten bei jedem Schritt halbiert, solange der Baum buschig bleibt. AVL- und Rot-Schwarz-Bäume sorgen dafür, mit Rotationen, die Sie beobachten können und die nach ihrem Fall benannt sind. Ein Heap hält nur den kleinsten oder größten Wert oben, mehr braucht eine Prioritätswarteschlange nicht. Eine Hashtabelle springt direkt zu einem aus dem Schlüssel berechneten Bucket und muss mit Kollisionen umgehen; ein Trie teilt die Präfixe von Wörtern; Union-Find sagt in nahezu konstanter Zeit, ob zwei Elemente zur selben Menge gehören.

Häufig gestellte Fragen

Welche Datenstruktur sollte ich verwenden?

Das hängt von den Fragen ab, die Sie am häufigsten stellen. Ein Stapel oder eine Warteschlange, wenn Elemente in der Reihenfolge ihres Eintreffens oder umgekehrt bearbeitet werden; eine Hashtabelle, um einen Schlüssel nachzuschlagen; ein balancierter Suchbaum wie ein AVL- oder Rot-Schwarz-Baum, wenn Sie die Schlüssel auch sortiert oder den nächstgelegenen Schlüssel brauchen; ein Heap, wenn Sie immer nur das kleinste oder größte Element brauchen; ein Trie für Wörter und Präfixe; Union-Find, um Gruppen zu verfolgen, die verschmelzen.

Was ist der Unterschied zwischen einem AVL-Baum und einem Rot-Schwarz-Baum?

Beide halten einen binären Suchbaum flach, sodass jedes Suchen, Einfügen und Löschen Zeit proportional zu log n braucht. Ein AVL-Baum ist strenger balanciert, die Höhen der beiden Seiten jedes Knotens liegen höchstens eins auseinander, daher sind Suchen etwas schneller. Ein Rot-Schwarz-Baum erlaubt mehr Spielraum und braucht beim Ändern weniger Rotationen, weshalb viele Standardbibliotheken ihn für ihre sortierten Maps und Sets verwenden.

Warum kann eine Hashtabelle im schlechtesten Fall langsam sein?

Landen viele Schlüssel im selben Bucket, muss eine Suche sie einzeln prüfen, genau wie bei einer Liste. Eine gute Hashfunktion verteilt die Schlüssel gleichmäßig, und die Tabelle wächst, bevor sie zu voll wird, sodass eine Suche im Durchschnitt konstante Zeit braucht. Probieren Sie eine Tabellengröße von 10 mit Zahlen, die auf dieselbe Ziffer enden, oder Wörter, die Anagramme voneinander sind, und sehen Sie, wie sich Kollisionen häufen.

Was bedeuten die Zahlen neben den AVL-Knoten?

Es sind Balancefaktoren: die Höhe des linken Teilbaums eines Knotens minus die Höhe seines rechten Teilbaums. In einem AVL-Baum muss jeder Balancefaktor −1, 0 oder +1 sein. Wird einer durch Einfügen oder Löschen +2 oder −2, rotiert der Baum an diesem Knoten; der Fall (LL, RR, LR oder RL) sagt, wohin die zusätzliche Höhe neigt, und entscheidet zwischen einer und zwei Rotationen.

Wird etwas an einen Server gesendet?

Nein. Jede Operation läuft in Ihrem Browser, und der Inhalt jeder Struktur wird im lokalen Speicher dieses Browsers gesichert.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor