Binary Search Tree

Rinaltra Nabasa S
50252512024
Struktur Data D

Pengertian BST

Binary Search Tree (BST) adalah struktur data hierarkis di mana setiap node mematuhi aturan mutlak: semua nilai pada subtree kiri lebih kecil dari induknya, dan semua nilai pada subtree kanan lebih besar dari induknya.

Poin Utama Materi

• Operasi Dasar: Tiga operasi pilar utama pada BST adalah Pencarian (Search), Penyisipan (Insert), dan Penghapusan (Delete).

• Kompleksitas Waktu: Sangat efisien dengan kecepatan rata-rata O(log n) karena algoritma membuang 50 persen kemungkinan di setiap langkah percabangan turun. Namun, pada kondisi terburuk (worst case ketika tree tidak seimbang atau memanjang), performanya turun drastis menjadi linear O(n).

• Skenario Penghapusan: Terdapat 3 kondisi reorganisasi memori saat menghapus node:

  1. Menghapus leaf node (node yang tidak memiliki anak).

  2. Menghapus node dengan 1 anak.

  3. Menghapus node dengan 2 anak (nilai node perlu digantikan terlebih dahulu oleh Inorder Successor atau Inorder Predecessor sebelum dihapus).

• Evolusi Struktur: Untuk menghindari masalah tree tidak seimbang (degradasi linear menjadi seperti linked list), arsitektur BST dapat ditingkatkan menggunakan struktur Self-Balancing BST seperti AVL Tree atau Red-Black Tree.

Implementasi Dasar C++

Berikut adalah kode C++ sederhana untuk mengimplementasikan proses penyisipan (insert), pencarian (search), dan penelusuran (inorder traversal) pada struktur data BST:

C++

#include <iostream>
using namespace std;

// Struktur node dasar
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Fungsi membuat node baru
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Fungsi Insert (Penyisipan)
Node* insert(Node* root, int value) {
    if (root == NULL) return createNode(value);
    
    // Logika persimpangan: Ke kiri atau ke kanan?
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);
        
    return root;
}

// Fungsi Inorder Traversal (Menampilkan data terurut)
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

// Fungsi Search (Pencarian)
bool search(Node* root, int key) {
    if (root == NULL) return false;
    if (root->data == key) return true; // Target ditemukan
    
    // Navigasi satu arah membuang cabang yang salah
    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

int main() {
    Node* root = NULL;
    
    // Memasukkan contoh data
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);

    cout << "Data Terurut (Inorder): ";
    inorder(root);
    cout << endl;

    int target = 40;
    if (search(root, target)) {
        cout << "Data " << target << " ditemukan!" << endl;
    } else {
        cout << "Data tidak ditemukan." << endl;
    }

    return 0;
}