🌳 Binary Search Tree (BST)

Struktur Data dan Algoritma

Pertemuan 12

Universitas Pertahanan RI

🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Menjelaskan properti BST
Mengimplementasikan operasi search pada BST
Mengimplementasikan operasi insert pada BST
Mengimplementasikan operasi delete (3 kasus)
Menganalisis kompleksitas BST
Memahami dampak BST tidak seimbang

📋 Agenda

Bagian 1

Review Binary Tree
Properti BST
Operasi Search
Operasi Insert

Bagian 2

findMin & findMax
Operasi Delete
Analisis Kompleksitas
Balanced BST

📖 Review: Binary Tree

Pada Pertemuan 11, kita mempelajari:

Binary Tree: setiap node punya maksimal 2 anak
Traversal: Preorder, Inorder, Postorder, Level-order
Pencarian pada Binary Tree biasa: O(n)

Bagaimana membuat pencarian lebih efisien?

📖 Binary Search Tree (BST)

Binary Search Tree (BST) adalah Binary Tree dimana untuk setiap node:

Semua nilai di left subtree < nilai node
Semua nilai di right subtree > nilai node

Ilustrasi Properti BST

Gambar 12.1: Properti Binary Search Tree

Struktur Node BST


struct BSTNode {
    int data;
    BSTNode* left;
    BSTNode* right;
    
    // Constructor
    BSTNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

Sama dengan Binary Tree, tapi dengan aturan pengurutan

📊 BST vs Binary Tree Biasa

Aspek	Binary Tree	BST
Pengurutan	Tidak ada aturan	Terurut
Search	O(n)	O(log n) avg
Insert	O(n)	O(log n) avg
Inorder Traversal	Urutan acak	Terurut ascending!

🧠 Quiz 1: Valid BST?

Apakah tree berikut adalah BST yang valid?

Jawaban: TIDAK VALID!

Node 12 berada di left subtree dari root 10, tapi 12 > 10.

Semua node di left subtree harus < root.

🔍 Operasi Search

Algoritma:

Mulai dari root
Jika nilai == node saat ini → ditemukan!
Jika nilai < node → ke kiri
Jika nilai > node → ke kanan
Jika nullptr → tidak ditemukan

Visualisasi Search

Gambar 12.2: Proses pencarian pada BST

Setiap langkah mengeliminasi setengah dari tree!

💻 Implementasi Search (Rekursif)


BSTNode* search(BSTNode* root, int key) {
    // Base case
    if (root == nullptr || root->data == key) {
        return root;
    }
    
    // Key lebih kecil, cari di kiri
    if (key < root->data) {
        return search(root->left, key);
    }
    
    // Key lebih besar, cari di kanan
    return search(root->right, key);
}

💻 Implementasi Search (Iteratif)


BSTNode* searchIterative(BSTNode* root, int key) {
    BSTNode* current = root;
    
    while (current != nullptr) {
        if (key == current->data) {
            return current;  // Ditemukan
        } else if (key < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    
    return nullptr;  // Tidak ditemukan
}

➕ Operasi Insert

Algoritma:

Jika tree kosong → node baru jadi root
Bandingkan dengan node saat ini
Jika < → rekursi ke kiri
Jika > → rekursi ke kanan
Sisipkan di posisi nullptr

Catatan: BST standar tidak mengizinkan nilai duplikat

Visualisasi Insert

Gambar 12.4: Proses penyisipan nilai pada BST

💻 Implementasi Insert


BSTNode* insert(BSTNode* root, int value) {
    // Base case: posisi ditemukan
    if (root == nullptr) {
        return new BSTNode(value);
    }
    
    // Rekursi ke subtree yang sesuai
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // Jika value == root->data, diabaikan
    
    return root;
}

Contoh: Membangun BST

Insert: 50, 30, 70, 20, 40, 60, 80

50 → root
30 < 50 → kiri
70 > 50 → kanan
20 < 50, < 30 → kiri-kiri

40 < 50, > 30 → kiri-kanan
60 > 50, < 70 → kanan-kiri
80 > 50, > 70 → kanan-kanan

        50
       /  \
      30   70
     / \   / \
    20 40 60  80

🔢 findMin & findMax

findMin

Traverse ke left-most node


BSTNode* findMin(BSTNode* root) {
    if (root == nullptr) 
        return nullptr;
    while (root->left != nullptr)
        root = root->left;
    return root;
}

findMax

Traverse ke right-most node


BSTNode* findMax(BSTNode* root) {
    if (root == nullptr) 
        return nullptr;
    while (root->right != nullptr)
        root = root->right;
    return root;
}

Contoh findMin/findMax

        50
       /  \
      30   70
     / \   / \
    20 40 60  80
   /
  15

findMin:

50 → 30 → 20 → 15

Min = 15

findMax:

50 → 70 → 80

Max = 80

🗑️ Operasi Delete

Tiga kasus yang perlu ditangani:

Kasus	Kondisi	Solusi
1	Node adalah leaf	Hapus langsung
2	Node punya 1 anak	Ganti dengan anaknya
3	Node punya 2 anak	Ganti dengan inorder successor

Kasus 1: Delete Leaf

Gambar 12.5: Penghapusan leaf node

Cukup set parent→child = nullptr

Kasus 2: Delete Node dengan 1 Anak

Gambar 12.6: Penghapusan node dengan satu anak

Bypass: Hubungkan parent langsung ke child

Kasus 3: Delete Node dengan 2 Anak

Gambar 12.7: Penghapusan node dengan dua anak

Inorder Successor

Inorder Successor adalah node dengan nilai terkecil yang lebih besar dari node yang dihapus.

Cara mencari:

findMin(right subtree)

Langkah: Copy nilai successor → Hapus node successor

💻 Implementasi Delete


BSTNode* deleteNode(BSTNode* root, int key) {
    if (root == nullptr) return nullptr;
    
    // Cari node yang akan dihapus
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // Kasus 1 & 2: Leaf atau satu anak
        if (root->left == nullptr) {
            BSTNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            BSTNode* temp = root->left;
            delete root;
            return temp;
        }
        // Kasus 3: Dua anak
        BSTNode* successor = findMin(root->right);
        root->data = successor->data;
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

🧠 Quiz 2: Delete Operation

Pada BST berikut, apa yang terjadi saat delete(50)?

        50
       /  \
      30   70
     / \   / \
    20 40 60  80

Jawaban:

Inorder successor = 60 (min di right subtree)
Copy 60 ke posisi root
Hapus node 60 yang asli (leaf)

        60
       /  \
      30   70
     / \     \
    20 40    80

📊 Analisis Kompleksitas

Operasi	Best	Average	Worst
Search	O(1)	O(log n)	O(n)
Insert	O(1)	O(log n)	O(n)
Delete	O(1)	O(log n)	O(n)
findMin/Max	O(1)	O(log n)	O(n)

Kompleksitas bergantung pada bentuk tree

Balanced vs Skewed BST

Gambar 12.3: Perbandingan BST seimbang dan tidak seimbang

Dampak BST Tidak Seimbang

Bentuk Tree	Tinggi	Operasi
Perfectly Balanced	⌊log₂(n)⌋	O(log n)
Reasonably Balanced	O(log n)	O(log n)
Skewed/Degenerate	n - 1	O(n)

⚠️ Penyebab BST Tidak Seimbang

Insert: 1, 2, 3, 4, 5

Masalah:

Tinggi = n - 1
Search = O(n)
Tidak lebih baik dari Linked List!

🧠 Quiz 3: Kompleksitas

Berapa perbandingan untuk mencari 75?

BST A (Balanced):

      50
     /  \
   25    75
  / \   /  \
10  30 60  90

BST B (Skewed):

10-25-30-50-60-75

BST A: 2

75 > 50 → 75 == 75 ✓

BST B: 6

10→25→30→50→60→75 ✓

BST balanced 3x lebih efisien!

⚖️ Solusi: Balanced BST

Self-balancing BST menjamin O(log n)

Tipe	Mekanisme	Kompleksitas
AVL Tree	Balance factor + rotasi	O(log n) guaranteed
Red-Black Tree	Pewarnaan + rotasi	O(log n) guaranteed
Splay Tree	Splaying	Amortized O(log n)

Detail implementasi: materi lanjutan/pengayaan

Strategi Membangun BST Seimbang

Untuk data {1, 2, 3, 4, 5, 6, 7}:

❌ Urutan: 1,2,3,4,5,6,7

Hasil: Skewed tree

✅ Urutan: 4,2,6,1,3,5,7

Hasil: Balanced tree

(Insert median dulu!)

🎖️ Aplikasi BST: Pertahanan

Sistem Radar dengan Range Query

Mencari semua objek dalam jarak tertentu


void rangeSearch(BSTNode* root, int low, int high, vector<int>& result) {
    if (root == nullptr) return;
    
    if (root->data > low)
        rangeSearch(root->left, low, high, result);
    
    if (root->data >= low && root->data <= high)
        result.push_back(root->data);
    
    if (root->data < high)
        rangeSearch(root->right, low, high, result);
}

Contoh: Range Query

Objek pada jarak: 50, 75, 120, 150, 180, 200, 250 km

Query: Cari objek jarak 100-200 km

Hasil: 120, 150, 180, 200 km

Kompleksitas: O(h + k), h=tinggi, k=hasil

Aplikasi BST Lainnya

Database Index — pencarian cepat berdasarkan key
Symbol Table — compiler dan interpreter
Auto-complete — suggest kata berdasarkan prefix
File System — organisasi direktori
Priority Scheduling — sistem operasi

🔑 Properti Penting: Inorder

Inorder traversal pada BST menghasilkan elemen terurut ascending

        50
       /  \
      30   70
     / \   / \
    20 40 60  80

Inorder: 20, 30, 40, 50, 60, 70, 80

Gunakan untuk: verifikasi BST, print sorted, find k-th element

💻 Class BST Lengkap


class BST {
private:
    struct Node {
        int data;
        Node *left, *right;
        Node(int val) : data(val), left(nullptr), right(nullptr) {}
    };
    Node* root;
    
    // Helper functions...
    
public:
    BST() : root(nullptr) {}
    ~BST() { /* destroy tree */ }
    
    void insert(int value);
    bool search(int key);
    void remove(int key);
    int findMin();
    int findMax();
    void inorderTraversal();
};

Implementasi lengkap: lihat modul12.md

📝 Ringkasan

Konsep	Deskripsi	Kompleksitas
BST Property	Left < Parent < Right	-
Search	Binary search pada tree	O(log n) avg
Insert	Cari posisi, sisipkan	O(log n) avg
Delete (leaf)	Hapus langsung	O(log n) avg
Delete (2 anak)	Inorder successor	O(log n) avg
Worst Case	Skewed tree	O(n)
Balanced BST	AVL, Red-Black	O(log n) guaranteed

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.12 | Weiss Ch.4.3 | Hubbard Ch.11

📚 Tugas

Pelajari modul12.md dan kerjakan Supplementary Problems
Implementasikan class BST dengan semua operasi
Kerjakan latihan12.md
Eksplorasi: Bagaimana AVL Tree melakukan rotasi?

Pertemuan berikutnya: Heap dan Priority Queue

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 12: Binary Search Tree