Träd (datastruktur)

Ett träd  är en av de mest använda datastrukturerna inom datavetenskap , som emulerar en trädstruktur som en uppsättning anslutna noder. Det är en sammankopplad graf som inte innehåller cykler. De flesta källor lägger också till ett villkor att grafens kanter inte får riktas. Utöver dessa tre begränsningar anger vissa källor att kanterna på en graf inte får viktas.

Definitioner

• Rotnoden  är den översta noden i trädet (nod 8 i exemplet).
• Roten  är en av hörnen, på begäran av observatören.

• Löv , löv eller lövnod - en nod som inte har några barn (noder 1, 4, 7, 13).

• En intern nod  är vilken nod som helst i trädet som har barn och därför inte är en lövnod (3, 6, 10, 14).

Ett träd sägs vara orienterat om ingen kant går in i roten.

• Den fullständiga sammanlänkade nyckeln  är postidentifieraren, som bildas genom att sammanfoga alla nycklar för de överordnade posterna (grupp)instanserna.

Noder

En nod är en instans av en av två typer av grafelement, motsvarande ett objekt av någon fast karaktär. En nod kan innehålla ett värde, ett tillstånd eller en representation av en enskild informationsstruktur eller själva trädet. Varje trädnod har noll eller fler underordnade noder som är längre ner i trädet (enligt konventionen "växer" träd ner, inte uppåt, som riktiga träd gör). En nod som har en underordnad nod kallas en föräldernod för dess underordnade (eller en föregångarnod eller en äldre nod). Varje nod har högst en förälder. Höjden på en nod är den maximala längden på en nedåtgående bana från den noden till den lägsta noden (kantnoden), som kallas ett löv . Höjden på rotnoden är lika med höjden på hela trädet. Häckningsdjupet för en nod är lika med längden på vägen till rotnoden.

Rotnoder

Noden utan förfäder (överst) kallas rotnoden . Detta är den nod där de flesta operationerna på trädet börjar (även om vissa algoritmer börjar vid "löv" och körs tills de når roten). Alla andra noder kan nås genom att gå från rotnoden längs kanter (eller länkar) (enligt den formella definitionen måste varje sådan väg vara unik). I diagram är det vanligtvis avbildat längst upp. I vissa träd, såsom högar , har rotnoden speciella egenskaper. Varje trädnod kan ses som rotnoden till ett underträd som "växer" från den noden.

Underträd

Ett underträd  är en del av en trädliknande datastruktur som kan representeras som ett separat träd. Vilken nod som helst i trädet T tillsammans med alla dess underliggande noder är ett underträd till trädet T . För vilken nod som helst i ett underträd måste antingen det finnas en sökväg till rotnoden för det underträdet, eller så måste själva noden vara rotnoden. Det vill säga, ett underträd är associerat med rotnoden av ett helt träd, och förhållandet mellan ett underträd och alla andra noder definieras genom begreppet motsvarande underträd (i analogi med termen "motsvarande undermängd ").

Ordna träd

Det finns två huvudtyper av träd. I ett rekursivt träd eller ett oordnat träd är det bara själva trädets struktur som har betydelse, utan att ta hänsyn till ordningen på barnen för varje nod. Ett träd i vilket en ordning ges (till exempel varje kant som leder till en ättling tilldelas ett annat naturligt nummer ) kallas ett träd med namngivna kanter eller ett ordnat träd med en datastruktur som ges före namngivning, kallad en ordnad träddatastruktur .

Ordnade träd är de vanligaste bland trädstrukturer. Ett binärt sökträd  är en typ av ordnat träd.

Representation av träd

Det finns många olika sätt att representera träd. Den vanligaste representationen visar noder som poster placerade i dynamiskt allokerat minne med pekare till deras ättlingar, förfäder (eller båda), eller som element i en array , länkade samman av relationer definierade av deras positioner i arrayen (till exempel en binär hög ) .

Träd som grafer

I grafteorin är ett träd  en sammankopplad acyklisk graf . Ett rotat träd är en graf med vertex vald som rot. I det här fallet ärver vilka två hörn som helst som är förbundna med en kant relationen mellan föräldrar och barn. En frånkopplad graf som enbart består av träd kallas en skog .

Lösningar

En steg-för-steg-uppräkning av trädelement längs länkarna mellan förfädernoder och efterkommande noder kallas trädgenomgång . Ofta kan en operation utföras genom att föra pekaren över enskilda noder. En genomgång där varje förfadersnod slås upp före dess avkomlingar kallas för en förbeställd genomgång eller genomgång i direkt ordning (förbeställningspromenad), och när man först tittar på avkomlingar och sedan på förfäder, kallas genomgången post -beställd traversering eller traversering i omvänd ordning (post-order walk). Det finns också en symmetrisk genomgång , som besöker det vänstra underträdet först, sedan noden, sedan det högra underträdet och en breddövergång , som besöker noderna nivå för nivå (trädets N:te nivå är uppsättningen av noder med höjd N ). Varje nivå passeras från vänster till höger.

Allmänna operationer

• infoga ett nytt element på en specifik position;
• insättning av underträd;
• lägga till en trädgren (kallad ett transplantat );
• hitta rotelementet för valfri nod;
• hitta den minst gemensamma förfadern till två hörn;
• uppräkning av alla element i trädet;
• uppräkning av element i en trädgren;
• sök efter ett isomorft underträd;
• elementsökning;
• avlägsnande av en trädgren (kallad beskärning );
• ta bort ett underträd;
• ta bort ett element.

Allmän tillämpning

• hantering av datahierarki ;
• förenkling av informationssökning (se trädgenomgång ) ;
• hantera sorterade listor med data;
• analys av aritmetiska uttryck ( engelsk  parsing ), programoptimering ;
• som en teknik för att arrangera digitala bilder för att erhålla olika visuella effekter ;
• en form av beslutsfattande i flera steg (se affärsschack ).

Se även

• Binär uppdelning av utrymme
• Heap (datastruktur)
• Träd (grafteori)
• Träd (mängdlära)
• trädstruktur
• prefixträd
• exponentiellt träd

• binärt träd

• AA-träd
• AVL-träd
• Röd-svart träd
• expanderande träd
• träd med böter

• B-träd ( 2-3-träd , B+-träd , B*-träd , UB-träd )
• DSW-algoritm
• dansande träd
• enfilade
• blandat träd
• k-dimensionellt träd
• octree
• quadtree
• R-träd (datastruktur)
• Beläggning träd
• Restträd
• segmentträd
• Passlista
• T-träd
• T-pyramid
• översta trädet
• van Emde Boas träd
• Sytt binärt träd
• Lista över datastrukturer (träd)

Anteckningar

Litteratur

• Donald E. Knuth . Kapitel 2.3. Träd // Konsten att programmera = Konsten att programmera. - 3:e uppl. - M .: Williams , 2002. - T. 1. Grundläggande algoritmer. — 720 s. — ISBN 5-8459-0080-8 (ryska) ISBN 0-201-89683-4 (engelska).
• Thomas Cormen , Charles Leiserson , Ronald Rivest , Clifford Stein . Introduktion till algoritmer. - 2:a upplagan. - MIT Press, McGraw-Hill, 2001. - ISBN 0-262-03293-7 .
  • Avsnitt 10.4: Representerande rotade träd, s.214-217.
  • Kapitel 12-14 (Binära sökträd, röd-svarta träd, förstärkande datastrukturer), s. 253-320.

Länkar

• Traversering av binära träd
• Röd-svarta träd