Sett inn i et BST
Bygg et binært søketre.
Sett inn i et BST er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.
Sorteringsregelen for BST
Et Binary Search Tree (BST) er et binærtre med én ekstra regel: For hver node er alle verdiene i det venstre deltreet mindre, og alle verdiene i det høyre deltreet større.
Denne sorteringen gjør det mulig å søke, sette inn og slette på tid som er proporsjonal med høyden til treet.
Hvor en verdi hører hjemme
Ved innsetting starter vi ved roten og sammenligner. Hvis den nye verdien er mindre, går vi til venstre. Hvis den er større, går vi til høyre.
Vi gjentar dette til vi finner en tom plass (NULL), som er akkurat der den nye noden hører hjemme.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/Hjelpefunksjonen create_node
Innsetting oppretter nye bladnoder, så vi gjenbruker en konstruktør som allokerer og initialiserer en node.
Begge barna starter som NULL, fordi en nylig satt inn node alltid er et blad.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Rekursiv innsetting
Den ryddigste måten å sette inn på er rekursivt, og funksjonen returnerer roten til det eventuelt nye deltreet.
Hvis deltreet er tomt, returnerer vi en ny node. Ellers går vi rekursivt til venstre eller høyre, kobler resultatet tilbake og returnerer deretter den uendrede roten.
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 */
}Hvorfor roten returneres
Ved å returnere roten til deltreet kan foreldrenoden koble lenken tilbake på én linje: root->left = insert(root->left, v).
Hvis deltreet var tomt, blir den returnerte nye noden barnet. Hvis det ikke var tomt, returneres den samme roten, og lenken forblir uendret.
/* 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);Håndtere duplikater
Reelle BST-er må bestemme hva som skal skje med like verdier. Et vanlig valg er å ignorere duplikater, slik vår insert gjør ved å ikke ha en gren for tilfellet med lik verdi.
Alternativer er å lagre en telling per node eller alltid sende duplikater til én bestemt side.
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 */Bygge et BST
Når vi setter inn en sekvens med verdier, får vi et tre med en struktur som avhenger av innsettingsrekkefølgen.
Her setter vi inn flere tall og skriver ut rotens umiddelbare barn for å bekrefte at sorteringsregelen gjelder.
#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;
}En iterativ innsetting
De kan også sette inn uten rekursjon. Vi går nedover med en peker og husker foreldrenoden til vi finner en tom plass.
Deretter kobler vi den nye noden til riktig side av foreldrenoden.
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;
}Innsettingsrekkefølgen former treet
Hvis vi setter inn 1,2,3,4,5 i sortert rekkefølge, får vi et degenerert tre som ligner en lenket liste, med en høyde som tilsvarer antallet.
Ved å sette inn i en balansert rekkefølge holder vi høyden nær log(n). Balanseringen påvirker søkehastigheten direkte.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Kostnaden ved innsetting
Hver innsetting følger én vei fra roten til et blad, så arbeidet er proporsjonalt med høyden til treet.
For et balansert tre er dette omtrent log(n) sammenligninger, mens det kan være n for et degenerert tre. Derfor finnes det selvbalanserende trær.
Fullstendig innsettingsdemo
Dette programmet setter inn verdier og teller deretter nodene for å bekrefte at fem ulike verdier ble lagret, mens en duplikatverdi ble ignorert.
Duplikatet 10 øker ikke antallet, fordi insert forkaster like verdier.
#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;
}Rask sjekk
Resonner rundt oppførselen ved innsetting.
Oppsummering
Ved innsetting i et BST sammenlignes den nye verdien med hver node. Programmet går til venstre for mindre verdier og til høyre for større, helt til en tom plass blir funnet.
Den rekursive formen returnerer roten til deltreet, slik at forelderen kan koble pekerne til igjen på en ryddig måte. Kostnaden ved innsetting avhenger av høyden på treet, så rekkefølgen verdiene settes inn i, har betydning.
Lær deg C med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 39
- Leksjoner
- 144
Ofte stilte spørsmål
Er leksjonen «Sett inn i et BST» gratis?
Ja – hele teksten i «Sett inn i et BST» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Sett inn i et BST»?
Bygg et binært søketre. Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med C Academy?
Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Sett inn i et BST»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?
Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Tre-noder og struktur
- Sett inn i et BST
- Traverseringer
- Søk og frigjøring