BST and B-tree

Rinaltra Nabasa S
5025251024
Struktur Data DD

1. Binary Search Tree (BST)

Pengertian

Binary Search Tree (BST) adalah struktur data pohon biner yang memiliki aturan khusus pada tiap nodenya:

• Nilai pada subtree kiri selalu lebih kecil dari nilai root (nilai_kiri < root).

• Nilai pada subtree kanan selalu lebih besar dari nilai root (root < nilai_kanan).

Setiap subtree di dalamnya juga harus memenuhi aturan BST. Karakteristik ini membuat proses pencarian data menjadi jauh lebih efisien dibandingkan menggunakan array atau linked list biasa.

Struktur Tree

Berikut adalah representasi visual dari sebuah BST:

Plaintext

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

Operasi pada BST

• Search: Membandingkan data yang dicari mulai dari root. Jika lebih kecil, pencarian bergerak ke kiri; jika lebih besar, bergerak ke kanan.

• Insert: Menelusuri tree untuk menemukan posisi kosong (daun) yang sesuai dengan aturan BST, kemudian menyisipkan node baru di sana.

• Delete: Proses penghapusan data dibagi menjadi 3 skenario:

  1. Leaf node (tidak punya child) -> bisa langsung dihapus.

  2. 1 child -> node dihapus, lalu posisinya digantikan oleh child-nya.

  3. 2 child -> node diganti dengan inorder successor (nilai terkecil di subtree sebelah kanan), baru kemudian menghapus node asal.

Traversal (Penelusuran)

• Inorder (Kiri -> Root -> Kanan): Menghasilkan data yang otomatis terurut secara ascending.

  Hasil: 20 30 40 50 60 70 80

• Preorder (Root -> Kiri -> Kanan): Hasil: 50 30 20 40 70 60 80

• Postorder (Kiri -> Kanan -> Root): Hasil: 20 40 30 60 80 70 50

Kompleksitas BST

Operasi	Best Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Catatan Penting: Kondisi worst case terjadi ketika data dimasukkan secara terurut (misal: 10, 20, 30, 40). Hal ini membuat struktur tree menjadi miring (skewed tree) dan menyerupai linked list.

Implementasi C++ (BST)

C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

// Insert
Node* insert(Node* root, int data) {
    if (root == nullptr) return new Node(data);
    if (data < root->data)
        root->left  = insert(root->left,  data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

// Search
bool search(Node* root, int data) {
    if (root == nullptr) return false;
    if (data == root->data) return true;
    if (data < root->data)  return search(root->left,  data);
    return search(root->right, data);
}

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

// Cari node terkecil (untuk delete)
Node* minNode(Node* root) {
    while (root->left != nullptr)
        root = root->left;
    return root;
}

// Delete
Node* deleteNode(Node* root, int data) {
    if (root == nullptr) return root;
    if (data < root->data)
        root->left  = deleteNode(root->left,  data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // Leaf atau 1 child
        if (root->left == nullptr) {
            Node* tmp = root->right;
            delete root;
            return tmp;
        }
        if (root->right == nullptr) {
            Node* tmp = root->left;
            delete root;
            return tmp;
        }
        // 2 child: ganti dengan inorder successor
        Node* succ   = minNode(root->right);
        root->data   = succ->data;
        root->right  = deleteNode(root->right, succ->data);
    }
    return root;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);

    cout << "Inorder awal: ";
    inorder(root);            
    cout << endl;

    cout << "Apakah 40 ada? " << (search(root, 40) ? "Ada (1)" : "Tidak (0)") << endl; 

    root = deleteNode(root, 30);
    cout << "Inorder setelah node 30 dihapus: ";
    inorder(root);            
    cout << endl;

    return 0;
}

Output Program BST:

2. B-Tree

Pengertian

B-Tree adalah struktur data self-balancing multiway search tree. Berbeda dengan BST yang nodenya maksimal hanya memiliki 2 child, satu node pada B-Tree dapat menyimpan banyak key (kunci data) dan memiliki banyak child. Struktur ini dirancang khusus untuk sistem database dan file system guna meminimalkan operasi akses disk (I/O).

Aturan B-Tree (Order = m)

• Maksimal child per node: m

• Maksimal key per node: m - 1

• Minimal child (selain root): pembulatan ke atas dari (m/2)

• Semua leaf node wajib berada di level yang sama (menjamin tree selalu seimbang atau balanced).

• Key di dalam satu node selalu tersusun secara terurut.

Struktur Tree (Order 3)

Plaintext

         [30  60]
        /    |    \
   [10 20] [40 50] [70 80]

Operasi pada B-Tree

• Search: Pencarian dimulai dari root, membandingkan key di dalam node, lalu memilih pointer child yang sesuai secara berulang hingga data ditemukan atau mencapai leaf.

• Insert: Penambahan data selalu dilakukan pada leaf node. Jika node tersebut penuh (overflow), dilakukan operasi split (pembelahan): nilai tengah akan naik menjadi parent, dan sisa key dipecah menjadi dua node baru.

• Delete: Penghapusan data dari node. Jika jumlah key menjadi di bawah batas minimal (underflow), struktur diperbaiki dengan meminjam (borrow) dari sibling atau melakukan penggabungan node (merge).

Contoh Operasi Split (Order 3)

Ketika kita memasukkan angka 30 ke dalam node leaf yang sudah berisi [10 20] (kondisi penuh):

Plaintext

Sebelum:  [10  20  30]   <-- Terjadi Overflow

Sesudah: [20]       <-- Key tengah (20) naik ke parent
                 /    \
            [10]    [30]

Kompleksitas B-Tree

Operasi	Kompleksitas (Rata-rata & Worst Case)
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

Implementasi C++ (B-Tree Order 3)

#include <iostream>
#include <vector>
using namespace std;
const int ORDER = 3;
struct BNode {
  vector<int> keys;
  vector<BNode *> children;
  bool isLeaf;
  BNode(bool leaf) : isLeaf(leaf) {}
};
class BTree {
  BNode *root;
  void splitChild(BNode *p, int i) {
    BNode *child = p->children[i];
    BNode *newNode = new BNode(child->isLeaf);
    int mid = ORDER / 2;
    int midKey = child->keys[mid];
    newNode->keys.assign(child->keys.begin() + mid + 1, child->keys.end());
    child->keys.resize(mid);
    if (!child->isLeaf) {
      newNode->children.assign(child->children.begin() + mid + 1,
                               child->children.end());
      child->children.resize(mid + 1);
    }
    p->keys.insert(p->keys.begin() + i, midKey);
    p->children.insert(p->children.begin() + i + 1, newNode);
  }
  void insertNonFull(BNode *node, int key) {
    int i = node->keys.size() - 1;
    if (node->isLeaf) {
      node->keys.push_back(0);
      while (i >= 0 && key < node->keys[i]) {
        node->keys[i + 1] = node->keys[i];
        i--;
      }
      node->keys[i + 1] = key;
    } else {
      while (i >= 0 && key < node->keys[i])
        i--;
      i++;
      if ((int)node->children[i]->keys.size() == ORDER - 1) {
        splitChild(node, i);
        if (key > node->keys[i])
          i++;
      }
      insertNonFull(node->children[i], key);
    }
  }
  void inorder(BNode *node) {
    if (!node)
      return;
    int n = node->keys.size();
    for (int i = 0; i < n; i++) {
      if (!node->isLeaf)
        inorder(node->children[i]);
      cout << node->keys[i] << " ";
    }
    if (!node->isLeaf)
      inorder(node->children[n]);
  }
  bool search(BNode *node, int key) {
    int i = 0;
    while (i < (int)node->keys.size() && key > node->keys[i])
      i++;
    if (i < (int)node->keys.size() && key == node->keys[i])
      return true;
    if (node->isLeaf)
      return false;
    return search(node->children[i], key);
  }
public:
  BTree() { root = new BNode(true); }
  void insert(int key) {
    if ((int)root->keys.size() == ORDER - 1) {
      BNode *newRoot = new BNode(false);
      newRoot->children.push_back(root);
      splitChild(newRoot, 0);
      root = newRoot;
    }
    insertNonFull(root, key);
  }
  bool search(int key) { return search(root, key); }
  void inorder() {
    inorder(root);
    cout << endl;
  }
};
int main() {
  BTree bt;
  bt.insert(10);
  bt.insert(20);
  bt.insert(30);
  bt.insert(40);
  bt.insert(50);
  cout << "Inorder Traversal B-Tree: ";
  bt.inorder();
  
  cout << "Pencarian 30: " << (bt.search(30) ? "Ditemukan" : "Tidak Ditemukan") << endl;
  cout << "Pencarian 99: " << (bt.search(99) ? "Ditemukan" : "Tidak Ditemukan") << endl;
  return 0;
}

Output

3. Tabel Perbandingan: BST vs B-Tree

Aspek	Binary Search Tree (BST)	B-Tree
Jumlah Child	Maksimal 2 child per node	Banyak child (sesuai nilai order m)
Keseimbangan Tree	Tidak selalu seimbang (bisa timpang)	Selalu seimbang (self-balancing)
Tinggi Tree (Height)	Bisa sangat tinggi atau dalam	Selalu pendek atau landai
Worst Case	O(n)	O(log n)
Akses Disk / Storage	Banyak (kurang efisien untuk storage besar)	Minim (sangat efisien untuk I/O disk)
Media Penyimpanan	Paling cocok untuk data di memori utama (RAM)	Sangat cocok untuk Database / File System
Kompleksitas Kode	Relatif mudah diimplementasikan	Cukup kompleks karena penanganan split & merge