Tässä opetusohjelmassa opit puun datarakenteesta. Opit myös erityyppisistä puista ja puun termeistä.
Puu on epälineaarinen hierarkkinen tietorakenne, joka koostuu reunoilla yhdistetyistä solmuista.
Puu
Miksi Tree Data Structure?
Muut tietorakenteet, kuten taulukot, linkitetty luettelo, pino ja jono, ovat lineaarisia tietorakenteita, jotka tallentavat tietoja peräkkäin. Minkä tahansa operaation suorittamiseksi lineaarisessa datarakenteessa ajan monimutkaisuus kasvaa datakoon kasvaessa. Mutta se ei ole hyväksyttävää nykypäivän laskennallisessa maailmassa.
Erilaiset puutietorakenteet mahdollistavat nopeamman ja helpomman pääsyn tietoihin, koska se on epälineaarinen tietorakenne.
Puutermit
Solmu
Solmu on entiteetti, joka sisältää avaimen tai arvon ja osoittaa sen alisolmuihin.
Kunkin polun viimeisiä solmuja kutsutaan lehtisolmuiksi tai ulkoisiksi solmuiksi, jotka eivät sisällä linkkiä / osoitinta lapsisolmuihin.
Solmua, jolla on ainakin alisolmu, kutsutaan sisäiseksi solmuksi .
Reuna
Se on linkki kahden solmun välillä.
Puun solmut ja reunat
Root
Se on puun ylin solmu.
Solmun korkeus
Solmun korkeus on reunojen lukumäärä solmusta syvimpään lehteen (eli pisin polku solmusta lehtisolmuun).
Solmun syvyys
Solmun syvyys on reunojen määrä juuresta solmuun.
Puun korkeus
Puun korkeus on juurisolmun korkeus tai syvimmän solmun syvyys.
Jokaisen puun solmun korkeus ja syvyys
Solmun aste
Solmun aste on kyseisen solmun haarojen kokonaismäärä.
Metsä
Erillisten puiden kokoelmaa kutsutaan metsäksi.
Metsän luominen puusta
Voit luoda metsän leikkaamalla puun juuren.
Puun tyypit
- Binaarinen puu
- Binaarinen hakupuu
- AVL-puu
- B-puu
Puun kulku
Jos haluat suorittaa minkä tahansa puun toiminnon, sinun on saavutettava tietty solmu. Puun läpi kulkeva algoritmi auttaa vierailemaan vaaditussa puun solmussa.
Jos haluat lisätietoja, käy puiden läpi.
Puun sovellukset
- Binaarisia hakupuita (BST) käytetään tarkistamaan nopeasti, onko elementti joukossa vai ei.
- Kasa on eräänlainen puu, jota käytetään kasan lajittelussa.
- Muokattua versiota puusta nimeltä Tries käytetään nykyaikaisissa reitittimissä reititystietojen tallentamiseen.
- Suosituimmat tietokannat käyttävät B-puita ja T-puita, jotka ovat muunnelmia puurakenteesta, jonka olemme oppineet yllä tallentamaan tietojaan
- Kääntäjät käyttävät syntaksipuuta vahvistaakseen jokaisen kirjoittamasi ohjelman syntaksin.
