C++ Binary Search Tree

5 min read Jul 01, 2024

Pohon Pencarian Biner (Binary Search Tree) dalam C++

Pohon pencarian biner (BST) adalah struktur data pohon yang diurutkan, yang berarti bahwa setiap node di pohon memiliki nilai yang lebih besar dari semua node di sub pohon kirinya dan lebih kecil dari semua node di sub pohon kanannya. Struktur ini memungkinkan pencarian, penyisipan, dan penghapusan data yang efisien.

Konsep Dasar BST

Node: Setiap node dalam BST berisi data dan pointer ke dua node anak, yang disebut anak kiri dan anak kanan.
Root: Node teratas dari pohon, tidak memiliki parent.
Leaf: Node yang tidak memiliki anak.
Tinggi: Jarak terpanjang dari root ke leaf.
Depth: Jarak dari root ke node tertentu.

Implementasi BST dalam C++

Berikut adalah implementasi dasar BST dalam C++:

#include 

using namespace std;

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

    Node(int data) {
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
    }
};

class BinarySearchTree {
private:
    Node *root;

public:
    BinarySearchTree() {
        root = nullptr;
    }

    // Fungsi untuk menyisipkan node baru
    void insert(int data) {
        root = insertRecursive(root, data);
    }

    Node* insertRecursive(Node* node, int data) {
        if (node == nullptr) {
            return new Node(data);
        }

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

        return node;
    }

    // Fungsi untuk mencari node berdasarkan data
    Node* search(int data) {
        return searchRecursive(root, data);
    }

    Node* searchRecursive(Node* node, int data) {
        if (node == nullptr || node->data == data) {
            return node;
        }

        if (data < node->data) {
            return searchRecursive(node->left, data);
        } else {
            return searchRecursive(node->right, data);
        }
    }

    // Fungsi untuk menampilkan data BST (in-order traversal)
    void inorderTraversal() {
        inorderTraversalRecursive(root);
    }

    void inorderTraversalRecursive(Node* node) {
        if (node != nullptr) {
            inorderTraversalRecursive(node->left);
            cout << node->data << " ";
            inorderTraversalRecursive(node->right);
        }
    }
};

int main() {
    BinarySearchTree bst;

    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    cout << "Inorder traversal: ";
    bst.inorderTraversal();
    cout << endl;

    int searchKey = 40;
    Node *foundNode = bst.search(searchKey);
    if (foundNode != nullptr) {
        cout << "Node with data " << searchKey << " found!" << endl;
    } else {
        cout << "Node with data " << searchKey << " not found!" << endl;
    }

    return 0;
}

Keuntungan Menggunakan BST

Pencarian Efisien: BST memungkinkan pencarian data yang efisien, dengan kompleksitas waktu rata-rata O(log n).
Penyisipan dan Penghapusan Efisien: Penyisipan dan penghapusan data juga dapat dilakukan dengan efisien, dengan kompleksitas waktu rata-rata O(log n).
Struktur Data yang Terurut: BST mempertahankan data dalam urutan terurut, yang memungkinkan operasi seperti menemukan nilai minimum dan maksimum secara mudah.

Kekurangan Menggunakan BST

Kemungkinan Ketidakseimbangan: Dalam kasus terburuk, BST dapat menjadi tidak seimbang, yang menyebabkan operasi pencarian, penyisipan, dan penghapusan memiliki kompleksitas waktu O(n).
Kompleksitas Implementasi: Implementasi BST dapat menjadi kompleks, terutama untuk operasi seperti penghapusan.

Aplikasi BST

BST digunakan dalam berbagai aplikasi, termasuk:

Database: Untuk menyimpan dan mengurutkan data.
Sistem Pencarian: Untuk mencari informasi dengan cepat.
Sistem Rekomendasi: Untuk membuat rekomendasi berdasarkan data pengguna.
Kompresor Data: Untuk menyimpan dan mengompresi data.

Kesimpulan

BST adalah struktur data yang powerful yang menyediakan pencarian, penyisipan, dan penghapusan data yang efisien. Namun, perlu diingat potensi ketidakseimbangan dan kompleksitas implementasi. Penting untuk memahami keuntungan dan kekurangan BST sebelum menggunakannya dalam aplikasi.