Introduktion til træer i datastruktur
Før vi forstå typerne af træer i datastruktur, skal vi først undersøge træerne i datastruktur. Træ i computerfeltet kaldes også det virkelige træ, men forskellen mellem den virkelige verden og computerfelttræet er, at det visualiseres som omvendt og rod oven på det og gren fra rod til træblade. Blandt forskellige applikationer i den virkelige verden bruges trædatastrukturen, da den kan demonstrere forhold mellem forskellige noder med forældre-barn-hierarkiet. Det kaldes også en hierarkisk datastruktur på grund af dette. Det er mest populært til at forenkle og fremskynde søgning og sortering. Det betragtes som en af de stærkeste og mest avancerede datastrukturer. Et træ er en repræsentation af den ikke-lineære datastruktur. Et træ kan vises ved hjælp af forskellige brugerdefinerede eller primitive datatyper. Vi kan bruge arrays, klasser tilsluttede lister eller andre former for datastrukturer til at implementere træet. Det er en gruppe af noder, der er indbyrdes forbundet. Knudepunkter er knyttet til kanterne for at demonstrere forholdet.
Relationer i et træ: I det ovenstående diagram er P rodens træ, også P er forælder til Q, R og S. Q er barn af P. Derfor er Q, R og S søskende. Hvorimod P er bedsteforældre til A, B, C, D og E.
Hvad er træer?
Et træ er en hierarkisk datastruktur, der naturligt gemmer informationen på en hierarkisk måde. Trædatasstrukturen er en af de mest effektive og modne. De knudepunkter, der er forbundet med kanterne, er repræsenteret.
Egenskaber ved træ: Hvert træ har en bestemt rodnode. Hver træknude kan krydses af en rodnode. Det kaldes rod, da træet var den eneste rod. Hvert barn har kun én forælder, men forælderen kan have mange børn.
Typer af træer i datastruktur
Herunder er træsorterne i en datastruktur:
1. Generelt træ
Hvis der ikke er nogen begrænsning på træets hierarki, kaldes et træ et generelt træ. Hver knude kan have uendeligt mange børn i General Tree. Træet er supersættet af alle andre træer.
2. Binært træ
Det binære træ er den slags træ, hvor de fleste to børn kan findes til hver forælder. Børnene er kendt som det venstre barn og det højre barn. Dette er mere populært end de fleste andre træer. Når visse begrænsninger og egenskaber anvendes i et binært træ, bruges også et antal andre, såsom AVL-træ, BST (Binary Search Tree), RBT-træ osv. Når vi går fremad, forklarer vi alle disse stilarter i detaljer.
3. Binært søgetræ
Binary Search Tree (BST) er en binær træudvidelse med flere valgfri begrænsninger. Værdien for det venstre barn i en knude skal i BST være mindre end eller lig med den overordnede værdi, og den højre børns værdi skal altid være større end eller lig med den overordnede værdi. Denne egenskab med binært søgetræ gør den ideel til søgefunktioner, da vi nøjagtigt kan bestemme ved hver knude, om værdien er i venstre eller højre undertræ. Dette er grunden til, at søgetreet er navngivet.
4. AVL-træ
AVL-træet er et binært søgetræ-selvbalancerende. På opfindernes vegne Adelson-Velshi og Landis gives navnet AVL. Dette var det første træ, der balanserede dynamisk. En balanceringsfaktor tildeles for hver knude i AVL-træet, baseret på om træet er afbalanceret eller ej. Højden på knudepunktbørnene er højst 1. AVL-vinstok. I AVL-træet er den korrekte balancefaktor 1, 0 og -1. Hvis træet har en ny knude, roteres det for at sikre, at træet er afbalanceret. Derefter drejes det. Almindelige operationer som visning, indsættelse og fjernelse tager O (log n) tid i AVL-træet. Det anvendes mest, når du arbejder med opslag-operationer.
5. Rød-sort træ
En anden slags auto-afbalancerende træ er rød-sort. Det rød-sorte navn gives, fordi det rød-sorte træ har enten rødt eller sortmalet på hver knude i henhold til det rød-sorte træs egenskaber. Det opretholder balancen i skoven. Selvom dette træ ikke er et fuldt afbalanceret træ, tager søgefunktionen kun O (log n) tid. Når de nye noder tilføjes i rød-sort træ, roteres knuder igen for at bevare det rød-sorte træs egenskaber.
6. N-ary træ
Det maksimale antal børn i denne type træ, der kan have en knude, er N. Et binært træ er et toårigt træ, som højst 2 børn i hver binær træknudepunkt. Et komplet N-ary-træ er et træ, hvor børn af en knude enten er 0 eller N.
Fordele ved træet
Nu vil vi forstå fordelene ved træet:
- Træet afspejler strukturelle forbindelser i dataene.
- Træet bruges til hierarki.
- Det tilbyder en effektiv søgning og indsættelsesprocedure.
- Træerne er fleksible. Dette gør det muligt at flytte undertræer med minimal indsats.
Konklusion - Typer af træer i datastruktur
Så her i denne artikel har vi set hvad der er trestruktur, hvad er forskellige trætyper i datastrukturen og dens fordele. Jeg håber, at du fik en idé om nogle af de almindelige træer i strukturen af dataene.
Anbefalede artikler
Dette er en guide til typer af træer i datastruktur. Her diskuterer vi hvad der er træer, 6 typer træer i datastruktur med fordele. Du kan også gennemgå vores andre relaterede artikler for at lære mere -
- AWS-datapipeline
- Oracle Data Warehousing
- Multidimensionel database
- Datastruktur Java Interview spørgsmål