Pohon Biner

Penyisipan, pencarian, dan penghapusan pada BST serta penelusuran in-order, pre-order, dan post-order.

Daftar isi

Pohon biner (binary tree) adalah struktur data bercabang yang setiap simpulnya memuat paling banyak dua anak. Binary search tree atau BST adalah pohon biner yang menaati satu sifat tambahan. Seluruh nilai pada cabang kiri lebih kecil daripada nilai simpulnya, sedangkan seluruh nilai pada cabang kanan lebih besar. Sifat inilah yang membuat pencarian dapat memangkas separuh pohon pada setiap langkah. Topik ini membangun BST dalam C mulai dari tiga penelusuran rekursif, penyisipan dan pencarian, hingga penghapusan simpul dengan tiga kasusnya.

Tiga penelusuran dengan rekursi#

Ketiga penelusuran memakai struktur rekursi yang sama, yaitu memproses simpul, anak kiri, dan anak kanan, tetapi urutannya berbeda. In-order mengunjungi kiri terlebih dahulu, kemudian simpul, lalu kanan, sehingga menghasilkan urutan naik pada BST. Pre-order mengunjungi simpul sebelum kedua anaknya dan cocok untuk menyalin struktur pohon. Post-order mengunjungi simpul paling akhir, sehingga menjadi cara alami untuk membebaskan seluruh simpul dari daun ke akar.

BST berisi tujuh nilai yang terbentuk dari data 50, 30, 70, 20, 40, 60, dan 80

Fungsi penelusuran berikut menerima pointer pertama agar pemisah spasi tidak muncul di awal baris. Ketiga fungsi memakai pola yang sama, sehingga mengganti urutan cukup dengan memindahkan tiga baris intinya.

c Contoh: inti penelusuran in-order

// tidak-dijalankan
void inorder(struct simpul *akar, int *pertama)
{
    if (akar == NULL) {
        return;
    }
    inorder(akar->kiri, pertama);   /* seluruh cabang kiri lebih dahulu */
    if (*pertama == 0) {
        printf(" ");
    }
    printf("%d", akar->nilai);      /* baru simpulnya */
    *pertama = 0;
    inorder(akar->kanan, pertama);  /* lalu seluruh cabang kanan */
}

Program utuh berikut membangun pohon tujuh simpul dari data tetap, lalu menampilkan hasil ketiga penelusurannya. Urutan nilai pada baris in-order terurut naik tanpa pengurutan eksplisit apa pun, dan hal itu langsung mengikuti sifat BST.

c penelusuran.c

#include <stdio.h>
#include <stdlib.h>

struct simpul {
    int nilai;
    struct simpul *kiri;
    struct simpul *kanan;
};

struct simpul *simpul_baru(int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->kiri = NULL;
    baru->kanan = NULL;
    return baru;
}

struct simpul *sisip(struct simpul *akar, int nilai)
{
    if (akar == NULL) {
        return simpul_baru(nilai);
    }
    if (nilai < akar->nilai) {
        akar->kiri = sisip(akar->kiri, nilai);
    } else if (nilai > akar->nilai) {
        akar->kanan = sisip(akar->kanan, nilai);
    }
    return akar;
}

void inorder(struct simpul *akar, int *pertama)
{
    if (akar == NULL) {
        return;
    }
    inorder(akar->kiri, pertama);
    if (*pertama == 0) {
        printf(" ");
    }
    printf("%d", akar->nilai);
    *pertama = 0;
    inorder(akar->kanan, pertama);
}

void preorder(struct simpul *akar, int *pertama)
{
    if (akar == NULL) {
        return;
    }
    if (*pertama == 0) {
        printf(" ");
    }
    printf("%d", akar->nilai);
    *pertama = 0;
    preorder(akar->kiri, pertama);
    preorder(akar->kanan, pertama);
}

void postorder(struct simpul *akar, int *pertama)
{
    if (akar == NULL) {
        return;
    }
    postorder(akar->kiri, pertama);
    postorder(akar->kanan, pertama);
    if (*pertama == 0) {
        printf(" ");
    }
    printf("%d", akar->nilai);
    *pertama = 0;
}

int main(void)
{
    struct simpul *akar = NULL;
    int data[7] = {50, 30, 70, 20, 40, 60, 80};

    for (int i = 0; i < 7; i++) {
        akar = sisip(akar, data[i]);
    }

    int pertama = 1;
    printf("In-order   : ");
    inorder(akar, &pertama);
    printf("\n");

    pertama = 1;
    printf("Pre-order  : ");
    preorder(akar, &pertama);
    printf("\n");

    pertama = 1;
    printf("Post-order : ");
    postorder(akar, &pertama);
    printf("\n");

    return 0;
}

text Keluaran

In-order   : 20 30 40 50 60 70 80
Pre-order  : 50 30 20 40 70 60 80
Post-order : 20 40 30 60 80 70 50

Demo berikut menghidupkan ketiga urutan tersebut. Klik salah satu tombolnya, amati simpul yang menyala satu per satu, dan bandingkan urutan kunjungan yang tercetak di bawah tombol dengan keluaran program di atas.

Pencarian dan penyisipan mengikuti sifat BST#

Pencarian pada BST membandingkan nilai yang dicari dengan simpul yang sedang dipegang, lalu bergerak ke kiri apabila nilainya lebih kecil dan ke kanan apabila lebih besar. Setiap perbandingan mengeliminasi satu cabang seluruhnya, sehingga banyaknya langkah sebanding dengan tinggi pohon, bukan dengan banyaknya simpul. Pada pohon yang seimbang, tingginya tumbuh sekitar $\log_2 n$ . Pohon yang meruncing menjadi rantai satu arah menyusutkan keunggulan itu menjadi sebanding dengan $n$ .

Penyisipan mengikuti jalur yang sama dengan pencarian, dan simpul baru selalu jatuh sebagai daun. Fungsi sisip pada program di atas ditulis secara rekursif dengan mengembalikan alamat cabang yang mungkin telah berubah, sehingga pemanggil cukup menugaskan kembali hasilnya, misalnya akar = sisip(akar, nilai). Nilai yang sama dengan simpul yang sudah ada tidak disisipkan dua kali karena kedua cabang perbandingan sama-sama menolaknya, dan perilaku ini membuat BST menjadi penampung nilai unik.

Fungsi cari mengembalikan alamat simpul yang ditemukan, sehingga pemanggil dapat menguji hasilnya terhadap NULL untuk membedakan ditemukan dan tidak ditemukan. Pencarian ini juga lazim ditulis dalam bentuk iteratif, yaitu perulangan yang memindahkan satu pointer kerja ke kiri atau kanan sesuai perbandingan. Hasil akhirnya sama persis dengan versi rekursifnya. Versi iteratif menghemat tumpukan pemanggilan fungsi, sedangkan versi rekursif lebih mudah dibaca karena menyerupai definisi pohonnya sendiri.

Penghapusan dengan tiga kasus#

Penghapusan adalah operasi BST yang paling menuntut, karena rantai kaitan antarsimpul harus tetap utuh sesudahnya. Kasus pertama adalah simpul daun tanpa anak, yang penanganannya hanya membebaskan simpul dan mengosongkan cabang orang tuanya. Kasus kedua adalah simpul dengan satu anak, yang penyelesaiannya menaikkan satu-satunya anak itu menggantikan posisi orang tuanya. Program berikut menyediakan fungsi cari, minimum, dan hapus, dan ketiga kasus penghapusan ditangani di dalam satu fungsi rekursif bernama hapus.

Kasus ketiga, yaitu simpul dengan dua anak, tidak memindahkan dua cabang sekaligus. Nilai penerus in-order, yakni nilai terkecil pada cabang kanan, disalin ke simpul yang sedang dihapus, kemudian simpul penerus aslinya dihapus dari cabang kanan. Simpul penerus itu sendiri pasti tidak memiliki anak kiri, sehingga penghapusannya jatuh ke kasus yang lebih sederhana dan rekursi berakhir dengan sendirinya.

c bst.c

#include <stdio.h>
#include <stdlib.h>

struct simpul {
    int nilai;
    struct simpul *kiri;
    struct simpul *kanan;
};

struct simpul *simpul_baru(int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->kiri = NULL;
    baru->kanan = NULL;
    return baru;
}

struct simpul *sisip(struct simpul *akar, int nilai)
{
    if (akar == NULL) {
        return simpul_baru(nilai);
    }
    if (nilai < akar->nilai) {
        akar->kiri = sisip(akar->kiri, nilai);
    } else if (nilai > akar->nilai) {
        akar->kanan = sisip(akar->kanan, nilai);
    }
    return akar;
}

void inorder(struct simpul *akar, int *pertama)
{
    if (akar == NULL) {
        return;
    }
    inorder(akar->kiri, pertama);
    if (*pertama == 0) {
        printf(" ");
    }
    printf("%d", akar->nilai);
    *pertama = 0;
    inorder(akar->kanan, pertama);
}

struct simpul *cari(struct simpul *akar, int nilai)
{
    if (akar == NULL || akar->nilai == nilai) {
        return akar;
    }
    if (nilai < akar->nilai) {
        return cari(akar->kiri, nilai);
    }
    return cari(akar->kanan, nilai);
}

struct simpul *minimum(struct simpul *akar)
{
    while (akar->kiri != NULL) {
        akar = akar->kiri;
    }
    return akar;
}

struct simpul *hapus(struct simpul *akar, int nilai)
{
    if (akar == NULL) {
        return NULL;
    }
    if (nilai < akar->nilai) {
        akar->kiri = hapus(akar->kiri, nilai);
    } else if (nilai > akar->nilai) {
        akar->kanan = hapus(akar->kanan, nilai);
    } else {
        /* kasus satu anak atau tanpa anak */
        if (akar->kiri == NULL) {
            struct simpul *pengganti = akar->kanan;
            free(akar);
            return pengganti;
        }
        if (akar->kanan == NULL) {
            struct simpul *pengganti = akar->kiri;
            free(akar);
            return pengganti;
        }
        /* kasus dua anak: ambil nilai penerus in-order */
        struct simpul *penerus = minimum(akar->kanan);
        akar->nilai = penerus->nilai;
        akar->kanan = hapus(akar->kanan, penerus->nilai);
    }
    return akar;
}

void bebaskan(struct simpul *akar)
{
    if (akar == NULL) {
        return;
    }
    bebaskan(akar->kiri);
    bebaskan(akar->kanan);
    free(akar);
}

int main(void)
{
    struct simpul *akar = NULL;
    int data[7] = {50, 30, 70, 20, 40, 60, 80};

    for (int i = 0; i < 7; i++) {
        akar = sisip(akar, data[i]);
    }

    int pertama = 1;
    printf("In-order sebelum penghapusan: ");
    inorder(akar, &pertama);
    printf("\n");

    printf("Cari 40: %s\n", cari(akar, 40) != NULL ? "ditemukan" : "tidak ada");
    printf("Cari 45: %s\n", cari(akar, 45) != NULL ? "ditemukan" : "tidak ada");

    akar = hapus(akar, 30);
    pertama = 1;
    printf("In-order setelah menghapus 30: ");
    inorder(akar, &pertama);
    printf("\n");

    bebaskan(akar);
    return 0;
}

text Keluaran

In-order sebelum penghapusan: 20 30 40 50 60 70 80
Cari 40: ditemukan
Cari 45: tidak ada
In-order setelah menghapus 30: 20 40 50 60 70 80

Simpul 30 pada program di atas memiliki dua anak, yaitu 20 dan 40, sehingga penghapusannya memakai nilai penerus in-order berupa 40. Hasil in-order sesudahnya tetap terurut naik, yang berarti sifat BST pulih sepenuhnya. Pembebasan seluruh pohon memakai post-order dengan alasan yang sudah terlihat pada bagian penelusuran, yaitu anak-anak harus dibebaskan sebelum orang tuanya agar tidak ada alamat yang hilang sebelum terpakai.

Kesalahan umum#

Empat kesalahan berikut paling sering muncul pada BST, dan semuanya berhubungan dengan urutan operasi terhadap simpul yang sedang dibaca atau dihapus.

Membebaskan pohon dengan in-order. Free pada simpul orang tua sebelum anaknya membuat anak menjadi tidak terjangkau. Gunakan post-order, atau simpan alamat anak sebelum membebaskan orang tuanya.
Salah menempatkan pencetakan pada penelusuran. Baris printf sebelum kedua panggilan rekursif menghasilkan pre-order, di antara keduanya menghasilkan in-order, dan sesudahnya menghasilkan post-order. Letakkan baris itu sesuai urutan yang diinginkan, bukan di luar fungsi rekursinya.
Menganggap BST selalu seimbang. Penyisipan data yang sudah terurut menghasilkan rantai satu arah, sehingga pencarian menyentuh hampir semua simpul. Pohon seimbang memerlukan penataan tambahan seperti rotasi yang dipakai struktur AVL dan red-black tree, dan rotasi menata ulang cabang secara lokal tanpa merusak urutan in-order.
Kehilangan cabang saat penghapusan dua anak. Menyalin nilai penerus tanpa menghapus simpul penerus aslinya membuat nilai yang sama muncul dua kali. Hapus penerus dari cabang kanan setelah nilainya disalin, sebagaimana hapus menugaskan ulang akar->kanan.

Ringkasan#

BST menaati sifat kiri lebih kecil dan kanan lebih besar, sehingga pencarian dan penyisipan bergerak sepanjang satu jalur dari akar ke daun.
In-order menghasilkan urutan naik, pre-order menyalin struktur, dan post-order membebaskan pohon dari daun ke akar.
Penghapusan memiliki tiga kasus, dan kasus dua anak diselesaikan dengan menyalin nilai penerus in-order lalu menghapus simpul penerus dari cabang kanan.

Referensi#

Binary Search Tree — VisuAlgo — Visualisasi interaktif penyisipan, pencarian, dan penghapusan BST.
malloc(3) — Linux man-pages project — Alokasi yang dipakai untuk setiap simpul pohon.