Binary Search Tree

Binary tree biasa tidak menjamin efisiensi pencarian. Node bernilai 50 bisa ada di mana saja — kiri, kanan, atau bahkan leaf terdalam. Bayangkan mencari buku di perpustakaan tanpa sistem klasifikasi: harus memeriksa setiap rak. Binary Search Tree (BST) menyelesaikan masalah ini dengan satu aturan sederhana namun kuat: untuk setiap node, semua nilai di subtree kiri lebih kecil dari node, dan semua nilai di subtree kanan lebih besar dari node. Aturan ini membuat BST bertindak seperti kamus terurut yang terbagi-bagi secara hierarkis. Pencarian, insert, dan delete semuanya O(h) di mana h adalah height — pada tree seimbang, ini O(log n). Pada Chapter ini kita akan memahami properti BST, memverifikasinya lewat in-order traversal, dan mengimplementasikan operasi search dasar. Operasi insert/delete lengkap akan dibahas pada chapter berikutnya.

Properti BST #

Binary tree disebut BST jika untuk setiap node N:

1. Semua nilai pada subtree kiri N kurang dari N.data.
2. Semua nilai pada subtree kanan N lebih besar dari N.data.
3. Subtree kiri dan subtree kanan juga memenuhi properti BST (rekursif).

Pada tree di atas, untuk setiap node, subtree kiri berisi nilai lebih kecil, subtree kanan berisi nilai lebih besar. In-order traversal menghasilkan: 1, 3, 4, 6, 7, 8, 10, 13, 14 — terurut ascending.

Mengapa In-order Traversal Terurut? #

In-order traversal pada BST selalu menghasilkan urutan terurut. Mekanismenya:

1. Kunjungi seluruh subtree kiri (semua nilai < node).
2. Cetak node.
3. Kunjungi seluruh subtree kanan (semua nilai > node).

Karena subtree kiri menghasilkan nilai-nilai yang lebih kecil dan dicetak lebih dulu, lalu node, lalu nilai-nilai yang lebih besar dari subtree kanan, hasilnya selalu terurut.

Verifikasi BST #

Implementasi verifikasi harus memeriksa rentang nilai yang valid untuk setiap node, bukan hanya membandingkan dengan child langsung:

#include <iostream>
#include <limits>
#include <vector>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

// Verifikasi BST dengan batas min/max yang dipersempit tiap level
template <typename T>
bool is_bst(const Node<T>* node, T lo, T hi) {
    if (node == nullptr) return true;
    if (node->data <= lo || node->data >= hi) return false;
    return is_bst(node->left,  lo, node->data)
        && is_bst(node->right, node->data, hi);
}

template <typename T>
bool is_bst(const Node<T>* root) {
    return is_bst(root, std::numeric_limits<T>::min(),
                         std::numeric_limits<T>::max());
}

template <typename T>
void inorder(const Node<T>* n, std::vector<T>& out) {
    if (n == nullptr) return;
    inorder(n->left, out);
    out.push_back(n->data);
    inorder(n->right, out);
}

int main() {
    // BST valid:
    //         8
    //        / \
    //       3   10
    //      / \    \
    //     1   6    14
    //        / \   /
    //       4   7 13
    Node<int>* root = new Node<int>(8);
    root->left  = new Node<int>(3);
    root->right = new Node<int>(10);
    root->left->left   = new Node<int>(1);
    root->left->right  = new Node<int>(6);
    root->left->right->left  = new Node<int>(4);
    root->left->right->right = new Node<int>(7);
    root->right->right = new Node<int>(14);
    root->right->right->left = new Node<int>(13);

    std::cout << "Is BST valid: " << (is_bst(root) ? "ya" : "tidak") << '\n';

    std::vector<int> sorted;
    inorder(root, sorted);
    std::cout << "In-order: ";
    for (int x : sorted) std::cout << x << ' ';
    std::cout << '\n';

    // Cek apakah in-order benar terurut ascending
    bool sorted_ok = true;
    for (size_t i = 1; i < sorted.size(); ++i) {
        if (sorted[i-1] >= sorted[i]) { sorted_ok = false; break; }
    }
    std::cout << "In-order terurut ascending: " << (sorted_ok ? "ya" : "tidak") << '\n';

    // Sekarang contoh bukan BST: node 6 di subtree kanan root 10 (6 < 10)
    Node<int>* bad = new Node<int>(10);
    bad->left  = new Node<int>(5);
    bad->right = new Node<int>(15);
    bad->right->left = new Node<int>(6);   // 6 < 10 → melanggar properti BST
    bad->right->right = new Node<int>(20);

    std::cout << "Bad tree Is BST valid: " << (is_bst(bad) ? "ya" : "tidak") << '\n';
    std::cout << "Bad tree (cek child-only, naive): " << '\n';
    // Naive: hanya cek left.data < data < right.data → lolos karena 6 < 15
    bool naive_ok = true;
    if (bad->left && bad->left->data >= bad->data) naive_ok = false;
    if (bad->right && bad->right->data <= bad->data) naive_ok = false;
    if (bad->right->left && bad->right->left->data >= bad->right->data) naive_ok = false;
    std::cout << "  naive cek node 15: child 6 < 15, lolos → " << (naive_ok ? "TRUE (salah!)" : "false") << '\n';

    return 0;
}

Output yang Dihasilkan:

Is BST valid: ya
In-order: 1 3 4 6 7 8 10 13 14 
In-order terurut ascending: ya
Bad tree Is BST valid: tidak
Bad tree (cek child-only, naive): 
  naive cek node 15: child 6 < 15, lolos → TRUE (salah!)

1. is_bst(node, lo, hi): fungsi rekursif dengan dua parameter batas lo dan hi. Setiap node harus berada dalam rentang (lo, hi) eksklusif. Saat turun ke subtree kiri, hi dipersempit ke node.data. Saat turun ke subtree kanan, lo dinaikkan ke node.data.
2. Pemanggilan awal is_bst(root, MIN, MAX): root boleh bernilai apa pun dalam rentang tipe data.
3. inorder ke vector: traversal in-order menampung nilai ke std::vector. Pada BST valid, vector ini selalu terurut ascending.
4. Cek sorted_ok: memverifikasi vector benar-benar terurut. Ini adalah cara alternatif verifikasi BST, namun memerlukan O(n) ruang — verifikasi min/max lebih efisien O(h) ruang.
5. Bad tree: root 10, anak kanan 15, anak kiri dari 15 adalah 6. Naive check hanya membandingkan child langsung (6 < 15) — lolos padahal 6 ada di subtree kanan 10, melanggar properti BST karena 6 < 10. Verifikasi is_bst dengan batas menangkap ini: 6 harus lebih besar dari 10 (lo=10) dan lebih kecil dari 15 (hi=15), namun 6 ≤ 10, jadi gagal.

Operasi Search pada BST #

Pencarian nilai X pada BST memanfaatkan properti pengurutan:

#include <iostream>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

template <typename T>
const Node<T>* search(const Node<T>* node, const T& target) {
    if (node == nullptr) return nullptr;
    if (target == node->data) return node;
    if (target < node->data) return search(node->left, target);
    return search(node->right, target);
}

int main() {
    Node<int>* root = new Node<int>(8);
    root->left  = new Node<int>(3);
    root->right = new Node<int>(10);
    root->left->left  = new Node<int>(1);
    root->left->right = new Node<int>(6);
    root->right->right = new Node<int>(14);

    for (int target : {6, 13, 8}) {
        const Node<int>* found = search(root, target);
        std::cout << "Cari " << target << ": "
                  << (found ? "ditemukan" : "tidak ditemukan") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Cari 6: ditemukan
Cari 13: tidak ditemukan
Cari 8: ditemukan

1. Base case nullptr → nullptr: bila mencapai leaf tanpa menemukan target, kembalikan nullptr.
2. Target == data: ketemu, kembalikan pointer ke node.
3. Target < data: target harus ada di subtree kiri (bila ada).
4. Target > data: target harus ada di subtree kanan (bila ada).
5. Kompleksitas O(h): setiap langkah membuang setengah dari sisa tree (idealnya). Pada balanced BST, h = O(log n). Pada skewed BST, h = O(n) — seburuk linear search.

Kompleksitas BST vs Struktur Lain #

Ringkasan #

• Properti BST: setiap node memiliki seluruh subtree kiri < node < seluruh subtree kanan. Validasi harus memeriksa rentang (lo, hi), bukan hanya child langsung.
• In-order traversal pada BST selalu menghasilkan urutan terurut ascending. Sifat ini dipakai untuk verifikasi BST, mencetak BST secara terurut, dan konversi BST ke sorted array.
• Operasi search memanfaatkan properti BST: bandingkan target dengan node, lalu pilih subtree kiri atau kanan. Kompleksitas O(h) di mana h adalah height.
• BST unggul untuk: traversal terurut, range query, dan operasi dinamis (insert/delete/search semua O(log n) pada tree seimbang).
• Kelemahan: pada data input terurut, BST bisa menjadi skewed dan semua operasi menjadi O(n). Solusinya adalah self-balancing BST seperti AVL atau Red-Black Tree yang akan dibahas pada chapter berikutnya.