Wenn wir einen Baum als eine teilweise geordnete Menge betrachten, wird er zu einem Sonderfall eines Join-Semilattice. Für ein Join-Semilattice möchten wir in der Lage sein, die (eindeutige) kleinste Obergrenze von zwei Elementen (mehr oder weniger) effizient zu berechnen. Im Fall eines Baums würde eine Datenstruktur, die dies ermöglichen würde, für jedes Element in dem entsprechenden Knoten einen Zeiger auf das übergeordnete Element und ein Abstandsmaß zur Wurzel speichern. (Tatsächlich ist eine Kennzeichnung basierend auf der topologischen Sortierung, die normalerweise für "ein Abstandsmaß zur Wurzel" verwendet wird, praktisch alles, was benötigt wird, eine kompatible Teilreihenfolge, die effizient ausgewertet werden kann.)
Jedes endliche Verknüpfungshalbgitter kann als eine Menge von Teilmengen einer endlichen Menge mit Einschluss in einer solchen Reihenfolge dargestellt werden, dass die kleinste Obergrenze durch die Vereinigung der Mengen gegeben ist. Daher wäre es eine mögliche Datenstruktur, jedes Element durch eine endliche Anzahl von Tags darzustellen und die kleinste Obergrenze durch die Vereinigung der entsprechenden Tags zu berechnen. (Wenn man sich das Komplement anschaut, sieht man, dass es auch möglich wäre, die kleinste Obergrenze als Schnittmenge der entsprechenden Tags zu definieren.) Eine weitaus häufigere Datenstruktur besteht darin, einfach eine Matrix zu verwenden, um alle Ergebnisse von "a <=" zu speichern b "oder sogar alle Ergebnisse von" join (a, b) ".
Eine solche Datenstruktur zur Darstellung eines Baums zu verwenden, wäre jedoch etwas seltsam. Gibt es mehr baumartige Datenstrukturen für Join-Semilattices, die noch eine (mehr oder weniger) effiziente Berechnung der (eindeutigen) kleinsten Obergrenze zweier Elemente ermöglichen? (Vielleicht eine Art gerichteter azyklischer Graph mit zusätzlichen Informationen in den Knoten, ähnlich dem Abstandsmaß zur Wurzel für den Baum?)
quelle
Antworten:
Dieser Blogpost zur Gittertheorie enthält einen nützlichen Referenzteil, der unter anderem "Gittertheorie mit Anwendungen" von Vijay K. Garg enthält. Kapitel 2 "Darstellen von Posets" beschreibt einige Datenstrukturen zum Darstellen von Posets und erläutert, wie Join (x, y) unter Verwendung einer solchen Datenstruktur berechnet wird.
Die ersten beiden diskutierten Datenstrukturen sind die Darstellung der Adjazenzliste des transitiven Reduktionsgraphen (= Hasse-Diagramm / Deckungsbeziehung) und des transitiven Abschlussgraphen (= Poset-Beziehung). Eine Bemerkung zu den Vorteilen der Verwendung einer topologischen Sortierung zum Beschriften der Knoten geht dieser Diskussion voraus. Beachten Sie, dass die Beschriftungen topologischer Art als "Abstandsmaß zur Wurzel" gut genug wären, was ein Teil der Datenstruktur für einen Baum in der Frage war.
Die anderen diskutierten Darstellungen sind "Skelettdarstellung", "Matrixdarstellung" und "Dimensionsbasierte Darstellung". Die "Skelettdarstellung" ist interessant und nützlich, basiert jedoch auf einer (= beliebigen) Kettenzerlegung des Posets. Die "Matrixrepräsentation" mag trivial erscheinen, ist aber wahrscheinlich die beste Repräsentation für die meisten praktischen Probleme. Die "Dimensionsbasierte Darstellung" repräsentiert das Poset als Teilmenge des kartesischen Produkts linearer Ordnungen, aber die Berechnung der minimalen Darstellung dieser Art ist NP-schwer.
Zusammenfassend ist die baumartigste Darstellung davon die Adjazenzlistendarstellung der transitiven Reduktion zusammen mit einer Kennzeichnung der Knoten durch eine topologische Sortierung (anstelle eines "Abstandsmaßes zur Wurzel"). Dies ist tatsächlich eine der von Sage verwendeten Darstellungen (die andere ist die "Matrix-Darstellung").
quelle