m -ärt träd

Ett exempel på ett m-ärt träd med m=5

I grafteorin är ett m -ärt träd (även känt som n -ary , k -ary eller k -way tree) ett rotat träd där varje nod inte har fler än m barn. Ett binärt träd är specialfallet där m = 2, och ett ternärt träd är ett annat fall med m = 3 som begränsar dess barn till tre.

Typer av m -ära träd

• Ett fullt m -ärt träd är ett m -ärt träd där inom varje nivå varje nod har antingen 0 eller m barn.
• Ett komplett m -ärt träd är ett m -ärt träd som är maximalt utrymmeseffektivt. Den måste fyllas helt på alla nivåer utom den sista nivån. Men om den sista nivån inte är klar måste alla noder i trädet vara "så långt till vänster som möjligt".
• Ett perfekt m -ärt träd är ett fullt m -ärt träd där alla lövnoder är på samma djup.

Egenskaper hos m -ära träd

• För ett m -ärt träd med höjden h är den övre gränsen för det maximala antalet löv $m^{h}$ .
• Höjden h för ett m -ärt träd inkluderar inte rotnoden, med ett träd som bara innehåller en rotnod som har en höjd av 0.
• Höjden på ett träd är lika med det maximala djupet D för någon nod i trädet.
• Det totala antalet noder $N$ i ett perfekt m -ärt träd är ${\textstyle \sum _{i=0}^{h} m^{i}={\frac {m^{h+1}-1}{m-1}}} ,$ medan höjden h är
  $${\begin{aligned}&{\frac {m^{h+1}-1}{m-1}}\geq N>{\frac {m^{h}-1}{m-1 }}\\[8pt]&m^{h+1}\geq (m-1)\cdot N+1>m^{h}\\[8pt]&h+1\geq \log _{m}\left ((m-1)\cdot N+1\right)>h\\[8pt]&h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right \rceil .\end{aligned}}$$
  Enligt definitionen av Big-Ω, det maximala djupet
  $$D=h\geq \ vänster\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m)$$
• Höjden på ett komplett m -ärt träd med n noder är ${\textstil \lfloor \log _{m}((m-1)\cdot n)\rfloor }$ .
• Det totala antalet möjliga m -ära träd med n noder är ${\textstil C_{n}={\frac {1}{(m- 1)n+1}}\cdot {\binom {m\cdot n}{n}}}$ (som är ett katalanskt tal ).

Traverseringsmetoder för maryträd

Huvudartikel: traversering av träd

Att korsa ett m -ärt träd är mycket likt binärt trädtraversering. Förbeställningsgenomgången går till det överordnade, vänstra underträdet och det högra underträdet, och för att passera efterbeställningen går det via vänster underträd, höger underträd och överordnad nod. För att korsa i ordning, eftersom det finns fler än två barn per nod för m > 2 , måste man definiera begreppet vänster och höger underträd. En vanlig metod för att upprätta vänster/höger underträd är att dela upp listan med barnnoder i två grupper. Genom att definiera en ordning på de m barnen i en nod, den första ${\textstil \{1,\dots ,\lfloor {\frac {m}{2}}\rfloor \} }$ noder skulle utgöra det vänstra underträdet och ${\textstyle \{\lceil {\frac {m}{2}}\rceil ,\dots ,m\}}$ noder skulle utgöra den högra underträd.

Konvertera ett m -ärt träd till binärt träd

Ett exempel på konvertering av ett m-ärt träd till ett binärt träd. m=6

Att använda en array för att representera ett mary -träd är ineffektivt, eftersom de flesta av noderna i praktiska tillämpningar innehåller mindre än m barn. Som ett resultat leder detta faktum till en gles array med stort oanvänt utrymme i minnet. Att konvertera ett godtyckligt mary- träd till ett binärt träd skulle bara öka höjden på trädet med en konstant faktor och skulle inte påverka den totala tidskomplexiteten i värsta fall. Med andra ord, ${\textstyle O(\log _{m}n)\equiv O(\log _{2}n)}$ sedan ${\textstyle \log _{2}m\cdot \log _{m}n={\frac {\log m}{\log 2}}\cdot {\frac {\log n}{\log m}}=\log _{2}n}$ .

Först länkar vi alla omedelbara barnnoder för en given överordnad nod för att bilda en länklista. Sedan behåller vi länken från föräldern till det första (dvs. det längst till vänster) barnet och tar bort alla andra länkar till resten av barnen. Vi upprepar denna process för alla barn (om de har några barn) tills vi har bearbetat alla interna noder och roterar trädet 45 grader medurs. Det erhållna trädet är det önskade binära trädet som erhålls från det givna m -ära trädet.

Metoder för förvaring av m -ära träd

Matriser

Ett exempel på att lagra ett m-ärt träd med m=3 i en array

m -ära träd kan också lagras i bredd-första ordning som en implicit datastruktur i arrayer , och om trädet är ett komplett m -ärt träd, slösar denna metod inget utrymme. I detta kompakta arrangemang, om en nod har ett index i , hittas dess c -te underordnade i intervallet {1,…, m } vid index $m\cdot i+c$ , medan dess förälder (om någon) finns vid index ${\textstil \left\lfloor {\frac {i-1}{m}}\right\rfloor } ($ förutsatt att roten har index noll, vilket betyder en 0- baserad array). Denna metod drar nytta av mer kompakt lagring och bättre referenslokalitet, särskilt under en förbeställningsgenomgång. Rymdkomplexiteten för denna metod är $O(m^{n})$ .

Pekarbaserad

Varje nod skulle ha en intern array för att lagra pekare till var och en av dess $m$ barn:

Pekarbaserad implementering av m-ärt träd där m =4.

Jämfört med arraybaserad implementering har denna implementeringsmetod överlägsen rymdkomplexitet av $O(m\cdot n)$ .

Uppräkning av maryträd

Huvudartikel: Enumerativ kombinatorik

Att lista alla möjliga m -ära träd är användbart inom många discipliner som ett sätt att kontrollera hypoteser eller teorier. Korrekt representation av mary tree-objekt kan avsevärt förenkla genereringsprocessen. Man kan konstruera en bitsekvensrepresentation genom att använda djup-första-sökningen av ett m -ärt träd med n noder som indikerar närvaron av en nod vid ett givet index med hjälp av binära värden. Till exempel representerar bitsekvensen x=1110000100010001000 ett 3-ärt träd med n=6 noder som visas nedan.

Problemet med denna representation är att listning av alla bitsträngar i lexikografisk ordning skulle innebära att två på varandra följande strängar kan representera två träd som är lexikografiskt mycket olika. Därför skulle uppräkning över binära strängar inte nödvändigtvis resultera i en ordnad generering av alla maryträd . En bättre representation baseras på en heltalssträng som anger antalet nollor mellan på varandra följande ettor, känd som Simple Zero Sequence . ${\textstyle S=s_{1},s_{2},\dots ,s_{n-1}}$ är en enkel nollsekvens som motsvarar bitsekvensen ${\textstyle 10^{s_{1}}10^{s_{2}}\ldots 10^{s_{n-1}}10^{j}}$ där j är antalet nollor som behövs i slutet av sekvensen för att få strängen att ha lämplig längd. Till exempel, $vv 00433}$ är den enkla nollsekvensrepresentationen av ovanstående figur. En mer kompakt representation av 00433 är ${\displaystyle 0^{2}4^{1}3^{2}} ,$ som kallas nollsekvens , som duplicerade baser inte kan ligga intill. Denna nya representation gör det möjligt att konstruera en nästa giltig sekvens i $O(1)$ . En enkel nollsekvens är giltig om

$$\sum _{i=1}^{i=j}s_{i}\leq (m-1 )j\qquad \forall j\leq n-1.$$

Det vill säga att antalet nollor i bitsekvensen för ett m -ärt träd inte kan överstiga det totala antalet nollpekare (dvs. pekare utan någon underordnad nod kopplad till dem). Denna summering sätter begränsningar för $n-1$ noder så att det finns utrymme för att lägga till $n^{t}h$ utan att skapa en ogiltig struktur (dvs. ha en tillgänglig nollpekare för att fästa den sista noden till den).

Tabellen nedan visar listan över alla giltiga enkla nollsekvenser för alla 3 -ära träd med 4 noder:

222	200	111	033	013
221	132	110	032	012
220	131	105	031	011
213	130	104	030	010
212	123	103	024	006
211	122	102	023	005
210	121	101	022	004
204	120	100	021	003
203	114	042	020	002
202	113	041	015	001
201	112	040	014	000

Från det nedre högra hörnet av tabellen (dvs "000"), finns det en ryggradsmall som styr genereringen av möjliga ordnade träd från "000" till "006". Stammall för denna grupp ("00X") avbildas nedan, där en ytterligare nod läggs till i positionerna märkta "x".

När man har uttömt alla möjliga positioner i ryggradsmallen, kommer en ny mall att konstrueras genom att flytta den tredje noden en position till höger som avbildas nedan, och samma uppräkning skulle ske tills alla möjliga positioner märkta "X" är slut.

Om vi ​​går tillbaka till uppräkningstabellen för alla m -ära träd, där $m=3$ och $n=4$ , kan vi enkelt observera det skenbara hoppet från "006" till " 010" kan förklaras trivialt på ett algoritmiskt sätt som avbildas nedan:

Pseudokoden för denna uppräkning ges nedan:

  
         
            
         
 Procedur  NÄSTA(  s  1  ,  s  2  , …,  s  n  −1  )  om  s  i  = 0 för all  i  så  avslutad  annars  i  ← max {  i  |  s  i  > 0}  s  i  ←  s  i  − 1  om  i  <  n  − 1  så  s  i  ← (  i  + 1) ⋅ (  m  − 1) − summa(  s  j  )  end if  för  j  ←  i  + 2,  i  + 3, …,  n  − 1  s  j  ←  k  − 1  slut om  slut 

Slinglös uppräkning

En genereringsalgoritm som tar $O(1)$ värsta tänkbara tid kallas loopless eftersom tidskomplexiteten inte kan involvera en loop eller rekursion. Loopless uppräkning av mary trees sägs vara loopless om den efter initialisering genererar successiva trädobjekt i $O(1)$ . För ett givet maryträd T med $a$ som en av dess noder och $d$ dess $t$ -te barn, en vänster-t-rotation vid $a$ görs genom att göra $d$ till rotnoden, och göra $b$ och alla dess underträd till ett barn till $a$ , dessutom tilldelar vi $m- 1$ lämnade de flesta underordnade av $d$ till $a$ och det högra underordnade av $d$ förblir kopplade till den medan $d$ flyttas upp till root, som visas nedan :

       
              
          
      Konvertera ett m-ärt träd till vänsterträd  för  i  = 1...  n  :  för  t  = 2...  m  :  medan  t  underordnad nod på djupet  i  ≠ 1: Lt-rotation vid noderna vid djupet  i  slutet medan  slutet för  slut för 

En höger-t-rotation vid d är inversen av denna operation. Den vänstra kedjan av T är en sekvens av $x_{1},x_{2},\dots ,x_{n}$ noder så att $x_{ 1}$ är roten och alla noder utom $x_{n}$ har ett barn anslutet till sin pekare längst till vänster (dvs. ${\displaystyle m[1]} )$ . Vilket mary- träd som helst kan transformeras till ett vänsterkedjeträd genom att använda en sekvens av ändliga vänster-t-rotationer för t från 2 till m . Specifikt kan detta göras genom att utföra vänster-t-rotationer på varje nod $x_{i}$ tills alla dess $m-1$ underträd blir noll på varje djup. Sedan definierar sekvensen av antalet vänster-t-rotationer utförda på djupet i betecknad med $c_{i}$ ett kodord för ett mary- träd som kan återställas genom att utföra samma sekvens av höger-t-rotationer .

Låt $m-1$ tuppel av $c_{1},c_{2},\dots ,c_{m-1}$ representera antalet L-2- rotationer, L-3- rotationer, ..., Lm -rotationer som har inträffat vid roten (dvs i =1). Därefter $c_{(i-1)(m-1)+t-1}$ är antalet Lt- rotationer som krävs på djupet i .

Att fånga antal vänsterrotationer på varje djup är ett sätt att koda ett m -ärt träd. Att räkna upp all möjlig laglig kodning skulle alltså hjälpa oss att generera alla m -ära träd för en given m och n . Men inte alla $c_{i}$ sekvenser av m icke-negativa heltal representerar ett giltigt m-ärt träd. En sekvens av $(n-1)\cdot (m-1)+1$ icke-negativa heltal är en giltig representation av ett mary -träd om och bara om

$$\sum _{i=j}^{n}\sum _{t=2}^{m}c_{(i-1)(m-1)+t-1}\qquad \leq nj, \qquad \forall j\in 0\dots n.$$

Lexikografiskt minsta kodordsrepresentation av en m-är med n noder är alla nollor och den största är n −1 ettor följt av m −1 noll till höger.

 
        
     
        
        
        
 Initialisering  c[i] till noll för alla i från 1 till  n  ⋅(  k  − 1) p[i] satt till  n  − 1 för i från 1 till n  summa  ← 0  j  ←  m  − 1  Uppsägningsvillkor  Avsluta när c[1 ] =  n  − 1  Procedur  NÄSTA  summa  ←  summa  + 1 −  c  [  j  + 1]  c  [j] ←  c  [  j  ] + 1  om  p  [  q  [  j  ]] >  p  [  q  [  j  + 1]] + 1  sedan  p  [  q  [  j  ]] ←  p  [  q  [  j  + 1]] + 1  slut om  p  [  q  [  j  +  c  [  j  ]]] ←  p  [  q  [  j  ]]  c  [  j  + 1] ← 0  om  summa  =  p  [  q  [  j  ]]  så  j  ←  j  − 1  annat  p  [  n  ] ←  summa  j  ←  m  − 1  slut om  slut 

Ansökan

En av tillämpningarna för m -ary tree är att skapa en ordbok för validering av acceptabla strängar. För att göra det, låt m vara lika med antalet giltiga alfabet (t.ex. antalet bokstäver i det engelska alfabetet ) med roten på trädet som representerar startpunkten. På samma sätt kan vart och ett av barnen ha upp till m barn som representerar nästa möjliga tecken i strängen. Således kan tecken längs vägarna representera giltiga nycklar genom att markera sluttecknet på nycklarna som "terminalnod". Till exempel, i exemplet nedan är "at" och "and" giltiga nyckelsträngar med "t" och "d" markerade som terminalnoder. Terminalnoder kan lagra extra information för att associeras med en given nyckel. Det finns liknande sätt att bygga en sådan ordbok med B-tree , Octree och/eller trie .

Se även

• Förgreningsfaktor
• Vänster-barn höger-syskon binärt träd
• Binärt träd

•   Storer, James A. (2001). En introduktion till datastrukturer och algoritmer . Birkhäuser Boston. ISBN 3-7643-4253-6 .

externa länkar

• N -ary trees, Bruno R. Preiss, Ph.D, P.Eng.