Struktur Data - B Tree dan BST

Nama    : Aga Nafta Filadelfiano
NRP      : 5025251055
Kelas     : Struktur Data (D) 

B Tree dan BST


1. Implementasi B Tree pada C++

Deskripsi:

B-Tree adalah struktur data pohon pencarian 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:
  • 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
  • Keseimbangan Sempurna: Semua leaf node (daun terbawah) pasti berada pada level atau kedalaman yang sama.
  • 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.
  • 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.

Implementasi Program:

a. Kelas BTreeNode (Representasi Node)
  • 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.

b. Kelas BTree (Pengelola Pohon)
  • 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.

Syntax Program:



Output:



Penjelasan 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;
};
Mendefinisikan kelas BTreeNode yang merepresentasikan sebuah node (simpul) di dalam B-Tree. Kelas ini menyimpan array data (keys), pointer ke node anak (children), jumlah data saat ini (numKeys), batas minimum derajat pohon (minDegree), status apakah node tersebut adalah daun (isLeaf), serta deklarasi fungsi-fungsi manipulasi node.

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);
};
Mendefinisikan kelas utama BTree untuk mengelola seluruh struktur pohon. Kelas ini bertindak sebagai wrapper atau jembatan yang menyimpan pointer ke simpul akar (root) dan memanggil fungsi internal milik BTreeNode (seperti traverse dan search) dimulai dari akar pohon tersebut.

BTreeNode::BTreeNode(int minDegree, bool isLeaf) 
    : minDegree(minDegree), isLeaf(isLeaf), numKeys(0) {
    keys = new int[2 * minDegree - 1];
    children = new BTreeNode*[2 * minDegree];
}
Merupakan constructor dari BTreeNode untuk mengalokasikan memori secara dinamis bagi array keys  dan array children saat sebuah node baru dibuat.

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();
    }
}
Melakukan penelusuran (traversal) seluruh data di dalam pohon secara berurutan (in-order). Fungsi ini akan mengunjungi anak sub-pohon di sebelah kiri sebuah kunci terlebih dahulu, mencetak kunci tersebut, lalu melanjutkan ke anak sub-pohon berikutnya secara rekursif hingga semua data tercetak berurutan dari terkecil ke terbesar.

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);
}
Penjelasan:Melakukan pencarian sebuah kunci (key) di dalam node saat ini menggunakan perulangan. Jika kunci ditemukan, fungsi mengembalikan pointer node tersebut; jika tidak ditemukan dan node adalah daun (leaf), fungsi mengembalikan nullptr; jika bukan daun, fungsi akan mencari secara rekursif ke node anak yang sesuai.

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);
    }
}
Fungsi utama untuk memasukkan kunci baru ke dalam B-Tree dengan dua kondisi utama:Jika pohon kosong, langsung membuat simpul akar (root) baru.Jika pohon tidak kosong, fungsi akan memeriksa apakah akar sudah penuh. Jika penuh, pohon akan tumbuh ke atas dengan memecah akar lama (splitChild) dan membuat akar baru sebelum melakukan penyisipan; jika tidak penuh, langsung memanggil insertNonFull.

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);
    }
}
Memasukkan kunci baru ke dalam simpul yang dipastikan belum penuh (non-full). Jika simpul tersebut adalah daun, kunci langsung disisipkan pada posisi yang tepat secara berurutan; jika bukan daun, fungsi akan turun ke simpul anak yang tepat, dan jika simpul anak tersebut penuh, fungsi akan memecahnya terlebih dahulu menggunakan splitChild sebelum melanjutkan proses penyisipan secara rekursif.

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++;
}
Memecah sebuah simpul anak yang penuh (fullChild) menjadi dua simpul yang lebih kecil. Kunci median (nilai tengah) dari simpul anak tersebut akan dinaikkan ke simpul induk saat ini, sedangkan sisa kunci bagian kanan dipindahkan ke simpul baru (newNode) yang baru saja dibuat.

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;
}
Fungsi utama program (driver code) yang mendemonstrasikan penggunaan B-Tree dengan derajat minimum 2. Alur program ini membuat objek pohon, memasukkan serangkaian angka (10 hingga 80), menampilkan seluruh isi pohon secara berurutan, dan melakukan simulasi pencarian angka 50 di dalam pohon tersebut.

2. Implementasi BST pada C++

Deskripsi:
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.
  • 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).
  • 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.
  • 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.
  • 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
  • Struktur Node: 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).
  • Fungsi Internal / Rekursif (private)
    • 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).
  • 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.

Syntax Program:


Output:


Penjelasan Code:
#include <iostream>

struct Node {
    int value;
    Node* left;
    Node* right;

    explicit Node(int val) : value(val), left(nullptr), right(nullptr) {}
};
Mendefinisikan struktur Node yang menjadi komponen dasar penyusun pohon. Setiap node menyimpan satu data integer (value) serta dua buah pointer (left dan right) untuk menunjuk ke cabang anak sebelah kiri dan anak sebelah kanan yang awalnya diatur kosong (nullptr).

class BST {
private:
    Node* root;
Mendefinisikan kelas utama bernama BST untuk membungkus seluruh fungsionalitas pohon biner. Di dalam bagian private, kelas ini menyimpan pointer root yang berfungsi sebagai titik puncak atau gerbang utama untuk mengakses seluruh node di dalam pohon.

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;
    }
Fungsi internal (rekursif) untuk menyisipkan data baru ke dalam pohon. Sesuai aturan BST, jika nilai baru lebih kecil dari nilai node saat ini, fungsi akan berbelok ke cabang kiri; jika lebih besar, fungsi akan berbelok ke cabang kanan, hingga menemukan posisi kosong (nullptr) untuk membuat node baru.

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);
    }
Fungsi internal (rekursif) untuk mencari keberadaan suatu nilai di dalam pohon. Proses pencarian memanfaatkan sifat BST: jika nilai yang dicari lebih kecil dari node sekarang maka pencarian berlanjut ke kiri, dan jika lebih besar akan berlanjut ke kanan sampai nilai ditemukan atau sampai menabrak pointer kosong.

Node* findMin(Node* node) const {
        Node* current = node;
        while (current && current->left != nullptr) {
            current = current->left;
        }
        return current;
    }
Fungsi pembantu untuk mencari nilai terkecil pada sub-pohon tertentu. Sesuai karakteristik BST, nilai terkecil selalu berada pada node yang terletak di ujung paling kiri bawah, sehingga fungsi ini cukup melakukan perulangan terus-menerus ke arah pointer left.

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;
    }
Fungsi internal (rekursif) untuk menghapus node berdasarkan nilai yang dicari dengan menangani 3 kondisi:Node daun (tidak punya anak): Node langsung dihapus dan mengembalikan nullptr.Node dengan 1 anak: Node dihapus, lalu posisinya digantikan oleh satu-satunya anak yang ia miliki (kiri atau kanan).Node dengan 2 anak: Nilai node tersebut diganti dengan nilai terkecil dari sub-pohon sebelah kanannya (findMin(node->right)), kemudian node asli yang memiliki nilai terkecil tersebut dihapus.

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 << " ";
        }
    }
Tiga metode rekursif untuk menelusuri (traversal) dan mencetak seluruh data di dalam pohon dengan urutan berbeda:
  • Inorder: Menelusuri Kiri --> Cetak Node --> Kanan (Menghasilkan cetakan angka yang terurut dari terkecil ke terbesar)
  • Preorder: Cetak Node --> Menelusuri Kiri --> Kanan
  • Postorder: Menelusuri Kiri --> Kanan --> Cetak Node

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";
    }
};
Bagian public dari kelas BST yang menyediakan fungsi antarmuka (interface) bagi pengguna luar. Fungsi-fungsi ini tidak memerlukan pointer root sebagai argumen dari luar, melainkan langsung meneruskan operasi panggilan tersebut ke fungsi privat internal dengan menyisipkan pointer root secara otomatis.

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;
}
Fungsi utama program (driver code) untuk mendemonstrasikan cara kerja kelas BST. Alurnya meliputi: inisialisasi objek pohon, menyisipkan 7 buah data, mencetak isi pohon dengan 3 jenis teknik traversal, melakukan pencarian angka 60, menghapus angka 50 (yang bertindak sebagai root awal), dan mencetak kembali hasil akhir pohon setelah penghapusan.

Source Code: GitHub

Postingan populer dari blog ini

Curiculum Vitae - Aga Nafta Filadelfiano

Gambar
Nama       : Aga Nafta Filadelfiano NRP          : 5025251055 Kelas        : Struktur Data (D) Aga Nafta Filadelfiano Marina Emas Timur - Kota Surabaya 60111 - aganafta1667@gmail.com - 085748483716 DESKRIPSI DIRI      Mahasiswa S1-Teknik Informatika Institut Teknologi Sepuluh Nopember (ITS) yang diterima melalui jalur Seleksi Nasional Berdasarkan Prestasi (SNBP). Memiliki ketertarikan dan kemampuan dalam bidang teknologi, analisa data, dan berpartisipasi baik dalam bidang akademik maupun non-akademik. Dikenal sebagai pribadi yang disiplin, memiliki semangat belajar tinggi, serta menjunjung nilai kerja sama dan tanggung jawab. PENDIDIKAN INSTITUT TEKNOLOGI SEPULUH NOPEMBER S1 Teknik Informatika (2025 - Sekarang) IPK Sementara : 4.0/4.0 SMA Negeri 2 Madiun (2022 - 2025) Nilai Akhir : 92.11/100.00 PENGALAMAN UKM MUSIK ITS - Anggota September 2025 - Sekarang ( Surabaya, Jawa Timur) INI LHO ITS X SUMMITS -...
Baca selengkapnya

Struktur Data - Studi Kasus Stack

Gambar
Nama    : Aga Nafta Filadelfiano NRP      : 5025251055 Kelas     : Struktur Data (D)   Studi Kasus Stack 1. Konversi Infix ke Postfix Infix adalah notasi yang menempatkan operator di antara dua operand ( A + B ), sedangkan Postfix menempatkan operator setelah operand (contoh: A B + ). Prosedur Konversi Infix ke Postfix Baca (scan) ekspresi infix dari kiri ke kanan. Jika simbol yang dibaca adalah tanda kurung buka '(' , maka Push ke dalam stack. Jika simbol adalah operand (nilai/variabel) tambahkan ke hasil postfix (output). Jika simbol adalah tanda kurung tutup ')' : Pop semua elemen dari stack Tambahkan ke postfix Lakukan sampai ditemukan pasangan tanda kurung buka '(' Buang tanda kurung buka tersebut (tidak dimasukkan ke output) Jika simbol adalah operator (+, -, *, /, dll): Selama Stack tidak kosong, dan Operator di atas stack memiliki prioritas lebih tinggi atau sama,...
Baca selengkapnya

Struktur Data - Tipe Data & Array

Gambar
Nama  : Aga Nafta Filadelfiano NRP    : 5025251055 Kelas   : Struktur Data (D) TIPE DATA & ARRAY 1. Deklarasi Array Array adalah struktur data yang digunakan untuk menyimpan banyak data dengan tipe yang sama dalam satu variabel . Setiap data dalam array memiliki indeks yang dimulai dari 0 . Syntax Program Output Penjelasan int myarray[] = {1,3,5,2,4,6}; Membuat array bernama myarray dengan tipe data  int yang  berisi 6 elemen cout << myarray[i] << " "; Mencetak nilai array sesuai indeks i 2. Mencetak Alamat pada Indeks Array Setiap elemen array disimpan di alamat memori yang berbeda . Alamat memori bisa diketahui menggunakan operator &. Syntax Program Output Penjelasan cout << myarray[i] << endl; Menampilkan isi array &myarray[i]   & berarti address of 3. Input Array Array dapat diisi langsung oleh user  menggunakan input cin . Syntax Program Output Penjelasan Menerima input dari user : for (int ...
Baca selengkapnya