0Pricing
C Academy · Pelajaran

Menyisipkan ke BST

Bangun pohon pencarian biner.

Menyisipkan ke BST adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.

Aturan Pengurutan BST

Pohon Pencarian Biner (BST) adalah pohon biner dengan satu aturan tambahan: untuk setiap simpul, semua nilai di subpohon kirinya lebih kecil, sedangkan semua nilai di subpohon kanannya lebih besar.

Pengurutan ini memungkinkan kita mencari, menyisipkan, dan menghapus dalam waktu yang sebanding dengan tinggi pohon.

Tempat Sebuah Nilai Berada

Untuk menyisipkan, kita mulai dari akar dan melakukan perbandingan. Jika nilai baru lebih kecil, kita bergerak ke kiri; jika lebih besar, kita bergerak ke kanan.

Kita mengulanginya sampai mencapai tempat kosong (NULL), tepat di situlah simpul baru harus ditempatkan.

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

Pembantu create_node

Penyisipan membuat simpul daun baru, jadi kita menggunakan kembali konstruktor yang mengalokasikan dan menginisialisasi sebuah simpul.

Kedua anak diawali dengan NULL karena simpul yang baru disisipkan selalu merupakan 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;
}

Penyisipan Rekursif

Penyisipan yang paling rapi dilakukan secara rekursif dan mengembalikan akar subpohon yang mungkin baru.

Jika subpohon kosong, kita mengembalikan simpul baru. Jika tidak, kita melakukan rekursi ke kiri atau kanan dan memasang kembali hasilnya, lalu 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 Mengembalikan Akar

Mengembalikan akar subpohon memungkinkan induknya memasang kembali hubungan tersebut dalam satu baris: root->left = insert(root->left, v).

Saat subpohon kosong, simpul baru yang dikembalikan menjadi anaknya. Saat subpohon tidak kosong, akar yang sama dikembalikan dan hubungannya 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);

Menangani Nilai Duplikat

BST nyata harus menentukan tindakan terhadap nilai yang sama. Pilihan umum adalah mengabaikan duplikat, seperti yang dilakukan insert kita karena tidak memiliki cabang untuk kasus nilai yang sama.

Alternatifnya mencakup menyimpan jumlah pada setiap simpul atau selalu mengarahkan duplikat ke salah satu sisi.

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

Membangun BST

Menyisipkan suatu urutan nilai menghasilkan pohon yang bentuknya bergantung pada urutan penyisipan.

Di sini kita menyisipkan beberapa angka dan mencetak anak langsung dari akar untuk memastikan aturan pengurutan tetap berlaku.

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

Penyisipan Iteratif

Anda juga dapat menyisipkan tanpa rekursi. Kita bergerak turun dengan sebuah penunjuk sambil mengingat induknya, sampai menemukan tempat kosong.

Kemudian kita memasang simpul baru pada sisi yang tepat dari 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;
}

Urutan Penyisipan Membentuk Pohon

Menyisipkan 1,2,3,4,5 dalam urutan terurut menghasilkan pohon merosot yang menyerupai senarai berantai, dengan tinggi yang sama dengan jumlah simpul.

Menyisipkan dalam urutan seimbang menjaga tinggi tetap mendekati log(n). Keseimbangan secara langsung memengaruhi kecepatan pencarian.

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

Biaya Penyisipan

Setiap penyisipan menelusuri satu jalur dari akar ke daun, sehingga pekerjaannya sebanding dengan tinggi pohon.

Untuk pohon seimbang, nilainya kira-kira log(n) perbandingan; untuk pohon merosot, nilainya dapat mencapai n. Inilah alasan pohon yang menyeimbangkan diri diperlukan.

Demo Penyisipan Lengkap

Program ini menyisipkan nilai, lalu menghitung jumlah simpul untuk memastikan lima nilai berbeda tersimpan dan satu duplikat diabaikan.

Duplikat 10 tidak menambah jumlah karena insert mengabaikan 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;
}

Pemeriksaan Singkat

Bernalarlah tentang perilaku penyisipan.

Ringkasan

Penyisipan BST membandingkan nilai baru dengan setiap simpul, bergerak ke kiri untuk nilai yang lebih kecil dan ke kanan untuk nilai yang lebih besar, hingga menemukan tempat kosong.

Bentuk rekursif mengembalikan akar subpohon agar simpul induk dapat menyambungkan kembali tautan dengan rapi. Biaya penyisipan bertambah sesuai tinggi pohon, sehingga urutan penyisipan berpengaruh.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Menyisipkan ke BST” gratis?

Ya — teks lengkap “Menyisipkan ke BST” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Menyisipkan ke BST”?

Bangun pohon pencarian biner. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C Academy?

Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.

Berapa lama pelajaran “Menyisipkan ke BST” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Node dan Struktur Pohon
  2. Menyisipkan ke BST
  3. Penelusuran
  4. Mencari dan Membebaskan Memori
← Kembali ke C Academy