Rotační vzdálenost - Rotation distance

v diskrétní matematika a teoretická informatika, rotační vzdálenost mezi dvěma binární stromy se stejným počtem uzlů je minimální počet rotace stromů potřeboval přenastavit jeden strom do druhého. Kvůli kombinatorické ekvivalenci mezi binárními stromy a triangulacemi konvexních polygonů je rotační vzdálenost ekvivalentní překlopit vzdálenost pro triangulace z konvexní polygony.

Rotační vzdálenost byla poprvé definována Karlem Čulíkem II a Derick Wood v roce 1982.[1] Každé dva n-node binární stromy mají maximálně rotační vzdálenost 2n − 6a některé páry stromů mají přesně tuto vzdálenost. The výpočetní složitost výpočet rotační vzdálenosti není znám.[2]

Definice

Střídání stromů

A binární strom je struktura skládající se ze sady uzlů, z nichž jeden je označen jako kořenový uzel, ve kterém je každý zbývající uzel buď levé dítě nebo správné dítě nějakého jiného uzlu, jeho rodič, a ve kterém následování nadřazených odkazů z libovolného uzlu nakonec vede ke kořenovému uzlu. (V některých zdrojích se zde popsané uzly nazývají „vnitřní uzly“, existuje další sada uzlů zvaná „externí uzly“, každý vnitřní uzel je musí mít přesně dvě děti a každý externí uzel musí mít nulové děti.[1] Zde popsanou verzi lze získat odstraněním všech externích uzlů z takového stromu.)

Pro libovolný uzel X na stromě je a podstrom stejné formy, zakořeněné na X a skládá se ze všech uzlů, které mohou dosáhnout X sledováním nadřazených odkazů. Každý binární strom má pořadí svých uzlů zleva doprava, jeho inorder traversal, získaný rekurzivním procházením levým podstromem (podstrom u levého podřízeného kořene, pokud takový podřízený existuje), poté vypsáním samotného kořene a následným rekurzivním procházením pravým podstromem. binární vyhledávací strom, každý uzel je přidružen k vyhledávacímu klíči a je nutné, aby pořadí zleva doprava bylo konzistentní s pořadím klíčů.[2]

A rotace stromu je operace, která mění strukturu binárního stromu bez změny jeho uspořádání zleva doprava. Několik samovyvažující binární vyhledávací strom datové struktury používají tyto rotace jako primitivní operaci ve svých algoritmech vyvažování. Rotace funguje na dvou uzlech X a y, kde X je rodičem ya restrukturalizuje strom vytvořením y být rodičem X a zaujmout místo X ve stromě. Uvolnit jeden z podřízených odkazů uživatele y a vytvořit prostor pro propojení X jako dítě y, může být při této operaci nutné přemístit také jedno z dětí y stát se dítětem XExistují dvě varianty této operace, a pravá rotace ve kterém y začíná jako levé dítě X a X končí jako správné dítě ya rotace doleva ve kterém y začíná jako správné dítě X a X končí jako levé dítě y.[2]

Jakékoli dva stromy, které mají stejnou sekvenci uzlů zleva doprava, mohou být navzájem transformovány sekvencí rotací. Vzdálenost rotace mezi dvěma stromy je počet rotací v nejkratší možné sekvenci rotací, která tuto transformaci provádí. Lze jej také popsat jako nejkratší vzdálenost dráhy v rotační graf, graf, který má vrchol pro každý binární strom na dané posloupnosti uzlů zleva doprava a hranu pro každou rotaci mezi dvěma stromy.[2] Tento rotační graf je přesně grafem vrcholů a hran an spolupracovník.[3]

Ekvivalence k překlopení vzdálenosti

Flip grafy pětiúhelníku a šestiúhelníku, které odpovídají rotacím tříuzlových a čtyřuzlových binárních stromů

Vzhledem k rodině triangulace nějakého geometrického objektu, a převrátit je operace, která transformuje jednu triangulaci na druhou odstraněním hrany mezi dvěma trojúhelníky a přidáním opačné úhlopříčky k výslednému čtyřúhelníku. Vzdálenost překlopení mezi dvěma triangulacemi je minimální počet překlopení potřebný k transformaci jedné triangulace do jiné. Lze jej také popsat jako nejkratší dráhovou vzdálenost v a flip graf, graf, který má vrchol pro každou triangulaci a hranu pro každé převrácení mezi dvěma triangulacemi. Překlopení a překlopení vzdáleností lze tímto způsobem definovat pro několik různých druhů triangulací, včetně triangulací sad bodů v Euklidovské letadlo, triangulace mnohoúhelníky a triangulace abstraktu rozdělovače.

Mezi triangulacemi dané osoby existuje vzájemná korespondence konvexní mnohoúhelník, s určeným kořenovým okrajem a binárními stromy, přičemž trojúhelníky jsou n-stranné polygony do binárních stromů s n − 2 uzly. V této korespondenci odpovídá každý trojúhelník triangulace uzlu v binárním stromu. Kořenový uzel je trojúhelník, který má určenou kořenovou hranu jako jednu ze svých stran, a dva uzly jsou spojeny jako nadřazený a podřízený ve stromu, když příslušné trojúhelníky sdílejí úhlopříčku v triangulaci. Pod touto korespondencí přesně odpovídají rotace v binárních stromech převrátí odpovídající triangulace. Proto je rotační vzdálenost zapnuta (n − 2)-uzlové stromy přesně odpovídají vzdálenosti překlopení na triangulacích n-stranné konvexní polygony.

Maximální hodnota

Čulík & Wood (1982) definujte "pravou páteř" binárního stromu jako cestu získanou od kořene a následováním správných podřízených odkazů až k dosažení uzlu, který nemá správné podřízené. Pokud má strom vlastnost, že ne všechny uzly patří do pravé páteře, vždy existuje správná rotace, která zvyšuje délku pravé páteře. Protože v tomto případě existuje alespoň jeden uzel X na pravé páteři, která má levé dítě y to není na pravé páteři. Provedení správné rotace X a y dodává y do pravé páteře, aniž byste z ní odstranili jakýkoli jiný uzel. Opakovaným zvětšováním délky pravé páteře libovolné n-node strom může být transformován do jedinečného stromu se stejným pořadí uzlů, ve kterém všechny uzly patří do pravé páteře, v maximálně n − 1 kroky. Vzhledem k tomu, že existují dva stromy se stejným pořadí uzlů, lze jeden transformovat jeden do druhého transformací prvního stromu na strom se všemi uzly na pravé páteři a potom obrácením stejné transformace druhého stromu, celkem maximálně 2n − 2 kroky. Proto, jak Čulík & Wood (1982) prokázáno, že rotační vzdálenost mezi libovolnými dvěma stromy je maximálně 2n − 2.[1]

Uvážením problému z hlediska převrácení konvexních mnohoúhelníků místo rotace stromů, Sleator, Tarjan & Thurston (1988) byli schopni ukázat, že rotační vzdálenost je maximálně 2n − 6. Pokud jde o triangulace konvexních mnohoúhelníků, pravá páteř je posloupnost trojúhelníků dopadajících na pravý koncový bod kořenové hrany a strom, ve kterém všechny vrcholy leží na páteři, odpovídá triangulace ventilátoru pro tento vrchol. Hlavní myšlenkou jejich vylepšení je pokus o převrácení obou daných triangulací na vějířovou triangulaci pro jakýkoli vrchol, nikoli pouze tu pro pravý koncový bod kořenové hrany. Není možné, aby všechny tyto volby poskytly současně nejhorší vzdálenost n − 1 z každé počáteční triangulace, což přináší zlepšení.[2]

Sleator, Tarjan & Thurston (1988) také použil geometrický argument, který ukázal, že pro nekonečně mnoho hodnot n, maximální rotační vzdálenost je přesně 2n − 6. Opět používají interpretaci problému, pokud jde o převrácení triangulací konvexních polygonů, a interpretují počáteční a koncovou triangulaci jako horní a dolní plochu konvexní mnohostěn s konvexním polygonem samotným interpretovaným jako a Hamiltonovský okruh v tomto mnohostěnu. Podle této interpretace lze sekvenci převrácení z jedné triangulace do druhé přeložit do sbírky čtyřstěn které triangulují daný trojrozměrný mnohostěn. Najdou rodinu mnohostěnů s vlastností, která (v trojrozměrném hyperbolická geometrie ) mnohostěny mají velký objem, ale všechny čtyřstěny v nich mají mnohem menší objem, z čehož vyplývá, že v každé triangulaci je zapotřebí mnoho čtyřstěnů. Binární stromy získané převodem horní a dolní sady ploch těchto mnohostěnů zpět na stromy mají vysokou rotační vzdálenost, alespoň 2n − 6.[2]

Následně Pournin (2014) poskytl důkaz, že pro všechny n ≥ 11, maximální rotační vzdálenost je přesně 2n − 6. Pourninův důkaz je kombinatorický a vyhýbá se použití hyperbolické geometrie.[3]

Výpočetní složitost

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Jaká je složitost výpočtu rotační vzdálenosti mezi dvěma stromy?
(více nevyřešených úloh z matematiky)

Kromě definice rotační vzdálenosti Čulík & Wood (1982) požádal o výpočetní složitost výpočtu rotační vzdálenosti mezi dvěma danými stromy. Existence krátkých sekvencí rotace mezi libovolnými dvěma stromy znamená, že testování, zda je rotační vzdálenost nanejvýš k patří do třída složitosti NP, ale není známo, že je NP-kompletní, ani není známo, že je řešitelný v polynomiální čas.

Vzdálenost rotace mezi libovolnými dvěma stromy může být v ekvivalentním pohledu polygonálních triangulací omezena počtem diagonál, které je třeba z jedné triangulace odstranit a nahradit jinými úhlopříčkami, aby se vytvořila druhá triangulace. Může být také horně ohraničen dvojnásobkem tohoto čísla, rozdělením problému na dílčí problémy podél libovolných úhlopříček sdílených mezi oběma triangulacemi a poté aplikováním metody Čulík & Wood (1982) ke každému dílčímu problému. Tato metoda poskytuje aproximační algoritmus za problém s přibližný poměr ze dvou.[4] Podobný přístup rozdělení do dílčích problémů podél sdílených úhlopříček vede k fixovatelný parametr algoritmus pro výpočet vzdálenosti rotace přesně.[5][6]

Určení složitosti výpočtu vzdálenosti rotace přesně bez parametrizace zůstává nevyřešeno a nejlepší algoritmy, které jsou v současné době známé pro daný problém, běží exponenciální čas.[7]

Reference

  1. ^ A b C Čulík, Karel, II; Dřevo, Dericku (1982), „Poznámka k některým opatřením podobnosti stromů“, Dopisy o zpracování informací, 15 (1): 39–42, doi:10.1016/0020-0190(82)90083-7, PAN  0678031
  2. ^ A b C d E F Kráječ, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), „Rotační vzdálenost, triangulace a hyperbolická geometrie“, Journal of the American Mathematical Society, 1 (3): 647–681, doi:10.1090 / S0894-0347-1988-0928904-4, JSTOR  1990951, PAN  0928904
  3. ^ A b Pournin, Lionel (2014), „Průměr asociahedry“, Pokroky v matematice, 259: 13–42, doi:10.1016 / j.aim.2014.02.035, PAN  3197650
  4. ^ Cleary, Sean; St. John, Katherine (2010), „Lineární časová aproximace pro rotační vzdálenost“, Journal of Graph Algorithms and Applications, 14 (2): 385–390, doi:10,7155 / jgaa.00212, PAN  2740180
  5. ^ Cleary, Sean; St. John, Katherine (2009), „Rotační vzdálenost je fixovatelná s pevnými parametry“, Dopisy o zpracování informací, 109 (16): 918–922, arXiv:0903.0197, doi:10.1016 / j.ipl.2009.04.023, PAN  2541971
  6. ^ Lucas, Joan M. (2010), „Vylepšená velikost jádra pro vzdálenost rotace v binárních stromech“, Dopisy o zpracování informací, 110 (12–13): 481–484, doi:10.1016 / j.ipl.2010.04.022, PAN  2667389
  7. ^ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017), „Computing the flip distance between triangulations“, Diskrétní a výpočetní geometrie, 58 (2): 313–344, arXiv:1407.1525, doi:10.1007 / s00454-017-9867-x, PAN  3679938