Ternärt träd

Ett enkelt ternärt träd i storlek 10 och höjd 2.

Inom datavetenskap är ett ternärt träd en träddatastruktur där varje nod har högst tre underordnade noder , vanligtvis särskiljda som "vänster", "mitt" och "höger". Noder med barn är föräldranoder, och barnnoder kan innehålla referenser till sina föräldrar. Utanför trädet finns det ofta en referens till "rot"-noden (förfadern till alla noder), om den finns. Vilken nod som helst i datastrukturen kan nås genom att börja vid rotnoden och upprepade gånger följa referenser till antingen vänster, mitten eller höger underordnad.

Ternära träd används för att implementera ternära sökträd och ternära högar .

Definition

Directed Edge - Länken från föräldern till barnet.
Rot - Noden utan föräldrar. Det finns högst en rotnod i ett rotat träd.
Leaf Node - Alla noder som inte har några barn.
Föräldernod - Vilken nod som helst som är ansluten med en riktad kant till sitt barn eller sina barn.
Child Node - Vilken nod som helst som är ansluten till en överordnad nod med en riktad kant.
Djup - Längden på banan från roten till noden. Uppsättningen av alla noder på ett givet djup kallas ibland en nivå av trädet. Rotnoden är på djupet noll.
Höjd - Längden på banan från roten till den djupaste noden i trädet. Ett (rotat) träd med bara en nod (roten) har en höjd på noll. I exempeldiagrammet har trädet en höjd av 2.
Syskon - Noder som delar samma föräldernod.

- En nod p är en förfader till en nod q om den finns på vägen från q till roten. Noden q kallas då en avkomling av p.

- En storlek på en nod är antalet ättlingar den har inklusive sig själv.

Egenskaper hos ternära träd

Maximalt antal noder

– Låt $h$ vara höjden på ett ternärt träd.

– Låt $M(h)$ vara det maximala antalet noder i ett ternärt träd med höjden h

h	M ( h )
0	1
1	4
2	13
3	40

– $M(h)=1+3+9+\cdots +3^ {h}=\summa _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}$

– Varje träd med höjden h har högst ${\frac {3^{h+1}-1}{2}}$ noder.

Om en nod $N$ upptar TREE $[k]$ , lagras dess vänstra underordnade i TREE $[3k-1]$ .
Mid Child lagras i TREE $[3k]$ .
Right Child lagras i TREE $[3k+1]$ .

Vanliga operationer

Införande

Noder kan infogas i ternära träd mellan tre andra noder eller läggas till efter en extern nod . I ternära träd anges en nod som infogas om vilket barn det är.

Externa noder

Säg att den externa noden som läggs till är nod A. För att lägga till en ny nod efter nod A, tilldelar A den nya noden som ett av dess underordnade och den nya noden tilldelar nod A som sin förälder.

Interna noder

Insättning på interna noder är mer komplex än på externa noder. Säg att den interna noden är nod A och att nod B är A:s underordnade. (Om infogningen är att infoga ett höger underordnat, då är B A:s högra underordnade, och på samma sätt med en vänster underordnad insättning eller mellanbarn.) A tilldelar sitt underordnade till den nya noden och den nya noden tilldelar sin förälder till A. Sedan tilldelar den nya noden sitt underordnade till B och B tilldelar sin förälder som den nya noden.

Radering

Borttagning är den process där en nod tas bort från trädet. Endast vissa noder i ett ternärt träd kan tas bort entydigt.

Nod med noll eller ett barn

Säg att noden som ska raderas är nod A. Om en nod inte har några barn ( extern nod ), utförs raderingen genom att ställa in barnet till A:s förälder till null och A:s förälder till null. Om den har ett barn, ställ in föräldern till A:s barn till A:s förälder och ställ in barnet till A:s förälder till A:s barn.

Jämförelse med andra träd

Bilden nedan är ett binärt sökträd som representerar 12 tvåbokstavsord. Alla noder på det vänstra barnet har mindre värden, medan alla noder på det högra barnet har större värden för alla noder. En sökning börjar från roten. För att hitta ordet "ON" jämför vi det med "IN" och tar rätt gren. Varje jämförelse kunde komma åt varje tecken i båda orden.

i / \ vara av / \ / \ som av är eller \ \ \ / \ vid han det på

Digital sökning försöker lagra strängar tecken för tecken. Nästa bild är ett träd som representerar samma uppsättning av 12 ord;

_ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ abhiot / \ / \ | / | \ /|\ | steyenstfnro som att vara av han i är det av på eller till

varje inmatningsord visas under noden som representerar det. I ett träd som representerar ord med små bokstäver har varje nod 26-vägs förgrening. Sökningarna är mycket snabba: En sökning efter "IS" börjar vid roten, tar "I"-grenen, sedan "S"-grenen och slutar vid den önskade noden. Vid varje nod kommer man åt ett array-element, testar för null och tar en gren.

i / | \ / | \ bso / | \ / \ | \ aehntnt | \ | / \ | syefro \ t

Bilden ovan är ett balanserat tremigt sökträd för samma uppsättning av 12 ord. De låga och höga pekarna visas som vinklade linjer, medan lika pekare visas som vertikala linjer. En sökning efter ordet "IS" startar vid roten, fortsätter ner det lika barnet till noden med värdet "S", och slutar där efter två jämförelser. En sökning på "AXE" gör tre jämförelser med den första bokstaven "A" och två jämförelser med den andra bokstaven "X" innan det rapporteras att ordet inte finns i trädet.

Exempel på ternära träd

Ternärt sökträd
Ternärt binärt träd
Ternär hög
Två oändliga ternära träd som innehåller alla primitiva Pythagoras trippel beskrivs i Tree of primitive Pythagorean triples och i Formler för att generera Pythagoras trippel . Rotnoden i båda träden innehåller trippel [3,4,5].

Se även