Vi läser de linjära datastrukturerna som en array, länkad lista, stack och kö där alla element är ordnade på ett sekventiellt sätt. De olika datastrukturerna används för olika typer av data.

Några faktorer beaktas vid val av datastruktur:

genomstruken markdown

Vilken typ av data behöver lagras?: Det kan vara en möjlighet att en viss datastruktur kan passa bäst för någon typ av data.Kostnad för operationer:Om vi ​​vill minimera kostnaden för operationerna för de mest frekvent utförda operationerna. Till exempel har vi en enkel lista där vi måste utföra sökoperationen; sedan kan vi skapa en array där element lagras i sorterad ordning för att utföra binär sökning . Den binära sökningen fungerar mycket snabbt för den enkla listan eftersom den delar upp sökutrymmet i hälften.Minnesanvändning:Ibland vill vi ha en datastruktur som använder mindre minne.

Ett träd är också en av de datastrukturer som representerar hierarkiska data. Anta att vi vill visa de anställda och deras positioner i hierarkisk form så kan det representeras enligt nedan:

Ovanstående träd visar organisationshierarki av något företag. I ovanstående struktur, john är vd av företaget, och John har två direkta rapporter namngivna som Steve och Rohan . Steve har tre direkta rapporter namngivna Lee, Bob, Ella var Steve är chef. Bob har två direkta rapporter namngivna Skall och Emma . Emma har två direktrapporter namngivna Tom och Raj . Tom har en direktrapport namngiven Räkningen . Denna speciella logiska struktur är känd som en Träd . Dess struktur liknar det riktiga trädet, så det heter a Träd . I den här strukturen rot är överst, och dess grenar rör sig i riktning nedåt. Därför kan vi säga att trädets datastruktur är ett effektivt sätt att lagra data på ett hierarkiskt sätt.

Låt oss förstå några nyckelpunkter i trädets datastruktur.

• En träddatastruktur definieras som en samling objekt eller enheter som kallas noder som är sammanlänkade för att representera eller simulera hierarki.
• En träddatastruktur är en icke-linjär datastruktur eftersom den inte lagras på ett sekventiellt sätt. Det är en hierarkisk struktur eftersom element i ett träd är ordnade på flera nivåer.
• I träddatastrukturen är den översta noden känd som en rotnod. Varje nod innehåller vissa data, och data kan vara av vilken typ som helst. I ovanstående trädstruktur innehåller noden namnet på den anställde, så typen av data skulle vara en sträng.
• Varje nod innehåller en del data och länken eller referensen till andra noder som kan kallas barn.

Några grundläggande termer som används i träddatastrukturen.

Låt oss överväga trädstrukturen, som visas nedan:

I ovanstående struktur är varje nod märkt med något nummer. Varje pil som visas i ovanstående figur är känd som en länk mellan de två noderna.

Rot:Rotnoden är den översta noden i trädhierarkin. Med andra ord är rotnoden den som inte har någon förälder. I ovanstående struktur är nod numrerad 1 trädets rotnod. Om en nod är direkt kopplad till någon annan nod, skulle den kallas en förälder-barn-relation.Barnnod:Om noden är en avkomling av någon nod, är noden känd som en undernod.Förälder:Om noden innehåller någon undernod, sägs den noden vara föräldern till den undernoden.Syskon:Noderna som har samma förälder kallas syskon.Bladnod:-Trädets nod, som inte har någon barnnod, kallas en lövnod. En lövnod är den nedersta noden i trädet. Det kan finnas hur många lövnoder som helst i ett allmänt träd. Bladnoder kan också kallas externa noder.Interna noder:En nod har minst en undernod känd som en inre Ancestor nod:-En förfader till en nod är vilken föregångare som helst på en väg från roten till den noden. Rotnoden har inga förfäder. I trädet som visas i bilden ovan är noderna 1, 2 och 5 förfäder till nod 10.Ättling:Den omedelbara efterföljaren till den givna noden är känd som en ättling till en nod. I figuren ovan är 10 avkomling av nod 5.

Egenskaper för träddatastruktur

Rekursiv datastruktur:Trädet är också känt som en rekursiv datastruktur . Ett träd kan definieras som rekursivt eftersom den särskiljande noden i en träddatastruktur är känd som en rotnod . Trädets rotnod innehåller en länk till alla underträdens rötter. Det vänstra underträdet visas i den gula färgen i bilden nedan och det högra underträdet visas i den röda färgen. Det vänstra underträdet kan delas upp i underträd som visas i tre olika färger. Rekursion innebär att reducera något på ett liknande sätt. Så denna rekursiva egenskap hos träddatastrukturen implementeras i olika applikationer.
Antal kanter:Om det finns n noder skulle det ha n-1 kanter. Varje pil i strukturen representerar länken eller sökvägen. Varje nod, förutom rotnoden, kommer att ha minst en inkommande länk känd som en kant. Det skulle finnas en länk för relationen mellan föräldrar och barn.Djup av nod x:Djupet av nod x kan definieras som längden på vägen från roten till noden x. En kant bidrar med en enhetslängd i banan. Så, djupet för nod x kan också definieras som antalet kanter mellan rotnoden och noden x. Rotnoden har 0 djup.Höjd på nod x:Höjden på nod x kan definieras som den längsta vägen från noden x till lövnoden.

Baserat på egenskaperna för träddatastrukturen klassificeras träd i olika kategorier.

Implementering av träd

Träddatastrukturen kan skapas genom att skapa noderna dynamiskt med hjälp av pekarna. Trädet i minnet kan representeras enligt nedan:

Ovanstående figur visar representationen av träddatastrukturen i minnet. I ovanstående struktur innehåller noden tre fält. Det andra fältet lagrar data; det första fältet lagrar adressen till det vänstra barnet, och det tredje fältet lagrar adressen till det högra barnet.

I programmering kan strukturen för en nod definieras som:

 struct node { int data; struct node *left; struct node *right; } 

Ovanstående struktur kan endast definieras för de binära träden eftersom det binära trädet kan ha ytterst två barn, och generiska träd kan ha fler än två barn. Strukturen för noden för generiska träd skulle vara annorlunda jämfört med det binära trädet.

välj från flera tabeller sql

Tillämpningar av träd

Följande är tillämpningarna för träd:

Lagra naturligt hierarkisk data:Träd används för att lagra data i den hierarkiska strukturen. Till exempel filsystemet. Filsystemet som är lagrat på skivenheten, filen och mappen är i form av naturligt hierarkiska data och lagras i form av träd.Organisera data:Den används för att organisera data för effektiv infogning, radering och sökning. Till exempel har ett binärt träd en logN-tid för att söka efter ett element.Försök:Det är en speciell sorts träd som används för att lagra ordboken. Det är ett snabbt och effektivt sätt för dynamisk stavningskontroll.Högen:Det är också en träddatastruktur implementerad med hjälp av arrayer. Den används för att implementera prioriterade köer.B-Tree och B+Tree:B-Tree och B+Tree är träddatastrukturerna som används för att implementera indexering i databaser.Routningstabell:Träddatastrukturen används också för att lagra data i routningstabeller i routrarna.

Typer av träddatastruktur

Följande är typerna av en träddatastruktur:

string tokenizer java

Allmänt träd:Det allmänna trädet är en av typerna av träddatastruktur. I det allmänna trädet kan en nod ha antingen 0 eller maximalt n antal noder. Det finns ingen begränsning på graden av noden (antalet noder som en nod kan innehålla). Den översta noden i ett allmänt träd är känd som en rotnod. Barnen till föräldranoden kallas underträd .

Det kan finnas n antal underträd i ett allmänt träd. I det allmänna trädet är underträden oordnade eftersom noderna i underträdet inte kan ordnas.
Varje icke-tomt träd har en nedåtgående kant, och dessa kanter är anslutna till noderna som kallas barnnoder . Rotnoden är märkt med nivå 0. Noderna som har samma förälder är kända som syskon . Binärt träd :Här antyder det binära namnet självt två tal, d.v.s. 0 och 1. I ett binärt träd kan varje nod i ett träd ha ytterst två undernoder. Här betyder ytterst om noden har 0 noder, 1 nod eller 2 noder.

För att veta mer om det binära trädet, klicka på länken nedan:
https://www.javatpoint.com/binary-tree Binärt sökträd :Binärt sökträd är en icke-linjär datastruktur i vilken en nod är ansluten till n antal noder. Det är en nodbaserad datastruktur. En nod kan representeras i ett binärt sökträd med tre fält, d.v.s. datadel, vänsterbarn och högerbarn. En nod kan kopplas till de två yttersta undernoderna i ett binärt sökträd, så noden innehåller två pekare (vänster underordnad och höger underordnad pekare).
Varje nod i det vänstra underträdet måste innehålla ett värde som är mindre än värdet på rotnoden, och värdet för varje nod i det högra underträdet måste vara större än värdet på rotnoden.

En nod kan skapas med hjälp av en användardefinierad datatyp som kallas struktur, enligt nedanstående:

 struct node { int data; struct node *left; struct node *right; } 

Ovanstående är nodstrukturen med tre fält: datafält, det andra fältet är den vänstra pekaren för nodtypen och det tredje fältet är den högra pekaren för nodtypen.

För att veta mer om det binära sökträdet, klicka på länken nedan:

https://www.javatpoint.com/binary-search-tree

AVL-träd

Det är en av typerna av det binära trädet, eller så kan vi säga att det är en variant av det binära sökträdet. AVL-trädet tillfredsställer egenskapen hos binärt träd såväl som av binärt sökträd . Det är ett självbalanserande binärt sökträd som uppfanns av Adelson Velsky Lindas . Här innebär självbalansering att balansera höjderna på vänster underträd och höger underträd. Denna balansering mäts i termer av balanserande faktor .

Vi kan betrakta ett träd som ett AVL-träd om trädet följer det binära sökträdet samt en balanserande faktor. Balanseringsfaktorn kan definieras som skillnaden mellan höjden på det vänstra underträdet och höjden på det högra underträdet . Balansfaktorns värde måste vara antingen 0, -1 eller 1; därför bör varje nod i AVL-trädet ha värdet på balanseringsfaktorn antingen som 0, -1 eller 1.

För att veta mer om AVL-trädet, klicka på länken nedan:

https://www.javatpoint.com/avl-tree

Röd-svart träd

Det röd-svarta trädet är det binära sökträdet. Förutsättningen för det röd-svarta trädet är att vi bör känna till det binära sökträdet. I ett binärt sökträd bör värdet på det vänstra underträdet vara mindre än värdet för den noden, och värdet på det högra underträdet bör vara större än värdet på den noden. Som vi vet är tidskomplexiteten för binär sökning i genomsnittsfallet log₂n, det bästa fallet är O(1), och det sämsta fallet är O(n).

När någon operation utförs på trädet vill vi att vårt träd ska vara balanserat så att alla operationer som sökning, infogning, radering etc. tar kortare tid, och alla dessa operationer kommer att ha samma tidskomplexitet som logga₂n.

Det röd-svarta trädet är ett självbalanserande binärt sökträd. AVL-trädet är också ett höjdbalanserande binärt sökträd då varför behöver vi ett röd-svart träd . I AVL-trädet vet vi inte hur många rotationer som skulle krävas för att balansera trädet, men i det Röd-svarta trädet krävs max 2 rotationer för att balansera trädet. Den innehåller en extra bit som representerar antingen den röda eller svarta färgen på en nod för att säkerställa balanseringen av trädet.

Splay träd

Splayträdets datastruktur är också ett binärt sökträd där nyligen nått element placeras vid rotpositionen av trädet genom att utföra några rotationsoperationer. Här, splaying betyder den nyligen öppnade noden. Det är en självbalanserande binärt sökträd som inte har något explicit balansvillkor som AVL träd.

java karta

Det kan vara en möjlighet att höjden på splayträdet inte är balanserad, dvs. höjden på både vänster och höger underträd kan skilja sig, men operationerna i splay tree tar ordning på lugna tid var n är antalet noder.

Splayträd är ett balanserat träd men det kan inte betraktas som ett höjdbalanserat träd eftersom det efter varje operation utförs rotation vilket leder till ett balanserat träd.

Treap

Treap-datastrukturen kom från Tree and Heap-datastrukturen. Så den omfattar egenskaperna för både träd- och heapdatastrukturer. I binärt sökträd måste varje nod på det vänstra underträdet vara lika med eller mindre än värdet på rotnoden och varje nod på det högra underträdet måste vara lika med eller större än värdet på rotnoden. I högdatastrukturen innehåller både höger och vänster underträd större nycklar än roten; därför kan vi säga att rotnoden innehåller det lägsta värdet.

I treap-datastrukturen har varje nod båda nyckel och prioritet där nyckeln härleds från det binära sökträdet och prioritet härleds från högdatastrukturen.

De Treap datastrukturen följer två egenskaper som anges nedan:

java kartor

• Höger underordnad av en nod>=nuvarande nod och vänster underordnad av en nod<=current node (binary tree)< li>
• Underordnade underträd måste vara större än noden (högen)

B-träd

B-träd är ett balanserat m-väg träd var m definierar trädets ordning. Hittills har vi läst att noden bara innehåller en nyckel men b-tree kan ha mer än en nyckel och fler än 2 barn. Den upprätthåller alltid den sorterade datan. I binärt träd är det möjligt att lövnoder kan vara på olika nivåer, men i b-träd måste alla lövnoder vara på samma nivå.

Om ordningen är m har noden följande egenskaper:

• Varje nod i ett b-träd kan ha maximum m barn
• För minsta barn har en lövnod 0 barn, rotnoden har minst 2 barn och den interna noden har minsta tak på m/2 barn. Till exempel är värdet på m 5 vilket betyder att en nod kan ha 5 barn och interna noder kan innehålla max 3 barn.
• Varje nod har maximala (m-1) nycklar.

Rotnoden måste innehålla minst 1 nyckel och alla andra noder måste innehålla minst tak på m/2 minus 1 nycklar.