Pertemuan 12 - BTree & BST
BTree & BST di C++
1. Implementasi BTree pada C++
Deskripsi (Fungsi) Program:
B-Tree adalah struktur data pohon pencarian (search tree) yang dapat menyeimbangkan dirinya sendiri (self-balancing). Berbeda dengan Binary Search Tree biasa di mana satu node maksimal hanya memiliki 2 anak (kiri dan kanan), B-Tree merupakan multiway search tree yang dirancang agar satu node dapat menampung banyak key (nilai) dan memiliki banyak anak (children).
Karakteristik Utama B-Tree:
1. Derajat Minimum (Minimum Degree): Biasanya disimbolkan dengan t (atau minDegree dalam kode). Nilai ini menentukan batas jumlah key dan child pada setiap node. Maksimal key per node = 2t - 1. Maksimal child per node = 2t
2. Keseimbangan Sempurna: Semua leaf node (daun terbawah) pasti berada pada level atau kedalaman yang sama.
3. Mekanisme Split (Pemecahan): Ketika sebuah node sudah penuh (mencapai batas maksimal key) dan ada data baru yang ingin dimasukkan, node tersebut akan terbelah menjadi dua. Key yang berada tepat di tengah akan "naik" ke parent node.
4. Efisiensi: Karena B-Tree lebih "lebar" dan tidak terlalu dalam, operasi pencarian (Search), penyisipan (Insert), dan penghapusan (Delete) sangat cepat dengan kompleksitas waktu O(log n). Struktur ini sangat sering digunakan dalam sistem database dan file system.
Kemudian implementasi program yang saya buat terbagi menjadi dua kelas utama: BTreeNode yang mewakili satu lingkaran/blok dalam pohon, dan BTree yang bertindak sebagai pengelola utama.
1. Kelas BTreeNode (Representasi Node)
Kelas ini bertanggung jawab atas data dan operasi yang terjadi di dalam satu node spesifik.
- BTreeNode(int minDegree, bool isLeaf) (Constructor): Saat node baru dibuat, fungsi ini mengalokasikan memori untuk array keys dan array children berdasarkan aturan derajat minimum.
- traverse(): Fungsi untuk mencetak seluruh isi pohon secara berurutan dari terkecil ke terbesar (inorder traversal). Fungsi ini membaca child sebelah kiri, mencetak key, lalu lanjut ke child kanannya.
- search(int key): Melakukan pencarian data. Fungsi ini mencari posisi key. Jika tidak ketemu di node saat ini, ia akan turun ke child yang rentang nilainya sesuai dengan key yang dicari.
- insertNonFull(int key): Fungsi ini hanya dipanggil jika node dipastikan belum penuh. Jika node adalah leaf, data langsung diselipkan pada urutan yang benar. Jika bukan leaf, ia akan mencari jalan turun ke child yang tepat (dan mengecek apakah child tersebut perlu di-split sebelum turun).
- splitChild(int childIndex, BTreeNode* fullChild): Ini adalah jantung dari algoritma B-Tree. Jika fullChild sudah penuh, fungsi ini akan membaginya menjadi dua node terpisah. Nilai yang berada di tengah akan dipindahkan ke node parent untuk menjaga struktur tetap seimbang.
2. Kelas BTree (Pengelola Pohon)
Kelas ini adalah jembatan penghubung antara programmer dan struktur pohon secara keseluruhan. Ia hanya menyimpan pointer ke titik awal pohon, yaitu root.
- BTree(int minDegree) (Constructor): Menginisialisasi pohon kosong dengan menetapkan nilai root menjadi kosong (nullptr).
- search(int key) & traverse(): Fungsi pembungkus (wrapper). Keduanya hanya memanggil fungsi search dan traverse milik root (jika pohon tidak kosong).
- insert(int key): Fungsi utama penyisipan dari luar: Jika pohon kosong, ia membuat root baru. Jika root yang ada saat ini sudah penuh, fungsi ini akan membuat node root baru, lalu memanggil splitChild untuk membelah root lama, kemudian baru memasukkan data. Jika root belum penuh, ia langsung mengoper tugasnya ke insertNonFull.
Code:
#include <bits/stdc++.h>
class BTreeNode {private: int* keys; int minDegree; BTreeNode** children; int numKeys; bool isLeaf;
public: BTreeNode(int minDegree, bool isLeaf);
void traverse() const; BTreeNode* search(int key); void insertNonFull(int key); void splitChild(int childIndex, BTreeNode* fullChild);
friend class BTree;};
class BTree {private: BTreeNode* root; int minDegree;
public: explicit BTree(int minDegree) : root(nullptr), minDegree(minDegree) {}
void traverse() const { if (root != nullptr) { root->traverse(); } }
BTreeNode* search(int key) { return (root == nullptr) ? nullptr : root->search(key); }
void insert(int key);};
BTreeNode::BTreeNode(int minDegree, bool isLeaf) : minDegree(minDegree), isLeaf(isLeaf), numKeys(0) { keys = new int[2 * minDegree - 1]; children = new BTreeNode*[2 * minDegree];}
void BTreeNode::traverse() const { int i; for (i = 0; i < numKeys; i++) { if (!isLeaf) { children[i]->traverse(); } std::cout << keys[i] << " "; } if (!isLeaf) { children[i]->traverse(); }}
BTreeNode* BTreeNode::search(int key) { int i = 0; while (i < numKeys && key > keys[i]) { i++; }
if (i < numKeys && keys[i] == key) { return this; }
if (isLeaf) { return nullptr; }
return children[i]->search(key);}
void BTree::insert(int key) { if (root == nullptr) { root = new BTreeNode(minDegree, true); root->keys[0] = key; root->numKeys = 1; return; }
if (root->numKeys == 2 * minDegree - 1) { BTreeNode* newRoot = new BTreeNode(minDegree, false); newRoot->children[0] = root; newRoot->splitChild(0, root);
int i = (newRoot->keys[0] < key) ? 1 : 0; newRoot->children[i]->insertNonFull(key);
root = newRoot; } else { root->insertNonFull(key); }}
void BTreeNode::insertNonFull(int key) { int i = numKeys - 1;
if (isLeaf) { while (i >= 0 && keys[i] > key) { keys[i + 1] = keys[i]; i--; } keys[i + 1] = key; numKeys++; } else { while (i >= 0 && keys[i] > key) { i--; }
if (children[i + 1]->numKeys == 2 * minDegree - 1) { splitChild(i + 1, children[i + 1]);
if (keys[i + 1] < key) { i++; } } children[i + 1]->insertNonFull(key); }}
void BTreeNode::splitChild(int childIndex, BTreeNode* fullChild) { BTreeNode* newNode = new BTreeNode(fullChild->minDegree, fullChild->isLeaf); newNode->numKeys = minDegree - 1;
for (int j = 0; j < minDegree - 1; j++) { newNode->keys[j] = fullChild->keys[j + minDegree]; }
if (!fullChild->isLeaf) { for (int j = 0; j < minDegree; j++) { newNode->children[j] = fullChild->children[j + minDegree]; } }
fullChild->numKeys = minDegree - 1;
for (int j = numKeys; j >= childIndex + 1; j--) { children[j + 1] = children[j]; } children[childIndex + 1] = newNode;
for (int j = numKeys - 1; j >= childIndex; j--) { keys[j + 1] = keys[j]; } keys[childIndex] = fullChild->keys[minDegree - 1]; numKeys++;}
int main(void) { BTree tree(2);
int valuesToInsert[] = {10, 20, 30, 40, 50, 60, 70, 80}; for (int value : valuesToInsert) { tree.insert(value); }
std::cout << "B-Tree Traversal: "; tree.traverse(); std::cout << "\n";
int searchKey = 50; std::cout << "Searching for " << searchKey << "...\n"; if (tree.search(searchKey) != nullptr) { std::cout << "Key " << searchKey << " found in the B-Tree.\n"; } else { std::cout << "Key " << searchKey << " NOT found.\n"; }
return 0;}
Hasil/Output Program:
Penjelasan Program:
2. Implementasi BST pada C++
Deskripsi (Fungsi) Program:
Binary Search Tree (BST) adalah struktur data pohon biner yang memiliki aturan pengurutan khusus untuk mempercepat proses pencarian, penyisipan, dan penghapusan data. Aturan utamanya adalah: nilai pada subtree kiri harus selalu lebih kecil dari nilai root (induknya), dan nilai pada subtree kanan harus selalu lebih besar dari root.
1. Insert (Penyisipan): Menambahkan node baru dengan membandingkan nilainya terhadap root; jika lebih kecil turun ke kiri, jika lebih besar turun ke kanan, hingga menemukan posisi kosong (leaf).
2. Search (Pencarian): Mencari nilai tertentu dengan prinsip membagi ruang pencarian. Pencarian menelusuri cabang kiri atau kanan tergantung apakah nilai yang dicari lebih kecil atau lebih besar dari node saat ini.
3. Delete (Penghapusan): Merupakan operasi paling kompleks karena harus mempertahankan struktur BST. Ada 3 skenario yang terjadi:
- Menghapus Leaf Node: Node tidak punya anak, sehingga bisa langsung dihapus.
- Menghapus Node dengan 1 Anak: Node dihapus, dan posisinya digantikan langsung oleh anak tunggalnya tersebut.
- Menghapus Node dengan 2 Anak: Node digantikan oleh Inorder Successor (nilai terkecil dari subtree sebelah kanan), kemudian successor di posisi asalnya tersebut dihapus.
4. Traversal: Cara mengunjungi seluruh node di dalam BST. Terdapat 3 jenis yaitu Inorder (Kiri-Root-Kanan), Preorder (Root-Kiri-Kanan), dan Postorder (Kiri-Kanan-Root).
Deskripsi Fungsi dalam Program C++ BST
1. Struktur Node
Node (Struct): Merepresentasikan satu titik/lingkaran dalam pohon. Memiliki 3 bagian utama: value untuk menyimpan angka, left (pointer ke anak kiri), dan right (pointer ke anak kanan).
2. Fungsi Internal / Rekursif (private)
Fungsi-fungsi ini bekerja di balik layar dan membutuhkan pointer Node secara spesifik untuk memanipulasi struktur pohon:
- insert(Node* node, int value): Bergerak turun dari root ke bawah. Jika nilai baru lebih kecil, fungsi memanggil dirinya sendiri ke node->left. Jika mencapai ujung bawah (nullptr), ia membuat Node baru.
- search(Node* node, int value): Mengecek nilai node saat ini. Jika cocok, mengembalikan node tersebut. Jika tidak, akan memanggil dirinya sendiri ke kiri atau ke kanan hingga menemukan nilai tersebut atau mencapai nullptr (tidak ditemukan).
- findMin(Node* node): Mencari Inorder Successor dengan cara terus bergerak ke anak kiri (node->left) hingga mentok. Nilai ujung kiri ini adalah nilai terkecil pada suatu cabang/subtree.
- remove(Node* node, int value): Melakukan operasi Delete berdasarkan 3 kondisi dari dokumen. Jika node memiliki 2 anak, fungsi ini akan memanggil findMin untuk mencari successor, menimpa nilai node saat ini dengan nilai successor, lalu memanggil remove lagi untuk menghapus successor di bawahnya.
- inorder, preorder, postorder: Mengunjungi dan mencetak node menggunakan rekursi berdasar aturan letak pencetakan node->value (di tengah, di awal, atau di akhir pemanggilan).
3. Fungsi Antarmuka / Pembungkus (public)
- BST() (Constructor): Mengatur pohon awal dengan root = nullptr (pohon kosong).
- insert(int value): Memanggil fungsi rekursif insert dengan memberikan root sebagai titik awal.
- search(int value): Mengembalikan nilai boolean (true jika fungsi search internal mengembalikan node, atau false jika mengembalikan nullptr).
- remove(int value): Memulai proses penghapusan rekursif dari root.
- printInorder(), printPreorder(), printPostorder(): Mencetak teks pengantar lalu menjalankan fungsi rekursi traversal dari root.
Code:
#include <iostream>
struct Node { int value; Node* left; Node* right;
explicit Node(int val) : value(val), left(nullptr), right(nullptr) {}};
class BST {private: Node* root;
Node* insert(Node* node, int value) { if (node == nullptr) { return new Node(value); }
if (value < node->value) { node->left = insert(node->left, value); } else if (value > node->value) { node->right = insert(node->right, value); } return node; }
Node* search(Node* node, int value) const { if (node == nullptr || node->value == value) { return node; }
if (value < node->value) { return search(node->left, value); }
return search(node->right, value); }
Node* findMin(Node* node) const { Node* current = node; while (current && current->left != nullptr) { current = current->left; } return current; }
Node* remove(Node* node, int value) { if (node == nullptr) { return nullptr; }
if (value < node->value) { node->left = remove(node->left, value); } else if (value > node->value) { node->right = remove(node->right, value); } else { if (node->left == nullptr) { Node* temp = node->right; delete node; return temp; } else if (node->right == nullptr) { Node* temp = node->left; delete node; return temp; }
Node* temp = findMin(node->right); node->value = temp->value; node->right = remove(node->right, temp->value); } return node; }
void inorder(Node* node) const { if (node != nullptr) { inorder(node->left); std::cout << node->value << " "; inorder(node->right); } }
void preorder(Node* node) const { if (node != nullptr) { std::cout << node->value << " "; preorder(node->left); preorder(node->right); } }
void postorder(Node* node) const { if (node != nullptr) { postorder(node->left); postorder(node->right); std::cout << node->value << " "; } }
public: BST() : root(nullptr) {}
void insert(int value) { root = insert(root, value); }
bool search(int value) const { return search(root, value) != nullptr; }
void remove(int value) { root = remove(root, value); }
void printInorder() const { std::cout << "Inorder : "; inorder(root); std::cout << "\n"; }
void printPreorder() const { std::cout << "Preorder : "; preorder(root); std::cout << "\n"; }
void printPostorder() const { std::cout << "Postorder : "; postorder(root); std::cout << "\n"; }};
int main() { BST tree;
int valuesToInsert[] = {50, 30, 70, 20, 40, 60, 80}; for (int val : valuesToInsert) { tree.insert(val); }
tree.printInorder(); tree.printPreorder(); tree.printPostorder();
std::cout << "\n"; int target = 60; if (tree.search(target)) { std::cout << "Key " << target << " found in BST.\n"; } else { std::cout << "Key " << target << " NOT found in BST.\n"; }
std::cout << "Removing 50...\n"; tree.remove(50); tree.printInorder();
return 0;}
Hasil/Output Program:
Komentar
Posting Komentar