Struktur data untuk set pohon.

Mencoba memungkinkan untuk penyimpanan efisien daftar elemen. Awalan dibagikan sehingga hemat ruang.

Saya mencari cara yang sama untuk menyimpan pohon secara efisien. Saya ingin dapat memeriksa keanggotaan dan menambahkan elemen, mengetahui apakah pohon yang diberikan adalah subtree dari beberapa pohon yang disimpan atau jika ada pohon yang disimpan menjadi subtree dari pohon yang diberikan juga diinginkan.

Saya biasanya akan menyimpan sekitar 500 pohon biner tidak seimbang dengan tinggi kurang dari 50.

EDIT

Aplikasi saya adalah semacam pemeriksa model menggunakan semacam memoisasi. Bayangkan saya memiliki keadaan dan rumus berikut: f = ϕ dan g = ( ϕ ∨ ψ ) dengan ϕ menjadi subformula yang kompleks, dan bayangkan saya pertama-tama ingin tahu apakah f berlaku dalam s . Saya memeriksa apakah ϕ berlaku dan setelah proses yang panjang saya mendapatkan bahwa ini adalah masalahnya. Sekarang, saya ingin tahu apakah g memegang s . Saya ingin mengingat fakta bahwa f memegang dan memperhatikan bahwa g ⇒ $s$$f = \phi$$g = (\phi \vee \psi)$$\phi$$f$$s$$\phi$$g$$s$$f$$g \Rightarrow f$sehingga saya dapat memperoleh di s hampir seketika. Sebaliknya, jika saya telah membuktikan bahwa g tidak menahan t , maka saya ingin mengatakan bahwa f tidak menahan t hampir secara instan.$g$$s$
$g$$t$$f$$t$

Kita dapat membuat urutan parsial pada rumus, dan memiliki iff g ⇒ f . Untuk setiap negara s , kita menyimpan dua set formula; L ( s ) menyimpan formula maksimal yang tahan dan l ( s ) menyimpan formula minimal yang tidak tahan. Sekarang diberi status s dan rumus g , saya dapat melihat apakah ∃ f ∈ L ( s ) , f ⇒ g , atau jika ∃ f ∈ l ( s $g \geq f$$g \Rightarrow f$$s$$L(s)$$l(s)$$s$$g$$\exists f \in L(s), f \Rightarrow g$ dalam hal ini saya selesai dan saya tahu langsung apakah g berlaku di s .$\exists f \in l(s), g \Rightarrow f$$g$$s$

Saat ini, dan l diimplementasikan sebagai daftar dan ini jelas tidak optimal karena saya perlu mengulangi semua formula yang disimpan secara individual. Jika formula saya adalah urutan, dan jika urutan parsial "adalah awalan" maka trie bisa membuktikan lebih cepat. Sayangnya formula saya memiliki struktur seperti pohon berdasarkan ¬ , ∧ , operator modal, dan proposisi atom.$L$$l$$\neg, \wedge$

Seperti @Raphael dan @Jack tunjukkan, saya bisa mengurutkan pohon, tapi saya khawatir itu tidak akan menyelesaikan masalah karena urutan parsial yang saya tertarik tidak akan sesuai dengan "adalah awalan".

Anda mungkin ingin mencoba g-mencoba . Ini pada dasarnya adalah struktur data yang Anda cari, tetapi dirancang untuk digunakan dengan grafik umum, bukan hanya pohon. Karena itu, saya tidak yakin bahwa g-mencoba memiliki jaminan teoritis yang baik - saya pikir mereka menggunakan algoritma kanonisasi grafik sebagai subrutin - tetapi dalam praktiknya mereka tampaknya bekerja dengan baik.

(Jangan takut bahwa kertas yang ditautkan adalah tentang "motif jaringan dalam jaringan biologis": g-trie adalah struktur data abstrak yang sangat baik untuk grafik.)

Bentuk khusus ini adalah ketekunan : Lihat kertas Membuat Struktur Data Persisten oleh Driscoll, Sarnak, Sleator, & Tarjan, dan Lokasi Titik Planar Menggunakan Pohon Pencarian Persisten oleh Sarnak & Tarjan, yang menyimpan keluarga pohon terkait.

Ini terdengar sedikit seperti hutan ( disjoint-set forest ) ...

Ini mengamortisasi biaya penyisipan melalui teknik yang disebut union by rank dan operasi pencarian menggunakan kompresi jalur . Saya tahu ada juga versi yang terus - menerus dari struktur ini yang dikembangkan oleh Sylvain Conchon dan Jean-Christophe Filliâtre tetapi saya tidak tahu apakah ini sama dengan yang disebutkan Jack ...

Bagaimana dengan automata pohon minimal ?

Dalam "Purely Functional Data Structures" (1998), Chris Okasaki mengusulkan percobaan pohon biner menggunakan agregasi tipe (10.3.2).

Saya tidak tahu apakah ini segera membantu; solusi yang diberikan mungkin tidak dapat diimplementasikan secara langsung.

Dalam istilah programmer: Jika Anda membuat pohon dari sub-ekspresi umum / pohon / DAG, Anda akan memiliki model ringkas yang bagus. Jadi Grafik Acyclic Disutradarai. Maka satu pohon saja sudah cukup.

Pohon kelas publik {Operasi string; Sub pohon [];

public int compareTo(Tree rhs) {
    if (rhs == null) return false;
    int cmp = operation.compareTo(rhs.operation);
    if (cmp == 0) {
        cmp = Arrays.compareTo(subtrees, rhs.subtrees);
    }
    return cmp;
}

...}

Peta commonSubExpressions = HashMap baru ();

Tree get (String expressionSyntax) {Tree t = new Tree (); t.operasi = ...; t.subtrees = ... panggilan rekursif untuk mendapatkan subekspresi; Tree t2 = commonSubExpressions.get (t); if (t2 == null) {t2 = t; commonSubExpressions.put (t2, t2); } return t2; }}