Johdatus puihin tietorakenteessa
Ennen kuin ymmärrät puurakennetyypit tietorakenteessa, tutkitaan ensin puita tietorakenteessa. Tietokonekentän puuta kutsutaan myös reaalimaailman puuksi, mutta ero todellisen maailman ja laskentakentän puun välillä on, että se visualisoidaan ylösalaisin ja juurella sen päällä ja haarautuu juurista puun lehtiin. Eri reaalimaailman sovelluksissa käytetään puun datarakennetta, koska se voi osoittaa eri solmujen väliset suhteet vanhemman ja lapsen hierarkiaan. Tämän vuoksi sitä kutsutaan myös hierarkkiseksi tietorakenteeksi. Se on suosituin tapa yksinkertaistaa ja nopeuttaa hakua ja lajittelua. Sitä pidetään yhtenä vahvimmista ja edistyneimmistä tietorakenteista. Puu on epälineaarisen tietorakenteen esitys. Puu voidaan näyttää käyttämällä erilaisia käyttäjän määrittelemiä tai primitiivisiä tietotyyppejä. Puun toteuttamiseen voidaan käyttää taulukkoja, luokkien liitettyjä luetteloita tai muunlaisia tietorakenteita. Se on ryhmä solmuja, jotka ovat toisiinsa liittyviä. Solmut on kiinnitetty reunoihin osoittamaan suhdetta.
Suhteet puussa: Edellä annetussa kaaviossa P on puun juuri myös P on Q: n emo, R ja S. Q on P. lapsi. Tästä syystä Q, R ja S ovat sisaruksia. P on A: n, B: n, C: n, D: n ja E: n isovanhempi,
Mitä puut ovat?
Puu on hierarkkinen tietorakenne, joka tallentaa tiedot luonnollisesti hierarkkisella tavalla. Puun tietorakenne on yksi tehokkaimmista ja kypsimmistä. Reunojen yhdistämät solmut on esitetty.
Puun ominaisuudet: Jokaisella puulla on tietty juurisolmu. Juurisolmu voi ylittää jokaisen puusolmun. Sitä kutsutaan juuri, koska puu oli ainoa juuri. Jokaisella lapsella on vain yksi vanhempi, mutta vanhemmalla voi olla useita lapsia.
Puutyypit tietorakenteessa
Alla on tyypit puurakenteesta tietorakenteessa:
1. Yleinen puu
Jos puun hierarkiaan ei aseteta rajoituksia, puuta kutsutaan yleiseksi puuksi. Jokaisella solmulla voi olla ääretön määrä lapsia Yleisessä puussa. Puu on kaikkien muiden puiden superjoukko.
2. Binaarinen puu
Binaaripuu on sellainen puu, josta kustakin vanhemmasta löytyy eniten kaksi lasta. Lapset tunnetaan vasen ja oikea lapsi. Tämä on suositumpi kuin useimmat muut puut. Kun binaaripuussa sovelletaan tiettyjä rajoituksia ja ominaisuuksia, käytetään myös useita muita, kuten AVL-puuta, BST (binaarinen hakupuu), RBT-puuta jne. Kun siirrymme eteenpäin, selitämme kaikki nämä tyylit yksityiskohtaisesti.
3. Binaarinen hakupuu
Binary Search Tree (BST) on binaarinen puun laajennus, jolla on useita valinnaisia rajoituksia. Solmun vasemman lapsiarvon tulisi BST: ssä olla pienempi tai yhtä suuri kuin vanhemman arvo ja oikean lapsen arvon tulisi aina olla suurempi tai yhtä suuri kuin vanhemman arvo. Tämä binaarinen hakupuu -ominaisuus tekee siitä ihanteellisen hakutoiminnoille, koska voimme tarkistaa kullakin solmulla tarkalleen, onko arvo vasemmassa vai oikeassa alapuussa. Siksi hakupuu on nimetty.
4. AVL-puu
AVL-puu on binaarinen hakupuu, joka tasapainottuu. Keksijöiden Adelson-Velshin ja Landisin puolesta annetaan nimi AVL. Tämä oli ensimmäinen puu, joka tasapainotti dynaamisesti. Tasapainotuskerroin allokoidaan jokaiselle AVL-puun solmulle sen perusteella, onko puu tasapainossa vai ei. Solmun lasten korkeus on korkeintaan 1. AVL viiniköynnös. AVL-puussa oikea tasapainotuskerroin on 1, 0 ja -1. Jos puulla on uusi solmu, sitä kierretään sen varmistamiseksi, että puu on tasapainossa. Sen jälkeen sitä käännetään. Yleiset toiminnot, kuten katseleminen, lisääminen ja poistaminen vievät O (log n) -aikaa AVL-puussa. Sitä käytetään enimmäkseen haut-operaatioiden kanssa.
5. Puna-musta puu
Toinen automaattisen tasapainottamisen puu on puna-musta. Puna-musta nimi annetaan, koska Puna-mustalla puulla on joko punainen tai musta maalattu jokaiselle solmulle puna-mustan puun ominaisuuksien mukaan. Se ylläpitää metsän tasapainoa. Vaikka tämä puu ei ole täysin tasapainossa oleva puu, etsintätoimenpide vie vain O (log n) -aikaa. Kun uudet solmut lisätään puna-musta puuhun, solmuja kierretään uudelleen punaisen mustan puun ominaisuuksien ylläpitämiseksi.
6. N-ary-puu
Tämän tyyppisessä puussa, jossa voi olla solmu, saa olla enintään lapsia. Binaarinen puu on kaksivuotinen puu, koska korkeintaan 2 lasta jokaisessa binaarisessa puusolmussa. Täydellinen N-ary-puu on puu, jossa solmun lapset ovat joko 0 tai N.
Puun edut
Nyt ymmärrämme puun edut:
- Puu heijastaa tiedon rakenteellisia yhteyksiä.
- Puua käytetään hierarkiaan.
- Se tarjoaa tehokkaan haku- ja lisäysmenettelyn.
- Puut ovat joustavia. Tämä mahdollistaa alapuiden siirtämisen pienellä vaivalla.
Johtopäätös - Puutyypit tietorakenteessa
Joten tässä artikkelissa olemme nähneet, mikä on puurakenne, mitkä ovat erityyppiset puut puurakenteessa ja sen eduista. Toivottavasti sinulla on käsitys joistakin yleisistä puista tietojen rakenteessa.
Suositellut artikkelit
Tämä on opas tietorakenteen puutyyppeihin. Tässä keskustellaan siitä, mikä on puita, kuusi tyyppistä puuta tietorakenteessa, ja sen etuja. Voit myös käydä läpi muiden aiheeseen liittyvien artikkeleidemme saadaksesi lisätietoja -
- AWS Data Pipeline
- Oracle-tietovarastointi
- Moniulotteinen tietokanta
- Tietorakenne Java-haastattelukysymykset