Puude tutvustus andmestruktuuris

Enne andmestruktuuris olevate puude tüüpide mõistmist uurime kõigepealt puude andmestruktuuris. Puu arvutiväljal nimetatakse ka reaalmaailma puuks, kuid tegeliku maailma ja arvutusvälja puu erinevus seisneb selles, et see on visualiseeritud tagurpidi ja juur peal ning hargneb juurtest puulehtedeni. Erinevate reaalmaailma rakenduste hulgas kasutatakse puu andmestruktuuri, kuna see võib näidata erinevate sõlmede suhteid vanema ja lapse hierarhiaga. Seetõttu nimetatakse seda ka hierarhiliseks andmestruktuuriks. See on kõige populaarsem otsingu ja sortimise lihtsustamiseks ja kiirendamiseks. Seda peetakse üheks tugevaimaks ja arenenumaks andmestruktuuriks. Puu on mittelineaarse andmestruktuuri esitus. Puu kuvamiseks võib kasutada erinevaid kasutaja määratletud või primitiivseid andmeid. Puu rakendamiseks võime kasutada massiive, ühendatud klasside loendeid või muud tüüpi andmestruktuure. See on omavahel seotud sõlmede rühm. Suhte demonstreerimiseks on servade külge kinnitatud sõlmed.

Suhted puus : ülaltoodud diagrammil on P puu juur ka P on Q ema, R ja S. Q on P. laps. Seega Q, R ja S on õed-vennad. P on A, B, C, D ja E vanavanem.

Mis on puud?

Puu on hierarhiline andmestruktuur, mis loomulikult salvestab teabe hierarhiliselt. Puu andmestruktuur on üks tõhusamaid ja küpsemaid. Esindatud on servadega ühendatud sõlmed.

Puu omadused: Igal puul on konkreetne juursõlm. Iga puusõlme saab juursõlmega ületada. Seda nimetatakse juuriks, kuna puu oli ainus juur. Igal lapsel on ainult üks vanem, kuid vanemal võib olla palju lapsi.

Puude tüübid andmestruktuuris

Allpool on andmestruktuuri puuliigid:

1. Üldine puu

Kui puu hierarhias ei seata mingeid piiranguid, nimetatakse puud üldiseks puuks. Igas sõlmes võib üldpuus olla lõpmatu arv lapsi. Puu on kõigi teiste puude superkomplekt.

2. Binaarne puu

Binaarne puu on selline puu, kus iga vanema jaoks võib leida kõige rohkem kaks last. Lapsi tuntakse vasaku ja parema lapsena. See on populaarsem kui enamik teisi puid. Kui binaarses puus rakendatakse teatavaid piiranguid ja omadusi, kasutatakse ka mitmeid teisi, näiteks AVL-puu, BST (binaarne otsingupuu), RBT-puu jne. Edasi liikudes selgitame kõiki neid stiile üksikasjalikult.

3. Binaarne otsingupuu

Binaarne otsimispuu (BST) on binaarne puulaiend, millel on mitu valikulist piirangut. Sõlme vasakpoolse lapse väärtus BST-s peaks olema väiksem või võrdne vanema väärtusega ja parem lapse väärtus peaks alati olema suurem või võrdne vanema väärtusega. See binaarse otsingupuu omadus muudab selle ideaalseks otsingutoimingute jaoks, kuna saame igas sõlmes täpselt kindlaks teha, kas väärtus on vasakus või paremas alampuus. Seetõttu on otsingupuu nimetatud.

4. AVL-puu

AVL-puu on binaarne otsingupuu ise tasakaalustav. Leiutajate Adelson-Velshi ja Landise nimel antakse nimi AVL. See oli esimene dünaamiliselt tasakaalus puu. Tasakaalutegur eraldatakse AVL-puu igale sõlmele vastavalt sellele, kas puu on tasakaalus või mitte. Laste sõlmede kõrgus on maksimaalselt 1. AVL viinapuu. AVL-puus on õige tasakaalutegur 1, 0 ja -1. Kui puul on uus sõlm, siis pööratakse seda puu tasakaalustamiseks. Seejärel pööratakse seda. Tavalised toimingud, näiteks vaatamine, sisestamine ja eemaldamine, võtavad AVL-puus O (log n) aega. Enamasti rakendatakse seda otsingute toimingutega töötamisel.

5. Punane-must puu

Teine selline automaatne tasakaalustamine on punane-must. Punane-must nimi on antud seetõttu, et punaselt mustal puul on vastavalt punase-musta puu omadustele igale sõlmele kas punane või must. See säilitab metsa tasakaalu. Kuigi see puu pole täielikult tasakaalustatud puu, võtab otsimistoiming ainult O (log n) aega. Kui uued sõlmed lisatakse punasesse musta puusse, siis pööratakse neid uuesti, et säilitada punase-musta puu omadused.

6. N-ary puu

Seda tüüpi puudes võib maksimaalselt olla laste arv, kellel võib olla sõlme. N. Binaarne puu on kaheaastane puu, kuna maksimaalselt 2 last igas binaarses puusõlmes. Täielik N-kujuline puu on puu, kus sõlme lapsed on kas 0 või N.

Puu eelised

Nüüd mõistame puu eeliseid:

  • Puu kajastub andmete struktuurses ühenduses.
  • Puu kasutatakse hierarhias.
  • See pakub tõhusat otsingu- ja sisestamisprotseduuri.
  • Puud on painduvad. See võimaldab alamõõnesid minimaalse vaevaga ümber paigutada.

Järeldus - puude tüübid andmestruktuuris

Nii et selles artiklis nägime, mis on puustruktuur, millised on andmestruktuuris erinevad puuliigid ja selle eelised. Loodetavasti saite aimu andmestruktuuris levinud puudest.

Soovitatavad artiklid

See on juhend puutüüpide kohta andmestruktuuris. Siin arutame, mis on puud, 6 tüüpi puud andmestruktuuris, koos eelistega. Lisateavet leiate ka meie muudest seotud artiklitest -

  1. AWS Data Pipeline
  2. Oracle'i andmete ladustamine
  3. Mitmemõõtmeline andmebaas
  4. Andmestruktuur Java intervjuu küsimused

Kategooria:

Suured andmed