Jika kita menganggap pohon sebagai set perintah parsial, itu menjadi kasus khusus join-semilattice. Untuk join-semilattice, kami ingin dapat menghitung batas (paling unik) dari dua elemen (lebih atau kurang) secara efisien. Dalam kasus pohon, struktur data yang akan memungkinkan ini adalah untuk menyimpan untuk setiap elemen dalam simpul yang sesuai pointer ke induk dan ukuran jarak ke root. (Sebenarnya, pelabelan berdasarkan jenis topologi biasanya digunakan untuk "ukuran jarak ke root", secara efektif semua yang diperlukan adalah urutan parsial yang kompatibel yang dapat dievaluasi secara efisien).
Setiap join-semilattice terbatas dapat direpresentasikan sebagai himpunan himpunan himpunan himpunan terbatas dengan pengurutan sedemikian rupa sehingga batas paling sedikit diberikan oleh penyatuan himpunan. Oleh karena itu, mewakili setiap elemen dengan jumlah tag yang terbatas, dan menghitung batas yang paling sedikit oleh penyatuan tag yang sesuai akan menjadi salah satu struktur data yang mungkin. (Dengan melihat komplemen, orang melihat bahwa mendefinisikan batas paling atas sebagai persimpangan tag yang sesuai juga dimungkinkan.) Struktur data yang jauh lebih umum adalah dengan hanya menggunakan matriks untuk menyimpan semua hasil "a <= b "atau bahkan semua hasil" gabung (a, b) ".
Namun, menggunakan struktur data seperti itu untuk mewakili pohon akan terasa aneh. Apakah ada lebih banyak struktur data seperti pohon untuk semilattis gabungan, yang masih memungkinkan (lebih atau kurang) perhitungan efisien dari elemen paling tidak terikat (unik) dari dua elemen? (Mungkin semacam grafik asiklik terarah dengan informasi tambahan pada node yang mirip dengan ukuran jarak ke root untuk pohon?)
sumber
Jawaban:
Blogpost ini tentang teori kisi memiliki bagian referensi yang berguna, yang berisi antara lain "Teori Kisi dengan Aplikasi" oleh Vijay K. Garg. Bab 2 "Representing Posets" menjelaskan beberapa struktur data untuk mewakili poset, dan membahas bagaimana cara menghitung join (x, y) menggunakan struktur data seperti itu.
Dua struktur data pertama yang dibahas adalah representasi daftar adjacency dari grafik reduksi transitif (= diagram Hasse / hubungan penutup) dan grafik penutupan transitif (= hubungan poset). Sebuah komentar tentang keuntungan menggunakan semacam topologi untuk memberi label pada node mendahului diskusi tersebut. Perhatikan bahwa label semacam topologi akan cukup baik sebagai "ukuran jarak ke root", yang merupakan salah satu bagian dari struktur data untuk pohon dalam pertanyaan.
Representasi yang dibahas lainnya adalah "Representasi Skeletal", "Representasi Matriks" dan "Representasi Berbasis Dimensi". "Representasi Kerangka" menarik dan bermanfaat, tetapi berdasarkan pada dekomposisi rantai (= apa saja) dari poset. "Representasi Matriks" mungkin tampak sepele, tetapi mungkin merupakan representasi terbaik untuk sebagian besar masalah praktis. "Representasi Berbasis Dimensi" mewakili poset sebagai bagian dari produk Cartesian pesanan linier, tetapi menghitung representasi minimal dari jenis ini adalah NP-hard.
Kesimpulannya, representasi yang paling mirip treel ini adalah representasi daftar adjacency dari reduksi transitif bersama dengan pelabelan node berdasarkan jenis topologis (alih-alih "ukuran jarak ke root"). Ini sebenarnya adalah salah satu representasi yang digunakan oleh Sage (yang lainnya adalah "Representasi Matrix").
sumber