Binary Search Tree: Implementasi Dasar di C++

Dec 26, 2024

—

Binary Search Tree (BST) adalah struktur data berbentuk pohon di mana setiap node memiliki maksimum dua anak, yaitu anak kiri (left child) dan anak kanan (right child). Nilai pada anak kiri selalu lebih kecil dari nilai di node induk, sedangkan nilai pada anak kanan selalu lebih besar.

Fitur Utama BST

Penyimpanan Terstruktur: Data diatur dalam struktur hierarki.
Operasi Cepat: Waktu pencarian, penyisipan, dan penghapusan rata-rata O(log⁡n)O(\log n) (dalam kasus ideal).
Traversal: Dapat dilakukan dengan metode seperti inorder, preorder, atau postorder.

Operasi Dasar dalam BST

Insert: Menambahkan elemen baru ke BST.
Search: Mencari elemen dalam BST.
Delete: Menghapus elemen dari BST.
Traversal: Menelusuri elemen dalam berbagai urutan.

Implementasi Dasar BST di C++

Berikut adalah implementasi dasar BST yang mencakup operasi insert, search, dan inorder traversal:

#include <iostream>
using namespace std;

// Struktur Node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Kelas BST
class BST {
private:
    Node* root;

    // Fungsi rekursif untuk menyisipkan elemen
    Node* insert(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        }

        return node;
    }

    // Fungsi rekursif untuk mencari elemen
    bool search(Node* node, int value) {
        if (node == nullptr) {
            return false;
        }

        if (value == node->data) {
            return true;
        } else if (value < node->data) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }

    // Fungsi rekursif untuk inorder traversal
    void inorder(Node* node) {
        if (node == nullptr) {
            return;
        }

        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }

public:
    BST() {
        root = nullptr;
    }

    // Menyisipkan elemen ke BST
    void insert(int value) {
        root = insert(root, value);
    }

    // Mencari elemen di BST
    bool search(int value) {
        return search(root, value);
    }

    // Traversal inorder
    void inorder() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    BST tree;

    // Menyisipkan elemen
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);

    // Menampilkan elemen dengan traversal inorder
    cout << "Inorder traversal: ";
    tree.inorder();

    // Mencari elemen
    cout << "Search for 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
    cout << "Search for 25: " << (tree.search(25) ? "Found" : "Not Found") << endl;

    return 0;
}

Penjelasan Kode

Struktur Node:
- Node menyimpan data, pointer ke anak kiri (left), dan pointer ke anak kanan (right).
- Node(int value) adalah konstruktor untuk membuat node baru.
Operasi Insert:
- Menyisipkan elemen baru secara rekursif.
- Jika nilai lebih kecil dari node saat ini, tambahkan ke anak kiri. Jika lebih besar, tambahkan ke anak kanan.
Operasi Search:
- Mencari elemen dengan cara membandingkan nilai dengan data pada node saat ini.
- Pindah ke anak kiri jika nilai lebih kecil, atau ke anak kanan jika lebih besar.
Traversal Inorder:
- Kunjungi anak kiri, kemudian node saat ini, dan akhirnya anak kanan.
- Traversal ini menghasilkan elemen dalam urutan terurut.
Kelas BST:
- Menyediakan metode publik insert, search, dan inorder yang memanggil fungsi rekursif privat.

Output

Inorder traversal: 20 30 40 50 60 70 80
Search for 40: Found
Search for 25: Not Found

Operasi Tambahan

Delete Node:
- Penghapusan lebih kompleks karena harus menangani tiga kasus:
  1. Node tanpa anak.
  2. Node dengan satu anak.
  3. Node dengan dua anak (gantikan dengan inorder successor atau inorder predecessor).
Traversal Lain:
- Preorder: Kunjungi node saat ini, anak kiri, lalu anak kanan.
- Postorder: Kunjungi anak kiri, anak kanan, lalu node saat ini.

Jika Anda ingin menambahkan operasi seperti penghapusan node atau traversal lain, beri tahu saya! 😊