Lisääminen binäärihakupuuhun
Rakentakaa binäärihakupuu.
Lisääminen binäärihakupuuhun on ilmainen C Academy-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu C Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C Academy-kurssilla on yhteensä 4 oppituntia.
Binäärihakupuun järjestyssääntö
Binäärihakupuu (Binary Search Tree, BST) on binääripuu, jota koskee yksi lisäsääntö: jokaisen solmun vasemman osapuun kaikki arvot ovat pienempiä ja oikean osapuun kaikki arvot suurempia.
Tämän järjestyksen ansiosta haku, lisäys ja poisto voidaan tehdä puun korkeuteen verrannollisessa ajassa.
Mihin arvo kuuluu
Lisäys aloitetaan juuresta ja arvoja vertaillaan. Jos uusi arvo on pienempi, siirrytään vasemmalle; jos suurempi, siirrytään oikealle.
Tätä jatketaan, kunnes saavutetaan tyhjä paikka (NULL), johon uusi solmu kuuluu.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/create_node-apufunktio
Lisäys muodostaa uusia lehtisolmuja, joten käytämme uudelleen konstruktoria, joka varaa ja alustaa solmun.
Molempien lasten arvoksi asetetaan aluksi NULL, koska juuri lisätty solmu on aina lehti.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Rekursiivinen lisäys
Selkein tapa toteuttaa lisäys on rekursiivinen funktio, joka palauttaa osapuun juuren, joka saattaa olla uusi.
Jos osapuu on tyhjä, palautetaan uusi solmu. Muussa tapauksessa jatketaan rekursiivisesti vasemmalla tai oikealla ja liitetään tulos takaisin, minkä jälkeen palautetaan muuttumaton juuri.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}Miksi juuri palautetaan
Osapuun juuren palauttaminen antaa isäntäsolmulle mahdollisuuden liittää linkin uudelleen yhdellä rivillä: root->left = insert(root->left, v).
Jos osapuu oli tyhjä, palautetusta uudesta solmusta tulee lapsi. Jos se ei ollut tyhjä, palautetaan sama juuri ja linkki säilyy ennallaan.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);Kaksoiskappaleiden käsittely
Oikean binäärihakupuun on päätettävä, miten samat arvot käsitellään. Yleinen vaihtoehto on ohittaa kaksoiskappaleet, kuten insert-funktiomme tekee, koska yhtäsuuruustapaukselle ei ole omaa haaraa.
Vaihtoehtoja ovat esimerkiksi solmukohtaisen lukumäärän tallentaminen tai kaksoiskappaleiden ohjaaminen aina samalle puolelle.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */Binäärihakupuun rakentaminen
Arvojen lisäämisjärjestys vaikuttaa muodostuvan puun rakenteeseen.
Tässä lisäämme useita lukuja ja tulostamme juuren välittömät lapset varmistaaksemme, että järjestyssääntö pätee.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return create_node(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}Iteratiivinen lisäys
Lisäyksen voi tehdä myös ilman rekursiota. Kuljemme osoittimen avulla alaspäin ja pidämme isäntäsolmun muistissa, kunnes löydämme tyhjän paikan.
Sitten liitämme uuden solmun kyseisen isäntäsolmun oikealle tai vasemmalle puolelle.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}Lisäysjärjestys muovaa puun
Arvojen 1,2,3,4,5 lisääminen järjestyksessä tuottaa surkastuneen puun, joka näyttää linkitetyltä listalta ja jonka korkeus vastaa solmujen määrää.
Lisääminen tasapainoisessa järjestyksessä pitää korkeuden lähellä arvoa log(n). Tasapaino vaikuttaa suoraan haun nopeuteen.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Lisäyksen kustannus
Jokainen lisäys kulkee yhtä juuresta lehteen johtavaa polkua pitkin, joten sen työmäärä on verrannollinen puun korkeuteen.
Tasapainoisessa puussa kyse on suunnilleen log(n):stä vertailuja; surkastuneessa puussa vertailuja voi olla n. Siksi itseään tasapainottavia puita tarvitaan.
Täydellinen insert-esimerkki
Tämä ohjelma lisää arvoja ja laskee sitten solmut varmistaakseen, että puuhun tallennettiin viisi eri arvoa ja että kaksoiskappale ohitettiin.
Kaksoiskappale 10 ei kasvata lukumäärää, koska insert ohittaa yhtä suuret arvot.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}Pikatarkistus
Päätelkää, miten lisääminen toimii.
Kertaus
Binäärihakupuun lisäämisessä uutta arvoa verrataan jokaiseen solmuun: pienempi arvo ohjataan vasemmalle ja suurempi oikealle, kunnes tyhjä paikka löytyy.
Rekursiivinen muoto palauttaa alipuun juuren, jotta pääsolmu voi liittää linkit siististi uudelleen. Lisäämisen kustannus riippuu puun korkeudesta, joten lisäämisjärjestyksellä on merkitystä.
Opi C tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 39
- Oppitunnit
- 144
Usein kysytyt kysymykset
Onko oppitunti ”Lisääminen binäärihakupuuhun” ilmainen?
Kyllä – oppitunnin ”Lisääminen binäärihakupuuhun” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko C Academy-kurssin, päivitä CoddyKit PROhon. C Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Lisääminen binäärihakupuuhun”?
Rakentakaa binäärihakupuu. Harjoittelet C Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni C Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin C Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Lisääminen binäärihakupuuhun”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä C Academy-oppitunnilla?
Kyllä. Jokainen C Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Puun solmut ja rakenne
- Lisääminen binäärihakupuuhun
- Läpikäynnit
- Haku ja vapauttaminen