Mencari dan Membebaskan Memori
Temukan node dan bebaskan memori.
Mencari dan Membebaskan Memori adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 4 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.
Mencari dalam BST
Pencarian memanfaatkan aturan pengurutan. Pada setiap simpul, kita membandingkan target dengan nilai simpul tersebut dan bergerak hanya ke satu subpohon.
Karena kita membuang setengah simpul yang tersisa pada setiap langkah, biaya pencarian bertambah sesuai tinggi pohon, bukan ukurannya.
Pencarian Rekursif
Pencarian rekursif memiliki dua kasus dasar: subpohon kosong berarti tidak ditemukan, sedangkan nilai yang cocok berarti ditemukan.
Jika tidak, kita melakukan rekursi ke kiri atau kanan berdasarkan hasil perbandingan.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}Pencarian Iteratif
Pencarian juga dapat dilakukan dengan perulangan sederhana untuk menghindari biaya tambahan rekursi.
Kita mengikuti penunjuk turun melalui pohon hingga menemukan target atau mencapai akhir pada NULL.
Node *search_iter(Node *root, int target) {
while (root != NULL) {
if (target == root->value) return root;
root = (target < root->value)
? root->left : root->right;
}
return NULL; /* not found */
}Pencarian dalam Praktik
Program ini membangun BST dan mencari nilai yang ada serta nilai yang tidak ada, lalu mencetak apakah masing-masing ditemukan.
Nilai yang dikembalikan dan bukan NULL berarti ditemukan; NULL berarti nilainya tidak ada dalam pohon.
#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;
}
Node *search(Node *r,int t){
if(!r||r->value==t) return r;
return t<r->value ? search(r->left,t) : search(r->right,t);
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("7:%s 99:%s\n",
search(root,7)?"found":"no",
search(root,99)?"found":"no");
return 0;
}Menemukan Nilai Minimum
Dalam BST, nilai terkecil berada pada simpul paling kiri: terus ikuti left hingga nilainya NULL.
Secara simetris, nilai maksimum berada pada simpul paling kanan. Fungsi pembantu ini penting untuk penghapusan dan kueri rentang.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Mengapa Pembebasan Penting
Setiap simpul berasal dari malloc, sehingga setiap simpul harus dikembalikan dengan free. Lupa membebaskannya menyebabkan kebocoran memori.
Namun, Anda tidak dapat membebaskan simpul lalu membaca penunjuk anaknya, sehingga urutan pembebasan sangat penting.
Membebaskan dalam Post-Order
Cara aman untuk membebaskan pohon adalah post-order: bebaskan kedua anak terlebih dahulu, lalu bebaskan simpulnya sendiri.
Dengan begitu, kita pasti membaca penunjuk left dan right milik simpul sebelum memori simpul tersebut dilepaskan.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Urutan Salah yang Berbahaya
Jika Anda membebaskan simpul sebelum melakukan rekursi ke anak-anaknya, Anda membuat perilaku tidak terdefinisi: Anda akan melakukan dereferensi memori yang sudah dibebaskan untuk mencapai subpohon.
Ini adalah galat klasik berupa penggunaan setelah pembebasan. Selalu bebaskan anak-anak terlebih dahulu.
/* WRONG: use-after-free */
void bad_free(Node *root) {
if (!root) return;
free(root); /* freed here */
bad_free(root->left); /* reads freed memory! */
bad_free(root->right);
}Hindari Penunjuk Menggantung
Setelah free_tree selesai, penunjuk akar asli masih menyimpan alamat lama, tetapi memorinya sudah tidak ada.
Mengaturnya kembali ke NULL di pemanggil mencegah penggunaan kembali penunjuk yang menggantung secara tidak sengaja.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Menghitung Simpul yang Dibebaskan
Kita dapat memastikan pembebasan berjalan dengan menghitung simpul selama penelusuran post-order, lalu membebaskan setiap simpul.
Program ini membangun pohon, membebaskannya, dan melaporkan jumlah simpul yang dilepaskan.
#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 free_count(Node *r){
if(!r) return 0;
int c = free_count(r->left) + free_count(r->right);
free(r);
return c + 1;
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("freed=%d\n", free_count(root));
root = NULL;
return 0;
}Mencari dan Membebaskan Bersama
Siklus hidup lengkap: bangun pohon, cari di dalamnya, lalu bebaskan. Melakukan ketiganya menjaga program tetap benar dan bebas kebocoran.
Alat seperti Valgrind dapat memastikan bahwa setiap malloc dipasangkan dengan free.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Pemeriksaan Singkat
Bernalarlah tentang pelepasan memori yang aman.
Ringkasan
Pencarian BST membandingkan nilai lalu turun ke satu subpohon pada setiap langkah, dengan waktu yang sebanding dengan tinggi pohon. Nilai minimum adalah simpul paling kiri, sedangkan nilai maksimum adalah simpul paling kanan.
Bebaskan pohon dalam urutan post-order agar anak-anak dilepaskan sebelum induknya, lalu atur akar ke NULL untuk menghindari penunjuk yang menggantung.
Belajar C dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 39
- Pelajaran
- 144
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Mencari dan Membebaskan Memori” gratis?
Ya — teks lengkap “Mencari dan Membebaskan Memori” 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 “Mencari dan Membebaskan Memori”?
Temukan node dan bebaskan memori. 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 4 dari 4.
Berapa lama pelajaran “Mencari dan Membebaskan Memori” 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
- Node dan Struktur Pohon
- Menyisipkan ke BST
- Penelusuran
- Mencari dan Membebaskan Memori