Selles õpetuses saate teada puuandmete struktuuri kohta. Samuti saate teada erinevat tüüpi puudest ja puudes kasutatavatest terminoloogiatest.
Puu on mittelineaarne hierarhiline andmestruktuur, mis koosneb servadega ühendatud sõlmedest.
Puu
Miks puu andmete struktuur?
Muud andmestruktuurid nagu massiivid, lingitud loend, virn ja järjekord on lineaarsed andmestruktuurid, mis salvestavad andmeid järjestikku. Lineaarses andmestruktuuris mis tahes toimingu tegemiseks suureneb aja keerukus koos andmete suuruse suurenemisega. Kuid see pole tänapäevases arvutusmaailmas vastuvõetav.
Erinevad puuandmete struktuurid võimaldavad andmetele kiiremat ja lihtsamat juurdepääsu, kuna tegemist on mittelineaarse andmestruktuuriga.
Puude terminoloogiad
Sõlm
Sõlm on üksus, mis sisaldab võtit või väärtust ja osutab selle alamsõlmedele.
Iga tee viimaseid sõlme nimetatakse lehesõlmedeks või välisteks sõlmedeks, mis ei sisalda linki / osutit alamsõlmedele.
Sõlme, millel on vähemalt alamsõlm, nimetatakse sisesõlmeks .
Edge
See on link kahe sõlme vahel.
Puu sõlmed ja servad
Juur
See on puu ülemine sõlm.
Sõlme kõrgus
Sõlme kõrgus on servade arv sõlmest sügavaima leheni (st pikim tee sõlmest lehesõlmeni).
Sõlme sügavus
Sõlme sügavus on servade arv juurest sõlmeni.
Puu kõrgus
Puu kõrgus on juursõlme kõrgus või sügavaima sõlme sügavus.
Iga puu sõlme kõrgus ja sügavus
Sõlme aste
Sõlme aste on selle sõlme harude koguarv.
Mets
Eraldatud puude kogu nimetatakse metsaks.
Metsa loomine puust
Metsa saate luua puu juure lõigates.
Puude tüübid
- Binaarne puu
- Binaarotsingupuu
- AVL puu
- B-puu
Puu läbimine
Puu mis tahes toimingu sooritamiseks peate jõudma konkreetse sõlmeni. Puu läbimise algoritm aitab puus vajalikku sõlme külastada.
Lisateabe saamiseks külastage puude läbimist.
Puu rakendused
- Binaarotsingu puid (BST) kasutatakse kiireks kontrollimiseks, kas element on komplektis olemas või mitte.
- Hunnik on omamoodi puu, mida kasutatakse kuhja sorteerimiseks.
- Puu modifitseeritud versiooni Tries kasutatakse tänapäevastes ruuterites marsruutimisteabe salvestamiseks.
- Kõige populaarsem andmebaas kasutab B-puid ja T-puid, mis on puukonstruktsiooni variandid, mida me õppisime nende andmete säilitamiseks
- Kompilaatorid kasutavad süntaksipuud iga teie kirjutatud programmi süntakside valideerimiseks.
