Operasi Binary Search Tree

Pada Chapter sebelumnya kita memahami properti BST dan operasi search dasar. Sekarang kita melangkah ke tiga operasi inti yang membuat BST menjadi struktur data dinamis: insert (menambahkan elemen baru), delete (menghapus elemen), serta operasi pendukung min/max dan successor/predecessor. Operasi delete paling kompleks karena ada tiga kasus berbeda tergantung jumlah child node target. Tanpa pemahaman menyeluruh tentang ketiga kasus ini, kita tidak akan bisa mempertahankan properti BST setelah penghapusan. Pada Chapter ini kita akan membedah setiap operasi dengan pola 4-langkah, mengimplementasikan BST class lengkap dengan destructor RAII, dan menguji setiap operasi dengan output yang dapat diverifikasi.

Insert: Rekursif untuk Pertahankan Properti #

Aturan #

Untuk insert nilai V ke BST:

Bila tree kosong, V menjadi root.
Bila V < node.data, insert ke subtree kiri.
Bila V > node.data, insert ke subtree kanan.
Bila V == node.data, tergantung kebijakan: tolak (BST strict) atau simpan di kanan (BST duplikat).

Mekanisme #

Insert rekursif turun dari root, memilih subtree kiri/kanan sesuai perbandingan. Saat menemukan nullptr, buat node baru di posisi tersebut. Pointer child di parent di-update agar menunjuk node baru.

cpp
#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>
class BST {
public:
    BST() : root_(nullptr) {}
    ~BST() { destroy(root_); }

    void insert(const T& v) { root_ = insert_rec(root_, v); }

    bool search(const T& v) const { return search_rec(root_, v) != nullptr; }

    void inorder() const { inorder_rec(root_); std::cout << '\n'; }

    const Node<T>* root() const { return root_; }

private:
    Node<T>* root_;

    static Node<T>* insert_rec(Node<T>* node, const T& v) {
        if (node == nullptr) return new Node<T>(v);
        if (v < node->data)      node->left  = insert_rec(node->left,  v);
        else if (v > node->data) node->right = insert_rec(node->right, v);
        // v == node->data → abaikan (no duplicate)
        return node;
    }

    static const Node<T>* search_rec(const Node<T>* node, const T& v) {
        if (node == nullptr) return nullptr;
        if (v == node->data) return node;
        if (v < node->data) return search_rec(node->left, v);
        return search_rec(node->right, v);
    }

    static void inorder_rec(const Node<T>* node) {
        if (node == nullptr) return;
        inorder_rec(node->left);
        std::cout << node->data << ' ';
        inorder_rec(node->right);
    }

    static void destroy(Node<T>* node) {
        if (node == nullptr) return;
        destroy(node->left);
        destroy(node->right);
        delete node;
    }
};

int main() {
    BST<int> tree;
    for (int v : {8, 3, 10, 1, 6, 14, 4, 7, 13}) {
        tree.insert(v);
    }
    std::cout << "In-order setelah insert: ";
    tree.inorder();

    std::cout << "Cari 7: " << (tree.search(7) ? "ditemukan" : "tidak") << '\n';
    std::cout << "Cari 99: " << (tree.search(99) ? "ditemukan" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text
In-order setelah insert: 1 3 4 6 7 8 10 13 14 
Cari 7: ditemukan
Cari 99: tidak

insert_rec: kembalikan pointer ke subtree yang sudah dimodifikasi. Bila nullptr, buat node baru. Bila v < data, update node->left dengan hasil insert rekursif ke subtree kiri. Pola ini memungkinkan insert tanpa parent pointer.
v == node->data diabaikan: implementasi ini menolak duplikat. Bila ingin menerima duplikat, tambahkan ke subtree kanan (atau kiri, konsisten).
~BST(): destructor memanggil destroy(root_) yang traversal post-order untuk delete semua node. RAII menjamin tidak ada memory leak.
Hasil in-order: 1 3 4 6 7 8 10 13 14 terurut ascending — verifikasi properti BST terjaga.

Min dan Max #

Aturan #

Minimum = node paling kiri (turun terus ke left).
Maksimum = node paling kanan (turun terus ke right).

cpp
template <typename T>
const Node<T>* find_min(const Node<T>* node) {
    if (node == nullptr) return nullptr;
    while (node->left != nullptr) node = node->left;
    return node;
}

template <typename T>
const Node<T>* find_max(const Node<T>* node) {
    if (node == nullptr) return nullptr;
    while (node->right != nullptr) node = node->right;
    return node;
}

Kompleksitas O(h): turun terus ke satu arah sampai nullptr. Pada balanced BST, O(log n); pada skewed BST, O(n).

Successor dan Predecessor #

Successor dari sebuah node adalah node dengan nilai terkecil yang lebih besar dari node tersebut. Predecessor adalah kebalikannya.

Aturan Successor #

Bila node memiliki subtree kanan: successor = minimum subtree kanan.
Bila node tidak punya subtree kanan: successor = ancestor terdekat yang anak kirinya juga ancestor dari node.

Implementasi Successor (dengan parent pointer) #

cpp
#include <iostream>

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

template <typename T>
const NodeP<T>* find_min_p(const NodeP<T>* node) {
    while (node->left) node = node->left;
    return node;
}

template <typename T>
const NodeP<T>* successor(const NodeP<T>* node) {
    if (node->right != nullptr) return find_min_p(node->right);
    // Naik ke parent sampai node adalah left child
    const NodeP<T>* p = node->parent;
    while (p != nullptr && node == p->right) {
        node = p;
        p = p->parent;
    }
    return p;
}

int main() {
    // Tree:
    //         15
    //        /  \
    //       6    18
    //      / \   / \
    //     3   7 17  20
    //    / \   \
    //   2   4  13
    NodeP<int>* n15 = new NodeP<int>(15);
    NodeP<int>* n6  = new NodeP<int>(6);   n6->parent = n15;  n15->left  = n6;
    NodeP<int>* n18 = new NodeP<int>(18);  n18->parent = n15; n15->right = n18;
    NodeP<int>* n3  = new NodeP<int>(3);   n3->parent = n6;   n6->left  = n3;
    NodeP<int>* n7  = new NodeP<int>(7);   n7->parent = n6;   n6->right = n7;
    NodeP<int>* n17 = new NodeP<int>(17);  n17->parent = n18; n18->left = n17;
    NodeP<int>* n20 = new NodeP<int>(20);  n20->parent = n18; n18->right = n20;
    NodeP<int>* n2  = new NodeP<int>(2);   n2->parent = n3;   n3->left = n2;
    NodeP<int>* n4  = new NodeP<int>(4);   n4->parent = n3;   n3->right = n4;
    NodeP<int>* n13 = new NodeP<int>(13);  n13->parent = n7;  n7->right = n13;

    // Successor yang punya subtree kanan
    auto print_succ = [&](const char* name, NodeP<int>* node) {
        const NodeP<int>* s = successor(node);
        std::cout << "Successor(" << name << ") = "
                  << (s ? std::to_string(s->data) : std::string("null")) << '\n';
    };
    print_succ("15", n15);
    print_succ("6",  n6);
    print_succ("13", n13);
    print_succ("4",  n4);
    print_succ("20", n20);
    return 0;
}

Output yang Dihasilkan:

text
Successor(15) = 17
Successor(6)  = 7
Successor(13) = 15
Successor(4)  = 6
Successor(20) = null

successor(node) dengan subtree kanan: kembalikan minimum subtree kanan. Misalnya successor(15): subtree kanan = {18, 17, 20}, minimum = 17.
successor(node) tanpa subtree kanan: naik ke parent selama node adalah right child. Saat node menjadi left child dari parent, parent adalah successor. Misalnya successor(13): 13 → 7 (13 adalah right child 7) → 6 (7 adalah right child 6) → 15 (6 adalah left child 15). Successor = 15.
successor(20): 20 adalah node terbesar, tidak ada successor. Fungsi mengembalikan nullptr, dan lambda print_succ mencetak "null" setelah cek null.

Delete: Tiga Kasus Klasik #

Delete adalah operasi paling kompleks pada BST karena ada tiga kasus:

Kasus 1: Node Leaf (Tanpa Child) #

Langsung hapus node, set pointer parent ke nullptr.

Kasus 2: Node dengan Satu Child #

Ganti node dengan child-nya. Pointer parent kini menunjuk ke child node yang dihapus.

Kasus 3: Node dengan Dua Child #

Cari successor in-order (minimum dari subtree kanan), salin nilainya ke node yang akan dihapus, lalu hapus successor asli (yang pasti jatuh ke kasus 1 atau kasus 2 karena successor minimum punya paling banyak satu child — child kanan).

Implementasi Delete #

cpp
#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>
Node<T>* find_min(Node<T>* node) {
    while (node->left) node = node->left;
    return node;
}

template <typename T>
Node<T>* remove(Node<T>* node, const T& v) {
    if (node == nullptr) return nullptr;
    if (v < node->data) {
        node->left = remove(node->left, v);
    } else if (v > node->data) {
        node->right = remove(node->right, v);
    } else {
        // Kasus 1 & 2: 0 atau 1 child
        if (node->left == nullptr) {
            Node<T>* tmp = node->right;
            delete node;
            return tmp;
        } else if (node->right == nullptr) {
            Node<T>* tmp = node->left;
            delete node;
            return tmp;
        }
        // Kasus 3: 2 child — cari successor, salin data, hapus successor
        Node<T>* succ = find_min(node->right);
        node->data = succ->data;
        node->right = remove(node->right, succ->data);
    }
    return node;
}

template <typename T>
void inorder(Node<T>* node) {
    if (node == nullptr) return;
    inorder(node->left);
    std::cout << node->data << ' ';
    inorder(node->right);
}

int main() {
    // BST:
    //         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 << "Sebelum hapus: ";
    inorder(root); std::cout << '\n';

    // Kasus 1: hapus leaf 7
    root = remove(root, 7);
    std::cout << "Setelah hapus 7 (leaf): ";
    inorder(root); std::cout << '\n';

    // Kasus 2: hapus 14 (1 child = 13)
    root = remove(root, 14);
    std::cout << "Setelah hapus 14 (1 child): ";
    inorder(root); std::cout << '\n';

    // Kasus 3: hapus 8 (root, 2 child)
    root = remove(root, 8);
    std::cout << "Setelah hapus 8 (root, 2 child): ";
    inorder(root); std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Sebelum hapus: 1 3 4 6 7 8 10 13 14 
Setelah hapus 7 (leaf): 1 3 4 6 8 10 13 14 
Setelah hapus 14 (1 child): 1 3 4 6 8 10 13 
Setelah hapus 8 (root, 2 child): 1 3 4 6 10 13 

remove rekursif: pola mirip insert — kembalikan pointer ke subtree yang sudah diupdate. Saat menemukan node target, jalankan salah satu dari tiga kasus.
Kasus 1 (leaf) dan Kasus 2 (1 child): ditangani bersama. Bila left == nullptr, kembalikan right (yang bisa nullptr atau node). Demikian pula sebaliknya. Node lama di-delete.
Kasus 3 (2 child): cari successor (minimum subtree kanan). Successor pasti punya paling banyak satu child (child kanan) karena minimum = paling kiri. Salin data successor ke node target, lalu hapus successor dari subtree kanan secara rekursif (yang akan jatuh ke kasus 1 atau 2).
Hasil Setelah hapus 8: root lama 8 diganti dengan successor 10 (minimum dari subtree kanan {10, 13, 14} yang sebelumnya 14 sudah dihapus). Subtree {13} tetap utuh.
Properti BST terjaga: setiap penghapusan menghasilkan in-order traversal yang masih terurut ascending.

Ringkasan Kompleksitas BST #

Operasi	Average (balanced)	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Min/Max	O(log n)	O(n)
Successor/Predecessor	O(h)	O(n)

Ringkasan #

Insert rekursif: turun ke subtree kiri/kanan sesuai perbandingan, buat node baru saat menemui nullptr. Kompleksitas O(h).
Min/Max = node paling kiri / paling kanan. O(h).
Successor (dengan subtree kanan): minimum subtree kanan. Successor (tanpa subtree kanan): ancestor terdekat yang left child-nya adalah ancestor node.
Delete punya tiga kasus: leaf (langsung hapus), 1 child (ganti dengan child), 2 child (ganti dengan successor, lalu hapus successor dari subtree kanan).
Semua operasi O(h) di mana h = height tree. Pada balanced BST = O(log n), pada skewed BST = O(n) — inilah motivasi untuk self-balancing BST seperti AVL dan Red-Black Tree.