M-ary strom - M-ary tree
v teorie grafů, an m-ary strom (také známý jako k-ary nebo k-způsob strom) je zakořeněný strom ve kterém každý uzel nemá více než m děti. A binární strom je zvláštní případ, kdym = 2a ternární strom je další případ s m = 3 což omezuje jeho děti na tři.
Typy m- střídavé stromy
- A úplný m-ary strom je m-ary strom, kde v každé úrovni má každý uzel buď 0 nebo m děti.
- A kompletní m-ary strom je m-ary strom, který je maximálně prostorově efektivní. Musí být zcela vyplněn na všech úrovních kromě poslední úrovně. Pokud však poslední úroveň není úplná, musí být všechny uzly stromu „co nejvíce vlevo“.[1]
- A perfektní m-ary strom je plný[1] m-ary strom, ve kterém všechny listové uzly jsou ve stejné hloubce.[2]
Vlastnosti m- střídavé stromy
- Pro m- strom s výškou h, horní hranice pro maximální počet listů je .
- Výška h z m-ary strom nezahrnuje kořenový uzel se stromem obsahujícím pouze kořenový uzel s výškou 0.
- Výška stromu se rovná maximální hloubce D kteréhokoli uzlu ve stromu.
- Celkový počet uzlů v perfektní m-ary strom je , zatímco výška h je
- Podle definice Big-Ω je maximální hloubka
- Výška kompletu m-aryní strom s n uzly je .
- Celkový počet možných m-aryní strom s n uzly je (což je Katalánské číslo ) [3].
Traversální metody pro m-ary
Traversing a m-ary strom je velmi podobný binárnímu stromu. Traversal předobjednávky jde do nadřazeného, levého podstromu a pravého podstromu a pro procházení post-orderu jde do levého podstromu, pravého podstromu a nadřazeného uzlu. Pro procházení v pořadí, protože pro každý uzel jsou více než dvě děti m> 2, je třeba definovat pojem vlevo, odjet a že jo podstromy. Jednou běžnou metodou pro založení levého / pravého podstromu je rozdělení seznamu podřízených uzlů do dvou skupin. Definováním objednávky na m děti uzlu, první uzly by tvořily levý podstrom a uzly by tvořily pravý podstrom.
Převést a m-ary strom na binární strom
Použití pole pro reprezentaci a m-strom je neefektivní, protože většina uzlů v praktických aplikacích obsahuje méně než m děti. Výsledkem je, že tato skutečnost vede k řídkému poli s velkým nevyužitým prostorem v paměti. Převod libovolného m-Ary strom na binární strom by jen zvýšil výšku stromu o konstantní faktor a neovlivnil by celkovou nejhorší časovou složitost. Jinými slovy, od té doby .
Nejprve spojíme všechny bezprostřední podřízené uzly daného nadřazeného uzlu dohromady, abychom vytvořili seznam odkazů. Poté ponecháme odkaz z rodiče na první (tj. Úplně vlevo) dítě a odstraníme všechny ostatní odkazy na ostatní děti. Tento postup opakujeme pro všechny děti (pokud mají nějaké děti), dokud nezpracujeme všechny vnitřní uzly a strom neotočíme o 45 stupňů ve směru hodinových ručiček. Získaný strom je požadovaný binární strom získaný z daného m-ary strom.
Způsoby skladování m- střídavé stromy
Pole
m-ary stromy mohou být také uloženy v pořadí v šíři jako implicitní datová struktura v pole, a pokud je strom kompletní m-ary strom, tato metoda neztrácí žádné místo. V tomto kompaktním uspořádání, pokud má uzel index i, své C-té dítě v rozsahu {1, ...,m} se nachází v indexu , zatímco jeho nadřazený prvek (pokud existuje) se nachází v indexu (za předpokladu, že kořen má index nula, což znamená pole založené na 0). Tato metoda těží z kompaktnějšího úložiště a lepšího referenční lokalita, zejména při předobjednávce. Prostorová složitost této metody je .
Na základě ukazatele
Každý uzel by měl vnitřní pole pro ukládání ukazatelů na každý z nich děti:
Ve srovnání s implementací založenou na poli má tato implementační metoda vynikající prostorovou složitost .
Výčet m-ary
Výpis všech možných m-ary stromy jsou užitečné v mnoha oborech jako způsob ověřování hypotéz nebo teorií. Správná reprezentace m-ary stromové procesy mohou značně zjednodušit proces generování. Lze sestrojit a reprezentace bitové sekvence pomocí hloubkového vyhledávání a m-aryní strom s n uzly indikující přítomnost uzlu v daném indexu pomocí binárních hodnot. Například bitová sekvence x = 1110000100010001000 představuje tříletý strom s n = 6 uzly, jak je znázorněno níže.
Problém s touto reprezentací spočívá v tom, že výpis všech bitových řetězců v lexikografickém pořadí by znamenal, že dva po sobě následující řetězce mohou představovat dva stromy, které jsou lexikograficky velmi odlišné. Proto by výčet přes binární řetězce nutně nevyústil v uspořádanou generaci všech m-ary.[4] Lepší reprezentace je založena na celočíselném řetězci, který označuje počet nul mezi po sobě jdoucími, známými jako Jednoduchá nulová sekvence. je jednoduchá nulová sekvence odpovídající bitové sekvenci kde j je počet nul potřebných na konci sekvence, aby řetězec měl odpovídající délku. Například, je jednoduchá reprezentace nulové sekvence výše uvedeného obrázku. Kompaktnější zobrazení 00433 je , který se nazývá nulová sekvence, které nemohou duplikovat báze. Tato nová reprezentace umožňuje sestavit další platnou sekvenci v Jednoduchá nulová sekvence je platná, pokud
Níže uvedená tabulka zobrazuje seznam všech platných jednoduchých nulových sekvencí všech 3-ary stromy se 4 uzly:
Počínaje od pravého dolního rohu tabulky (tj. „000“) je a páteřní šablona který určuje generování možných uspořádaných stromů počínaje od „000“ do „006“. Páteřní šablona pro tuto skupinu („00X“) je znázorněna níže, kde je na pozice označené „x“ přidán další uzel.
Jakmile jeden vyčerpá všechny možné pozice v páteřní šabloně, bude vytvořena nová šablona posunutím třetího uzlu o jednu pozici doprava, jak je znázorněno níže, a dojde ke stejnému výčtu, dokud nebudou vyčerpány všechny možné polohy označené „X“.
Vracíme se k tabulce výčtu všech m-ary stromy, kde a , můžeme snadno pozorovat zdánlivý skok z „006“ na „010“, který lze vysvětlit triviálně algoritmickým způsobem, jak je znázorněno níže:
Pseudokód pro tento výčet je uveden níže[4]:
Postup DALŠÍ() -li pro všechny i pak hotovo jiný -li ipak skončit, pokud pro skončit, pokudkonec
Loopless výčet
Generační algoritmus, který trvá nejhorší čas se nazývá loopless, protože časová složitost nemůže zahrnovat smyčku nebo rekurzi. Loopless výčet m-ary trees is said to be loopless if after initialization, it generates successive tree objects in . Pro daný a m-ary strom T s je jedním z jeho uzlů a své dítě, a rotace doleva na se děje výrobou kořenový uzel a tvorba a všechny jeho podstromy dítětem , navíc přiřadíme opustil většinu dětí z na a to pravé dítě zůstane k němu připojený, zatímco je povýšen na root, jak je uvedeno níže:
Převeďte strom stromu na levý strom pro : pro : zatímco t dítě uzlu v hloubce : Rotace L-t v uzlech v hloubce i skončit chvíli konec pro konec pro
A doprava-t rotace na d je inverzní k této operaci. The levý řetěz z T je posloupnost uzly takové, že je kořen a všechny uzly kromě mít jedno dítě připojené k jejich levici nejvíce (tj. ) ukazatel. Žádný m-strom může být přeměněn na levý řetěz strom používající posloupnost konečných rotace vlevo t pro t z 2 na m. Konkrétně to lze provést provedením rotací vlevo t na každém uzlu až do všech podstrom stát nula v každé hloubce. Poté se v hloubce provede posloupnost počtu rotací vlevo t i označeno definuje a kódové slovo a m-strom, který lze obnovit provedením stejné sekvence pravostranných rotací.
Nech n-tice představují počet L-2 rotace, L-3 rotace, ..., L-m rotace, ke kterým došlo v kořenovém adresáři (tj. i = 1). je počet L-t rotace potřebné v hloubce i.
Zachycení počtu otáček doleva v každé hloubce je způsob kódování m-ary strom. Výčet všech možných legálních kódování by nám tedy pomohl vygenerovat všechny m-aryary stromy pro daný m a n. Ale ne všechny sekvence m nezáporná celá čísla představují platný strom m. Posloupnost nezáporná celá čísla je platná reprezentace a m-ary strom právě tehdy [5]
Lexikograficky nejmenší zastoupení kódového slova a m-ary s n uzly jsou všechny nuly a největší je n-1 následované m-1 nula vpravo.
Inicializace c [i] na nulu pro všechna i od 1 do p [i] nastaveno na pro i od 1 do n Podmínka ukončení Ukončete, když c [1] = n-1Postup DALŠÍ [5] -li pak skončit, pokud -li pak jiný skončit, pokudkonec
aplikace
Jednou z aplikací m-ary strom vytváří slovník pro validaci přijatelných řetězců. Abychom to mohli udělat, nechme to m být roven počtu platných abeced (např. počet písmen znaku anglická abeceda ) s kořenem stromu představujícím výchozí bod. Podobně může mít každé z dětí až m děti představující další možný znak v řetězci. Znaky podél cest tak mohou představovat platné klíče označením koncového znaku klíčů jako „koncový uzel“. Například v příkladu níže „at“ a „a“ jsou platné řetězce kláves s „t“ a „d“ označenými jako terminální uzly. Koncové uzly mohou ukládat další informace, které mají být přidruženy k danému klíči. Existují podobné způsoby, jak takový slovník vytvořit B-strom, Octree a / nebo trie.
Viz také
Reference
- ^ A b "Objednané stromy". Citováno 19. listopadu 2012.
- ^ Black, Paul E. (20. dubna 2011). "dokonalý strom K-Ary". Americký národní institut pro standardy a technologie. Citováno 10. října 2011.
- ^ Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2. vydání). AIP.
- ^ A b Baronaigien, dodávka Dominique Roelants (2000). "Generování K-ary stromů bez smyček". Journal of Algorithms. 35 (1): 100–107. doi:10.1006 / jagm.1999.1073.
- ^ A b Korsh, James F (1994). "Loopless generace k-ary stromových sekvencí". Dopisy o zpracování informací. Elsevier. 52 (5): 243–247. doi:10.1016/0020-0190(94)00149-9.
- Storer, James A. (2001). Úvod do datových struktur a algoritmů. Birkhäuser Boston. ISBN 3-7643-4253-6.