Was sind die weniger bekannten, aber nützlichen Datenstrukturen?

Question

Es gibt einige Datenstrukturen, die wirklich nützlich sind, aber den meisten Programmierern unbekannt sind. Welche sind das?

Jeder kennt verknüpfte Listen, binäre Bäume und Hashes, aber was ist mit Listen überspringen y Bloom-Filter zum Beispiel. Ich würde gerne mehr Datenstrukturen kennenlernen, die nicht so häufig vorkommen, aber wissenswert sind, weil sie auf großartigen Ideen beruhen und den Werkzeugkasten eines Programmierers bereichern.

PS: Ich interessiere mich auch für Techniken wie Tanzende Links die sich die Eigenschaften einer gemeinsamen Datenstruktur zunutze machen.

EDIT : Bitte versuchen Sie Links einbeziehen zu Seiten, die die Datenstrukturen genauer beschreiben. Versuchen Sie auch, ein paar Worte zu folgenden Themen hinzuzufügen warum eine Datenstruktur ist cool (als Jonas Kölker bereits hervorgehoben). Versuchen Sie außerdem, Folgendes bereitzustellen eine Datenstruktur pro Antwort . Dadurch können sich die besseren Datenstrukturen allein aufgrund ihrer Stimmen an die Spitze setzen.

Answer 1

Huffman-Bäume - für die Kompression verwendet.

Answer 2

Jeder, der Erfahrung mit 3D-Rendering hat, sollte vertraut sein mit BSP-Bäume . Im Allgemeinen handelt es sich dabei um eine Methode zur Strukturierung einer 3D-Szene, die für das Rendering in Kenntnis der Kamerakoordinaten und -richtung geeignet ist.

Die binäre Raumaufteilung (BSP) ist eine Methode zur rekursiven Unterteilung eines Raumes in konvexe Mengen durch Hyperebenen. Diese Unterteilung führt zu einer Repräsentation der Szene mit Hilfe von einer Baumdatenstruktur, die als BSP-Baum.

Mit anderen Worten, es ist eine Methode der Aufteilung kompliziert geformter Polygone in konvexe Mengen, oder kleinere Polygone, die vollständig aus nicht-reflektierenden Winkeln (Winkel kleiner als 180°). Für eine allgemeinere Beschreibung der Raumaufteilung, siehe Raum Partitionierung.

Ursprünglich wurde dieser Ansatz vorgeschlagen in der 3D-Computergrafik vorgeschlagen, um die die Effizienz des Renderings zu erhöhen. Einige andere Anwendungen sind die Durchführung geometrische Operationen mit Formen (konstruktive Festkörpergeometrie) im CAD, Kollisionserkennung in der Robotik und 3D Computerspielen, und andere Computer Anwendungen, die den Umgang mit komplexen räumlichen Szenen.

Answer 3

Werfen Sie einen Blick auf Fingerbäume vor allem, wenn Sie ein Fan der zuvor erwähnt rein funktionale Datenstrukturen. Sie sind eine funktionale Darstellung persistenter Sequenzen, die den Zugriff auf die Enden in amortisierter konstanter Zeit und die Verkettung und Aufteilung in logarithmischer Zeit zur Größe des kleineren Teils unterstützt.

Gemäß der Originalartikel :

Unsere funktionalen 2-3 Fingerbäume sind ein Beispiel für eine allgemeine Entwurfstechnik, die von Okasaki (1998) eingeführt wurde und implizite rekursive Verlangsamung . Wir haben bereits festgestellt, dass diese Bäume eine Erweiterung seiner impliziten Deque-Struktur sind, wobei Paare durch 2-3 Knoten ersetzt werden, um die für eine effiziente Verkettung und Aufteilung erforderliche Flexibilität zu gewährleisten.

Ein Finger Tree kann parametrisiert werden mit einer Monoid und die Verwendung verschiedener Monoide führt zu unterschiedlichem Verhalten des Baums. Auf diese Weise können Finger Trees andere Datenstrukturen simulieren.

Answer 4

Ringspeicher oder Ringpuffer - u. a. für das Streaming verwendet.

Answer 5

Ich bin überrascht, dass noch niemand Merkle-Bäume erwähnt hat (d.h.. Hash-Bäume ).

Wird in vielen Fällen verwendet (P2P-Programme, digitale Signaturen), in denen Sie den Hash einer ganzen Datei überprüfen wollen, obwohl Sie nur einen Teil der Datei zur Verfügung haben.