Introduktion till träd i datastruktur

Innan vi förstår typerna av träd i datastruktur, kommer vi först att studera träden i Datastruktur. Träd i datorfältet kallas också det verkliga trädet, men skillnaden mellan den verkliga världen och datorfältsträdet är att det visualiseras som upp och ner på roten och grenar från rot till träd. Bland olika verkliga tillämpningar används träddatastrukturen eftersom den kan visa förhållanden mellan olika noder med förälder-barnhierarkin. Det kallas också en hierarkisk datastruktur på grund av detta. Det är mest populärt för att förenkla och påskynda sökning och sortering. Det betraktas som en av de starkaste och mest avancerade datastrukturerna. Ett träd är en representation av den icke-linjära datastrukturen. Ett träd kan visas med olika användardefinierade eller primitiva datatyper. Vi kan använda matriser, klasser anslutna listor eller andra typer av datastrukturer för att implementera trädet. Det är en grupp noder som är sammanhängande. Noder är fästa vid kanterna för att visa förhållandet.

Relationer i ett träd: I ovanstående diagram är P rotens träd, även P är förälder till Q, R och S. Q är barn av P. Därför är Q, R och S syskon. Medan P är farförälder till A, B, C, D och E.

Vad är träd?

Ett träd är en hierarkisk datastruktur som naturligt lagrar informationen på ett hierarkiskt sätt. Trädatasstrukturen är en av de mest effektiva och mogna. Noderna som är anslutna med kanterna representeras.

Egenskaper för träd: Varje träd har en specifik rotnod. Varje trädnod kan korsas av en rotnod. Det kallas rot, eftersom trädet var den enda roten. Varje barn har bara en förälder, men föräldern kan ha många barn.

Typer av träd i datastruktur

Nedan är de typer av träd i en datastruktur:

1. Allmänt träd

Om ingen begränsning placeras på trädets hierarki kallas ett träd för ett allmänt träd. Varje nod kan ha oändligt många barn i General Tree. Trädet är superuppsättningen för alla andra träd.

2. Binärt träd

Det binära trädet är den typ av träd där de flesta två barn kan hittas för varje förälder. Barnen är kända som vänsterbarnet och det högra barnet. Detta är mer populärt än de flesta andra träd. När vissa begränsningar och egenskaper tillämpas i ett binärt träd, används också ett antal andra såsom AVL-träd, BST (Binary Search Tree), RBT-träd, etc. När vi går framåt förklarar vi alla dessa stilar i detalj.

3. Binary Search Tree

Binary Search Tree (BST) är ett binärt trädförlängning med flera valfria begränsningar. Vänsterbarnets värde för en nod ska i BST vara mindre än eller lika med föräldervärdet och det högra barnvärdet ska alltid vara större än eller lika med förälderns värde. Den här egenskapen Binary Search Tree gör den idealisk för sökoperationer eftersom vi exakt kan bestämma vid varje nod om värdet finns i vänster eller höger underträd. Det är därför sökträdet heter.

4. AVL-träd

AVL-träd är en självbalansering av binärt sökträd. På uppdrag av uppfinnarna Adelson-Velshi och Landis ges namnet AVL. Detta var det första trädet som balanserade dynamiskt. En balanseringsfaktor tilldelas för varje nod i AVL-trädet, baserat på om trädet är balanserat eller inte. Noden barnens höjd är högst 1. AVL vinstockar. I AVL-trädet är rätt balansfaktor 1, 0 och -1. Om trädet har en ny nod, kommer det att roteras för att säkerställa att trädet är balanserat. Den roteras sedan. Vanliga operationer som visning, infogning och borttagning tar O (log n) tid i AVL-trädet. Det används mest när du arbetar med uppslagningar.

5. Röd-svart träd

En annan typ av auto-balanserande träd är röd-svart. Det röd-svarta namnet ges eftersom det röd-svarta trädet har antingen rött eller svart målade på varje nod enligt det röd-svarta trädets egenskaper. Det upprätthåller balansen i skogen. Trots att detta träd inte är ett helt balanserat träd tar sökoperationen bara O (log n) tid. När de nya noderna läggs till i röd-svart träd, roteras noderna igen för att bibehålla det rött-svarta trädets egenskaper.

6. N-ary Tree

Det maximala antalet barn i den här typen av träd som kan ha en nod är N. Ett binärt träd är ett tvåårigt träd, som högst 2 barn i varje binär trädnod. Ett komplett N-ary-träd är ett träd där barn av en nod antingen är 0 eller N.

Fördelar med träd

Nu kommer vi att förstå fördelarna med träd:

  • Trädet reflekterar i data strukturella anslutningar.
  • Trädet används för hierarki.
  • Det erbjuder ett effektivt sök- och infogningsförfarande.
  • Träden är flexibla. Detta gör att underträden kan flyttas med minimal ansträngning.

Slutsats - Trädtyper i datastruktur

Så här i den här artikeln har vi sett vad som är trädstruktur, vad är olika typer av träd i datastrukturen och dess fördelar. Jag hoppas att du fick en uppfattning om några av de vanliga träden i strukturen för uppgifterna.

Rekommenderade artiklar

Detta är en guide till typer av träd i datastruktur. Här diskuterar vi vad som är träd, 6 typer av träd i datastruktur, med fördelar. Du kan också gå igenom våra andra relaterade artiklar för att lära dig mer -

  1. AWS Data Pipeline
  2. Oracle Data Warehousing
  3. Flerdimensionell databas
  4. Datastruktur Java-intervjufrågor

Kategori:

Big Data