C Academy · Pelajaran

Menyisipkan ke dalam BST

Bina pepohon carian binari.

Pelajaran 2 daripada 413 langkah

Menyisipkan ke dalam BST ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Peraturan Susunan BST

Pepohon Carian Binari (BST) ialah pokok binari dengan satu peraturan tambahan: bagi setiap nod, semua nilai dalam subpokok kirinya lebih kecil, manakala semua nilai dalam subpokok kanannya lebih besar.

Susunan ini membolehkan kita mencari, memasukkan dan memadam dalam masa yang berkadar dengan ketinggian pokok.

Tempat Sesuatu Nilai Berada

Untuk memasukkan nilai, kita bermula pada akar dan membuat perbandingan. Jika nilai baharu lebih kecil, kita bergerak ke kiri; jika lebih besar, kita bergerak ke kanan.

Kita mengulanginya sehingga mencapai ruang kosong (NULL), iaitu tempat sebenar nod baharu itu berada.

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

Pembantu create_node

Pemasukan membina nod daun baharu, jadi kita menggunakan semula pembina yang memperuntukkan dan memulakan nod.

Kedua-dua anak bermula sebagai NULL kerana nod yang baru dimasukkan sentiasa ialah daun.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

Pemasukan Rekursif

Pemasukan yang paling kemas adalah secara rekursif dan mengembalikan akar subpokok yang mungkin baharu.

Jika subpokok itu kosong, kita mengembalikan nod baharu. Jika tidak, kita melakukan rekursi ke kiri atau kanan dan menyambungkan semula hasilnya, kemudian mengembalikan akar yang tidak berubah.

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 */
}

Mengapa Akar Dikembalikan

Mengembalikan akar subpokok membolehkan induk menyambungkan semula pautan dalam satu baris: root->left = insert(root->left, v).

Apabila subpokok kosong, nod baharu yang dikembalikan menjadi anak. Jika tidak, akar yang sama dikembalikan dan pautannya tidak berubah.

/* 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);

Mengendalikan Nilai Pendua

BST sebenar mesti menentukan perkara yang perlu dilakukan terhadap nilai yang sama. Pilihan biasa ialah mengabaikan pendua, seperti yang dilakukan oleh insert kita kerana tiada cabang untuk kes yang sama.

Alternatifnya termasuk menyimpan kiraan bagi setiap nod atau sentiasa menghantar pendua ke satu sisi tertentu.

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 */

Membina BST

Memasukkan jujukan nilai menghasilkan pokok yang bentuknya bergantung pada susunan pemasukan.

Di sini kita memasukkan beberapa nombor dan mencetak anak serta-merta bagi akar untuk mengesahkan bahawa peraturan susunan dipatuhi.

#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;
}

Pemasukan Berlelaran

Anda juga boleh memasukkan tanpa rekursi. Kita bergerak ke bawah dengan penuding sambil mengingati induk sehingga menemui ruang kosong.

Kemudian kita menyambungkan nod baharu kepada sisi yang betul pada induk tersebut.

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;
}

Susunan Pemasukan Membentuk Pokok

Memasukkan 1,2,3,4,5 mengikut susunan terisih menghasilkan pokok merosot yang kelihatan seperti senarai terpaut, dengan ketinggian yang sama dengan kiraan.

Memasukkan nilai dalam susunan seimbang mengekalkan ketinggian hampir kepada log(n). Keseimbangan memberi kesan langsung kepada kelajuan carian.

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

Kos Pemasukan

Setiap pemasukan mengikuti satu laluan dari akar ke daun, jadi kerja yang dilakukan berkadar dengan ketinggian pokok.

Bagi pokok seimbang, jumlahnya kira-kira log(n) perbandingan; bagi pokok merosot, jumlahnya boleh menjadi n. Inilah sebabnya pokok pengimbangan kendiri wujud.

Demo Sisipan Lengkap

Program ini menyisipkan nilai, kemudian mengira nod untuk mengesahkan bahawa lima nilai berbeza telah disimpan dan satu pendua diabaikan.

Pendua 10 tidak menambah kiraan kerana insert menggugurkan nilai yang sama.

#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;
}

Semakan Pantas

Fikirkan tentang tingkah laku sisipan.

Jawab dalam pelajaran interaktif

Rumusan

Sisipan BST membandingkan nilai baharu dengan setiap nod, bergerak ke kiri untuk nilai yang lebih kecil dan ke kanan untuk nilai yang lebih besar, sehingga ruang kosong ditemui.

Bentuk rekursif mengembalikan akar subpokok supaya nod induk boleh menyambungkan semula pautan dengan kemas. Kos sisipan meningkat mengikut ketinggian pepohon, jadi susunan sisipan penting.

Percuma untuk bermula

Pelajari C dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 39
Pelajaran: 144

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Menyisipkan ke dalam BST” percuma?

Ya — teks penuh “Menyisipkan ke dalam BST” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Menyisipkan ke dalam BST”?

Bina pepohon carian binari. Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Menyisipkan ke dalam BST” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke C Academy