Luemme lineaariset tietorakenteet, kuten taulukon, linkitetyn listan, pinon ja jonon, joissa kaikki elementit on järjestetty peräkkäin. Erilaisia tietorakenteita käytetään erityyppisille tiedoille.
Tietorakenteen valinnassa otetaan huomioon joitakin tekijöitä:
Puu on myös yksi tietorakenteista, jotka edustavat hierarkkista dataa. Oletetaan, että haluamme näyttää työntekijät ja heidän asemansa hierarkkisessa muodossa, niin se voidaan esittää alla olevan kuvan mukaisesti:
Yllä oleva puu näyttää organisaatiohierarkia jostain yrityksestä. Yllä olevassa rakenteessa John on toimitusjohtaja yhtiöstä, ja Johnilla on kaksi suoraa raporttia nimeltä Steve ja Rohan . Steve on nimennyt kolme suoraa raporttia Lee, Bob, Ella missä Steve on johtaja. Bobilla on nimetty kaksi suoraa raporttia Tulee ja Emma . Emma on nimetty kaksi suoraa raporttia Tom ja Raj . Tomilla on yksi suora raportti nimeltä Laskuttaa . Tämä erityinen looginen rakenne tunnetaan nimellä a Puu . Sen rakenne on samanlainen kuin oikea puu, joten se on nimetty a Puu . Tässä rakenteessa juuri on huipulla ja sen oksat liikkuvat alaspäin. Siksi voidaan sanoa, että Tree-tietorakenne on tehokas tapa tallentaa dataa hierarkkisesti.
Ymmärretään joitakin puun tietorakenteen avainkohtia.
- Puutietorakenne määritellään kokoelmaksi objekteja tai kokonaisuuksia, jotka tunnetaan solmuina ja jotka on linkitetty toisiinsa edustamaan tai simuloimaan hierarkiaa.
- Puutietorakenne on epälineaarinen tietorakenne, koska se ei tallennu peräkkäin. Se on hierarkkinen rakenne, koska puun elementit on järjestetty useille tasoille.
- Puun tietorakenteessa ylin solmu tunnetaan juurisolmuna. Jokainen solmu sisältää jonkin verran dataa, ja data voi olla mitä tahansa tyyppiä. Yllä olevassa puurakenteessa solmu sisältää työntekijän nimen, joten tietotyyppi olisi merkkijono.
- Jokainen solmu sisältää tietoja ja linkin tai viittauksen muihin solmuihin, joita voidaan kutsua lapsiksi.
Jotkut puun tietorakenteessa käytetyt perustermit.
Tarkastellaan puurakennetta, joka näkyy alla:
Yllä olevassa rakenteessa jokainen solmu on merkitty jollain numerolla. Jokainen yllä olevassa kuvassa näkyvä nuoli tunnetaan nimellä a linkki kahden solmun välillä.
Puun tietorakenteen ominaisuudet
Puut luokitellaan eri luokkiin Tree-tietorakenteen ominaisuuksien perusteella.
Puun toteutus
Puutietorakenne voidaan luoda luomalla solmut dynaamisesti osoittimien avulla. Muistissa oleva puu voidaan esittää alla olevan kuvan mukaisesti:
Yllä oleva kuva esittää puutietorakenteen esityksen muistissa. Yllä olevassa rakenteessa solmu sisältää kolme kenttää. Toinen kenttä tallentaa tiedot; ensimmäinen kenttä tallentaa vasemman lapsen osoitteen ja kolmas kenttä oikean lapsen osoitteen.
Ohjelmoinnissa solmun rakenne voidaan määritellä seuraavasti:
struct node { int data; struct node *left; struct node *right; } Yllä oleva rakenne voidaan määrittää vain binääripuille, koska binääripuulla voi olla korkeintaan kaksi lasta ja yleisillä puilla voi olla enemmän kuin kaksi lasta. Yleisten puiden solmun rakenne olisi erilainen kuin binääripuu.
Puiden sovellukset
Seuraavat ovat puiden sovellukset:
Puun tietorakenteen tyypit
Seuraavat ovat puutietorakenteen tyypit:
Voi olla n alipuiden lukumäärä yleisessä puussa. Yleisessä puussa alipuut ovat järjestämättömiä, koska alipuun solmuja ei voi järjestää.
Jokaisella ei-tyhjällä puulla on alaspäin suuntautuva reuna, ja nämä reunat on yhdistetty solmuihin, jotka tunnetaan nimellä lapsisolmut . Juurisolmu on merkitty tasolla 0. Solmut, joilla on sama vanhempi, tunnetaan nimellä sisarukset .
Saat lisätietoja binääripuusta napsauttamalla alla olevaa linkkiä:
https://www.javatpoint.com/binary-tree
Jokaisen vasemman alipuun solmun tulee sisältää arvo, joka on pienempi kuin juurisolmun arvo, ja oikean alipuun jokaisen solmun arvon on oltava suurempi kuin juurisolmun arvo.
Solmu voidaan luoda käyttäjän määrittämän tietotyypin avulla rakenne, kuten alla:
struct node { int data; struct node *left; struct node *right; } Yllä oleva on solmurakenne, jossa on kolme kenttää: tietokenttä, toinen kenttä on solmutyypin vasen osoitin ja kolmas kenttä on solmutyypin oikea osoitin.
Saat lisätietoja binäärihakupuusta napsauttamalla alla olevaa linkkiä:
https://www.javatpoint.com/binary-search-tree
Se on yksi binääripuun tyypeistä, tai voimme sanoa, että se on muunnelma binäärihakupuusta. AVL-puu täyttää ominaisuuden binääripuu samoin kuin binäärihakupuu . Se on itsetasapainottava binäärihakupuu, jonka keksi Adelson Velsky Lindas . Tässä itsetasapainotuksella tarkoitetaan vasemman ja oikean alipuun korkeuksien tasapainottamista. Tämä tasapainotus mitataan tasapainottava tekijä .
Voimme pitää puuta AVL-puuna, jos puu noudattaa binäärihakupuuta sekä tasapainotustekijää. Tasapainotekijä voidaan määritellä vasemman alipuun ja oikean alipuun korkeuden välinen ero . Tasapainotustekijän arvon on oltava joko 0, -1 tai 1; siksi jokaisen AVL-puun solmun tasapainotustekijän arvon tulisi olla joko 0, -1 tai 1.
merkkijono n java
Saat lisätietoja AVL-puusta napsauttamalla alla olevaa linkkiä:
https://www.javatpoint.com/avl-tree
Puna-musta puu on binäärihakupuu. Red-Black-puun edellytyksenä on, että meidän pitäisi tietää binäärihakupuusta. Binäärihakupuussa vasemmanpuoleisen alipuun arvon tulee olla pienempi kuin kyseisen solmun arvon ja oikeanpuoleisen alipuun arvon tulee olla suurempi kuin kyseisen solmun arvo. Kuten tiedämme, binäärihaun aikamonimutkaisuus keskimääräisessä tapauksessa on log2n, paras tapaus on O(1) ja huonoin tapaus O(n).
Kun puulle suoritetaan mikä tahansa toiminto, haluamme puumme olevan tasapainossa niin, että kaikki toiminnot, kuten etsiminen, lisääminen, poistaminen jne., vievät vähemmän aikaa ja kaikki nämä toiminnot ovat aikamonimutkaisia. Hirsi2n.
Puna-musta puu on itsetasapainottava binäärihakupuu. AVL-puu on myös korkeutta tasapainottava binäärihakupuu miksi tarvitsemme punamusta puuta . AVL-puussa emme tiedä kuinka monta kiertoa puun tasapainottamiseen tarvittaisiin, mutta punamustassa puussa puun tasapainottamiseen tarvitaan enintään 2 kierrosta. Se sisältää yhden ylimääräisen bitin, joka edustaa joko solmun punaista tai mustaa väriä puun tasapainon varmistamiseksi.
Splay-puun tietorakenne on myös binäärihakupuu, jossa äskettäin käsitelty elementti sijoitetaan puun juuripaikkaan suorittamalla joitain kiertotoimintoja. Tässä, splaying tarkoittaa äskettäin käytettyä solmua. Se on a itse tasapainottuva binäärihakupuu, jolla ei ole eksplisiittistä tasapainoehtoa, kuten AVL puu.
Saattaa olla mahdollista, että leikkauspuun korkeus ei ole tasapainossa, eli sekä vasemman että oikean alipuun korkeus voi vaihdella, mutta leikkauspuun toiminnot ovat järjestyksessä rauhoittaa aika missä n on solmujen lukumäärä.
Splay-puu on tasapainoinen puu, mutta sitä ei voida pitää korkeustasapainoisena puuna, koska jokaisen toimenpiteen jälkeen suoritetaan kierto, joka johtaa tasapainoiseen puuhun.
Treap-tietorakenne tuli Tree- ja Heap-tietorakenteesta. Joten se sisältää sekä Tree- että Heap-tietorakenteiden ominaisuudet. Binaarihakupuussa jokaisen vasemman alipuun solmun on oltava yhtä suuri tai pienempi kuin juurisolmun arvo ja jokaisen oikean alipuun solmun on oltava yhtä suuri tai suurempi kuin juurisolmun arvo. Keon tietorakenteessa sekä oikea että vasen alipuu sisältävät suurempia avaimia kuin juuri; siksi voimme sanoa, että juurisolmu sisältää pienimmän arvon.
Treap-tietorakenteessa jokaisella solmulla on molemmat avain ja etusijalla jossa avain on johdettu binaarihakupuusta ja prioriteetti keon tietorakenteesta.
The Treap tietorakenne noudattaa kahta alla annettua ominaisuutta:
- Solmun oikea lapsi>=nykyinen solmu ja solmun vasen lapsi<=current node (binary tree)< li>
- Minkä tahansa alipuun lapsien on oltava suurempia kuin solmu (kasa)
B-puu on tasapainoinen m-tie puu missä m määrittää puun järjestyksen. Tähän mennessä olemme lukeneet, että solmu sisältää vain yhden avaimen, mutta b-puussa voi olla useampi kuin yksi avain ja enemmän kuin 2 lasta. Se säilyttää aina lajitellut tiedot. Binääripuussa on mahdollista, että lehtisolmut voivat olla eri tasoilla, mutta b-puussa kaikkien lehtien solmujen on oltava samalla tasolla.
Jos järjestys on m, solmulla on seuraavat ominaisuudet:
- Jokaisella b-puun solmulla voi olla maksimi m lapset
- Vähimmäislapsilla lehtisolmussa on 0 lasta, juurisolmussa vähintään 2 lasta ja sisäisessä solmussa on vähintään m/2 lasta. Esimerkiksi m:n arvo on 5, mikä tarkoittaa, että solmussa voi olla 5 lasta ja sisäisissä solmuissa enintään 3 lasta.
- Jokaisella solmulla on maksimiavaimet (m-1).
Juurisolmun tulee sisältää vähintään 1 avain ja kaikkien muiden solmujen tulee sisältää vähintään katto m/2 miinus 1 avaimet.