Jeśli uważamy drzewo za częściowo uporządkowany zbiór, staje się to szczególnym przypadkiem złączenia-semilattice. W przypadku semilattice złączenia chcemy być w stanie efektywnie obliczyć (unikatową) górną granicę dwóch elementów (mniej więcej). W przypadku drzewa, strukturą danych, która to umożliwiłaby, byłoby przechowywanie dla każdego elementu w odpowiednim węźle wskaźnika do elementu nadrzędnego i miary odległości do elementu głównego. (W rzeczywistości etykietowanie oparte na sortowaniu topologicznym zwykle stosowane do „pomiaru odległości do pierwiastka”, w rzeczywistości wszystko, czego potrzeba, to zgodna częściowa kolejność, którą można skutecznie ocenić).
Każdy skończony łącznik-semilattice może być reprezentowany jako zbiór podzbiorów zbioru skończonego z zawartością w porządku, w którym najmniejsza górna granica jest podana przez sumę zbiorów. Stąd reprezentowanie każdego elementu skończoną liczbą znaczników i obliczenie najmniejszej górnej granicy przez połączenie odpowiednich znaczników byłoby jedną możliwą strukturą danych. (Patrząc na dopełnienie, można zauważyć, że zdefiniowanie najmniejszej górnej granicy jako przecięcia odpowiednich znaczników byłoby również możliwe.) O wiele bardziej powszechna struktura danych polega na użyciu matrycy do przechowywania wszystkich wyników „a <= b ”lub nawet wszystkie wyniki„ join (a, b) ”.
Jednak użycie takiej struktury danych do przedstawienia drzewa byłoby dziwne. Czy istnieją bardziej drzewiaste struktury danych dla połączonych semilattices, które nadal umożliwiają (mniej lub bardziej) wydajne obliczanie (unikalnej) najmniejszej górnej granicy dwóch elementów? (Być może jakiś ukierunkowany wykres acykliczny z dodatkowymi informacjami w węzłach podobny do miary odległości do korzenia drzewa?)
źródło
Odpowiedzi:
Ten blog na temat teorii sieci zawiera przydatny rozdział, który zawiera między innymi „Teorię krat z aplikacjami” Vijaya K. Garga. Rozdział 2 „Reprezentowanie pozycji” opisuje niektóre struktury danych do reprezentowania zestawów i omawia sposób obliczania łączenia (x, y) przy użyciu takiej struktury danych.
Dwie pierwsze omówione struktury danych to reprezentacja listy przyległości grafu redukcji przechodnich (= relacja diagramu Hassego / relacja pokrycia) i grafu zamknięcia przechodniego (= relacja poset). Uwaga o zaletach używania sortowania topologicznego do oznaczania węzłów poprzedza tę dyskusję. Zauważ, że etykiety sortowania topologicznego byłyby wystarczające jako „miara odległości do korzenia”, która była jedną częścią struktury danych dla drzewa w pytaniu.
Inne omawiane reprezentacje to „Reprezentacja szkieletowa”, „Reprezentacja macierzowa” i „Reprezentacja oparta na wymiarze”. „Reprezentacja szkieletowa” jest interesująca i użyteczna, ale oparta na (= dowolnym) rozkładzie łańcucha poety. „Reprezentacja macierzy” może wydawać się trywialna, ale prawdopodobnie jest najlepszą reprezentacją większości praktycznych problemów. „Reprezentacja oparta na wymiarach” reprezentuje zbiór jako podzbiór iloczynu kartezjańskiego rzędów liniowych, ale obliczenie minimalnej reprezentacji tego rodzaju jest trudne NP.
Podsumowując, najbardziej treelike ich reprezentacja to reprezentacja listy przyległości redukcji przechodnich wraz z etykietowaniem węzłów według rodzaju topologicznego (zamiast „miary odległości do pierwiastka”). Jest to właściwie jedna z reprezentacji używanych przez Sage'a (druga to „Reprezentacja macierzy”).
źródło