Wstawianie do BST
Zbuduje Pan/Pani binarne drzewo wyszukiwania.
Wstawianie do BST to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Reguła uporządkowania BST
Binary Search Tree (BST) to drzewo binarne z dodatkową regułą: dla każdego węzła wszystkie wartości w jego lewym poddrzewie są mniejsze, a wszystkie wartości w prawym poddrzewie — większe.
To uporządkowanie pozwala wyszukiwać, wstawiać i usuwać elementy w czasie proporcjonalnym do wysokości drzewa.
Gdzie należy umieścić wartość
Aby wstawić wartość, zaczynamy od korzenia i porównujemy wartości. Jeśli nowa wartość jest mniejsza, przechodzimy w lewo; jeśli większa — w prawo.
Powtarzamy te czynności aż do napotkania pustego miejsca (NULL), czyli dokładnie tam, gdzie należy umieścić nowy węzeł.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/Funkcja pomocnicza create_node
Wstawianie tworzy nowe węzły liści, dlatego ponownie wykorzystujemy konstruktor, który alokuje i inicjalizuje węzeł.
Oba dzieci zaczynają od wartości NULL, ponieważ świeżo wstawiony węzeł zawsze jest liściem.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Rekurencyjne wstawianie
Najczytelniejsza implementacja wstawiania jest rekurencyjna i zwraca korzeń danego poddrzewa (który może być nowym węzłem).
Jeśli poddrzewo jest puste, zwracamy nowy węzeł. W przeciwnym razie wywołujemy funkcję rekurencyjnie dla lewej lub prawej strony, ponownie dołączamy wynik, a następnie zwracamy niezmieniony korzeń.
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 */
}Dlaczego zwracamy korzeń
Zwrócenie korzenia poddrzewa pozwala rodzicowi ponownie dołączyć odwołanie w jednym wierszu: root->left = insert(root->left, v).
Jeśli poddrzewo było puste, zwrócony nowy węzeł staje się dzieckiem. Jeśli nie było puste, zwracamy ten sam korzeń, a odwołanie pozostaje niezmienione.
/* 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);Obsługa duplikatów
Rzeczywiste drzewa BST muszą określać, co zrobić z równymi wartościami. Częstym rozwiązaniem jest ignorowanie duplikatów, tak jak robi to nasza funkcja insert, która nie ma osobnej gałęzi dla równego przypadku.
Alternatywy obejmują przechowywanie licznika w każdym węźle albo konsekwentne kierowanie duplikatów na jedną stronę.
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 */Budowanie BST
Wstawienie sekwencji wartości tworzy drzewo, którego kształt zależy od kolejności wstawiania.
W tym przykładzie wstawiamy kilka liczb i wyświetlamy bezpośrednie dzieci korzenia, aby potwierdzić, że reguła uporządkowania jest zachowana.
#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;
}Iteracyjne wstawianie
Wstawianie można również wykonać bez rekurencji. Schodzimy w dół drzewa za pomocą wskaźnika i zapamiętujemy rodzica, aż znajdziemy puste miejsce.
Następnie dołączamy nowy węzeł po właściwej stronie tego rodzica.
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;
}Kolejność wstawiania kształtuje drzewo
Wstawienie wartości 1,2,3,4,5 w kolejności rosnącej tworzy zdegenerowane drzewo przypominające listę jednokierunkową, którego wysokość jest równa liczbie elementów.
Wstawianie w kolejności zapewniającej równowagę utrzymuje wysokość w pobliżu log(n). Równowaga bezpośrednio wpływa na szybkość wyszukiwania.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Koszt wstawiania
Każde wstawianie przemierza jedną ścieżkę od korzenia do liścia, więc wymaga pracy proporcjonalnej do wysokości drzewa.
W przypadku drzewa zrównoważonego jest to około log(n) porównań, a w przypadku drzewa zdegenerowanego może wynosić n. Dlatego istnieją drzewa samobalansujące.
Pełny przykład wstawiania
Ten program wstawia wartości, a następnie zlicza węzły, aby potwierdzić, że zapisano pięć różnych wartości, a duplikat został zignorowany.
Duplikat 10 nie zwiększa liczby elementów, ponieważ insert pomija wartości równe.
#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;
}Szybkie sprawdzenie
Przeanalizuj działanie wstawiania.
Podsumowanie
Wstawianie do BST porównuje nową wartość z każdym węzłem, przechodząc w lewo dla wartości mniejszych i w prawo dla większych, aż znajdzie puste miejsce.
Wersja rekurencyjna zwraca korzeń poddrzewa, aby rodzic mógł poprawnie ponownie podłączyć odnośniki. Koszt wstawiania rośnie wraz z wysokością drzewa, dlatego kolejność wstawiania ma znaczenie.
Często zadawane pytania
Czy lekcja „Wstawianie do BST” jest bezpłatna?
Tak — pełny tekst „Wstawianie do BST” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Wstawianie do BST”?
Zbuduje Pan/Pani binarne drzewo wyszukiwania. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Wstawianie do BST”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.