Určiť štrukturálnu ekvivalenciu BST so štandardným traversal - algoritmus, vyhľadávanie, dátové štruktúry, strom, katalánsky

Je možné rozhodnúť o štrukturálnejrovnocennosť dvoch binárnych vyhľadávacích stromov len s výsledkami prechodov, pred objednávkou, v poradí a po objednávke. Predpokladajme, že mám len výsledné súbory všetkých prechodov. Viem, že len na traverzu, nemôžete pomôcť, ale nemohol som si predstaviť iné výsledky. Chápem pomoc BFS. Chcem vedieť o prechodoch a objednávkach. A ak je to možné, uverejnite v nej odkazy.

odpovede:

Odpoveď je : môžete obnoviť binárny strom vyhľadávania z jeho predbežného traverzu.

Nie som si istý, aké je vaše matematické pozadie, takže sa opýtajte, či potrebujete ďalšie vysvetlenie.

Pre jednoduchosť, predpokladám, že uzol je označený číslom 1,2 ... n, kde n je počet uzlov. Potom predbežná traverzia stromu t dáva vám permutáciu [n] = {1,2,...,n} ktoré majú určitú vlastnosť: zakaždým, keď máte písmeno b vo svojej permutácii, nemôžete nájsť dva po sebe idúce listy ca po b v permutácii tak, že a<b<c, Takáto permutacia sa hovorí vyhnúť sa vzor b-ac (stojan pre ľubovoľný počet písmen).

Napríklad 4 2 1 3 zabraňuje b-ac, zatiaľ čo 3 1 4 2 neznamená, že 3 - 4 2.

Toto je vlastne ekvivalent: Permutácia je predčítanie čítania stromu, ak sa vyhneme b-ac.

Je známe, že existuje toľko stromov veľkosti nako permutačné vyhnúť b-ac, takže je to bijekcia. Ich počet je známy ako katalánske číslo. Pravdepodobne to môžete nájsť ako cvičenie knihy Stanleyho "enumerative combinatorics".

Tu je viac algoritmické vysvetlenie:

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that
- for 1<=j<=i then l[j] < b and
- for i<j<=n  then l[j] > b
if there isn"t exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

Ako dôsledok

Dva binárne vyhľadávacie stromy sú rovnaké, ak a iba ak majú rovnakú predbežnú traverzu

Má pre vás zmysel?

Ďalšie odkazy

• Katalánske číslo v on-line encyklopéde Integer Sequences
• Anders Claesson Generalized Avoidance, European Journal of Combinatorics 22 (2001) 961-971

V BST môžete ísť vľavo dieťa (L), pravé dieťa(R) alebo nahor (U). Prechod môže potom byť opísaný reťazcom nad {L, R, U}, napr. "LLURUURLURUU". Pre BST s ekvivalentnými štruktúrami budú tieto reťazce identické.