Binary tree chapter sebelumnya menerima label apa pun di node mana pun; binary search tree (BST) menambahkan satu aturan disiplin yang mengubahnya menjadi struktur pencarian. Aturannya: untuk setiap node, seluruh subtree kiri hanya memuat nilai yang lebih kecil, dan seluruh subtree kanan hanya memuat nilai yang lebih besar. Akibatnya, setiap langkah pencarian turun satu level dan langsung membuang separuh kandidat — binary search dari chapter algoritma, tetapi dijalankan pada struktur data yang hidup dan mudah diperbarui. Chapter ini membangun BST lengkap dengan insert, search, in-order traversal, dan penghapusan tiga kasus, lalu membuktikan sendiri kelemahan terbesarnya.

Properti BST dan Operasi Dasar #

Properti BST bersifat rekursif: berlaku pada root dan pada setiap subtree di dalamnya. Dari properti itu, operasi dasar hampir menulis dirinya sendiri. Mencari nilai x: bandingkan dengan node sekarang — lebih kecil? belok kiri. Lebih besar? belok kanan. Sama? ketemu. Menyisipkan nilai: jalankan pencarian yang sama sampai menemukan tempat kosong (nullptr), lalu tempelkan node baru di sana. Kedua operasi berjalan O(h) dengan h tinggi tree; pada tree seimbang h kira-kira log₂ n, persis seperti binary search pada array.

Program berikut memuat seluruh implementasi, termasuk penghapusan tiga kasus yang kita bedah setelah ini:

cpp 
// Binary Search Tree: insert, search, in-order terurut, dan hapus (3 kasus).
#include <iostream>

struct Node {
    int data;
    Node* kiri;
    Node* kanan;
};

Node* insert(Node* akar, int nilai) {
    if (akar == nullptr) return new Node{nilai, nullptr, nullptr};
    if (nilai < akar->data) {
        akar->kiri = insert(akar->kiri, nilai);
    } else if (nilai > akar->data) {
        akar->kanan = insert(akar->kanan, nilai);
    }
    return akar;  // nilai duplikat diabaikan
}

bool cari(Node* akar, int nilai) {
    if (akar == nullptr) return false;
    if (nilai == akar->data) return true;
    return (nilai < akar->data) ? cari(akar->kiri, nilai)
                                : cari(akar->kanan, nilai);
}

void inOrder(Node* akar, bool& pertama) {
    if (akar == nullptr) return;
    inOrder(akar->kiri, pertama);
    if (!pertama) std::cout << ' ';
    std::cout << akar->data;
    pertama = false;
    inOrder(akar->kanan, pertama);
}

void cetakUrut(Node* akar, const char* label) {
    std::cout << label;
    bool pertama = true;
    inOrder(akar, pertama);
    std::cout << '\n';
}

Node* minNode(Node* node) {  // node terkiri = nilai terkecil
    while (node->kiri != nullptr) node = node->kiri;
    return node;
}

Node* hapus(Node* akar, int nilai) {
    if (akar == nullptr) return nullptr;
    if (nilai < akar->data) {
        akar->kiri = hapus(akar->kiri, nilai);
    } else if (nilai > akar->data) {
        akar->kanan = hapus(akar->kanan, nilai);
    } else {
        // Kasus 1 dan 2: tanpa anak atau hanya anak kanan
        if (akar->kiri == nullptr) {
            Node* kanan = akar->kanan;
            delete akar;
            return kanan;
        }
        // Kasus 2: hanya anak kiri
        if (akar->kanan == nullptr) {
            Node* kiri = akar->kiri;
            delete akar;
            return kiri;
        }
        // Kasus 3: dua anak — ganti dengan nilai terkecil subtree kanan
        Node* pengganti = minNode(akar->kanan);
        akar->data = pengganti->data;
        akar->kanan = hapus(akar->kanan, pengganti->data);
    }
    return akar;
}

int tinggi(Node* node) {
    if (node == nullptr) return 0;
    int kiri = tinggi(node->kiri);
    int kanan = tinggi(node->kanan);
    return 1 + (kiri > kanan ? kiri : kanan);
}

void hapusTree(Node* node) {  // pola post-order: anak dulu, baru node
    if (node == nullptr) return;
    hapusTree(node->kiri);
    hapusTree(node->kanan);
    delete node;
}

int main() {
    Node* akar = nullptr;
    for (int nilai : {8, 3, 10, 1, 6, 14, 4, 7, 13}) {
        akar = insert(akar, nilai);
    }
    cetakUrut(akar, "In-order            : ");

    std::cout << "cari(6) : " << (cari(akar, 6) ? "ketemu" : "tidak") << '\n';
    std::cout << "cari(9) : " << (cari(akar, 9) ? "ketemu" : "tidak") << '\n';

    akar = hapus(akar, 1);    // kasus 1: daun
    akar = hapus(akar, 14);   // kasus 2: satu anak
    akar = hapus(akar, 3);    // kasus 2: satu anak
    cetakUrut(akar, "Setelah hapus 1,14,3: ");

    akar = hapus(akar, 8);    // kasus 3: dua anak (root)
    cetakUrut(akar, "Setelah hapus 8     : ");

    // Skenario degenerate: insert terurut membuat rantai satu arah
    Node* miring = nullptr;
    for (int nilai : {1, 2, 3, 4, 5, 6, 7}) {
        miring = insert(miring, nilai);
    }
    std::cout << "Tinggi BST miring (insert terurut) : " << tinggi(miring) << '\n';
    std::cout << "Tinggi BST pertama (9 nilai campur): " << tinggi(akar) << '\n';

    hapusTree(akar);
    hapusTree(miring);
    return 0;
}

Output yang Dihasilkan:

text 
In-order            : 1 3 4 6 7 8 10 13 14
cari(6) : ketemu
cari(9) : tidak
Setelah hapus 1,14,3: 4 6 7 8 10 13
Setelah hapus 8     : 4 6 7 10 13
Tinggi BST miring (insert terurut) : 7
Tinggi BST pertama (9 nilai campur): 3

Bedah baris penting:

  1. Baris 10-19 (insert): kasus kosong membuat node baru; perbandingan memilih cabang; nilai duplikat diabaikan — BST kita tidak menyimpan dua kunci sama.
  2. Baris 20-26 (cari): satu perbandingan per level, lalu mundur ke satu cabang saja. cari(9) tidak pernah menyentuh subtree kiri — itulah penghematan yang ditawarkan BST.
  3. Baris 27-37 (inOrder): traversal kiri → node → kanan dari chapter Tree; pada BST, urutan ini keluar sudah terurut menaik, seperti terlihat pada baris pertama output.
  4. Baris 43-46 (minNode): nilai terkecil subtree selalu di ujung terkiri — helper untuk kasus penghapusan yang paling rumit.
  5. Baris 48-77 (hapus): tiga kasus penghapusan, dibahas lengkap di bagian berikutnya.
  6. Baris 91-94: menyisipkan 8, 3, 10, 1, 6, 14, 4, 7, 13 lalu mencetaknya lewat in-order: 1 3 4 6 7 8 10 13 14 — terurut tanpa satu pun pemanggilan sort.
  7. Baris 109-113: menyisipkan 1..7 secara menaik menghasilkan tinggi 7, sementara tree pertama dengan 9 nilai campur hanya setinggi 3 — bukti nyata skenario terburuk BST.

Penghapusan: Tiga Kasus #

Menghapus node BST adalah satu-satunya operasi yang butuh ketelitian ekstra, karena sambungan harus dipindahkan tanpa melanggar properti BST. Semua kasus berangkat dari pencarian yang sama, lalu bercabang:

  1. Node daun (tanpa anak): cukup lepaskan — hapus(akar, 1) pada contoh mengembalikan nullptr ke induknya. Baris 56-60 menangani ini sekaligus sebagai subkasus berikutnya.
  2. Satu anak: node digantikan langsung oleh anaknya. hapus(akar, 14) menggantikan 14 dengan satu-satunya anaknya, 13; baris 62-66 menangani varian anak kiri.
  3. Dua anak: node tidak boleh sekadar dilepas karena dua subtree harus tetap terjaga. Trik standar: cari nilai terkecil di subtree kanan (successor in-order), salin nilainya ke node sekarang, lalu hapus node successor — yang pasti berada di kasus 1 atau 2. hapus(akar, 8) menyalin 10 ke root, lalu menghapus node 10 asli.

Penggantian dengan successor in-order menjamin properti BST tetap terpenuhi: successor adalah nilai terkecil yang lebih besar, sehingga lebih besar dari seluruh subtree kiri dan lebih kecil dari sisa subtree kanan. Setelah tiga penghapusan dan satu penghapusan root, in-order pada output tetap terurut — bukti strukturnya masih sah.

Skenario Terburuk: Tree Degenerate #

Baris terakhir output menyembunyikan pelajaran paling penting. Menyisipkan 1, 2, 3, 4, 5, 6, 7 secara menaik membuat setiap node baru belok kanan terus — hasilnya bukan tree melainkan rantai, dengan tinggi 7 untuk 7 node. Pada rantai seperti ini semua operasi menjadi O(n): BST kehilangan seluruh keunggulannya dan tidak lebih baik dari linear search.

Data yang datang hampir terurut adalah kasus nyata yang sangat umum, sehingga masalah ini tidak bisa diabaikan. Solusinya adalah self-balancing BST seperti AVL tree atau red-black tree, yang melakukan rotasi agar tinggi tetap mendekati log₂ n. std::map dan std::set di STL memakai red-black tree, sehingga menjamin O(log n) pada urutan insert apa pun tanpa usaha dari penggunanya.

BST menjaga urutan dengan perbandingan; struktur berikutnya menjaga urutan dengan aturan yang jauh lebih longgar dan tetap menawarkan akses instan ke elemen ekstrem — heap, fondasi dari priority queue.

Rujukan resmi: std::map dan std::set .