Tugas Pertemuan ke-13 · Struktur Data - D

Implementasi & Studi Kasus
Binary Search Tree

Memahami cara kerja BST dari konsep dasar, insert, search, traversal, hingga penerapannya pada sistem ranking game online menggunakan C++.

GitHub Repository

Mata KuliahStruktur Data - D

Pertemuanke-13

BahasaC++

Topik UtamaBinary Search Tree (BST)

Apa Itu Binary Search Tree?

Binary Search Tree (BST) adalah struktur data berbentuk pohon (tree) yang menyimpan data secara terurut. Setiap node memiliki maksimal dua anak — kiri dan kanan — dengan aturan ketat: nilai kiri selalu lebih kecil dari node induk, dan nilai kanan selalu lebih besar. Berkat aturan ini, pencarian data jauh lebih efisien dibanding pencarian linear biasa.

Komponen Utama dalam BST

🌱

Root Node paling atas, titik awal seluruh tree

🔗

Parent Node yang memiliki satu atau dua anak (child)

🌿

Child Node turunan langsung dari parent-nya

🍃

Leaf Node paling ujung yang tidak punya anak

🌲

Subtree Bagian dari tree yang juga memenuhi aturan BST

Aturan Dasar BST

Nilai di subtree kiri harus lebih kecil dari nilai node induknya.

Nilai di subtree kanan harus lebih besar dari nilai node induknya.

Tidak boleh ada nilai yang duplikat dalam satu BST.

Setiap subtree kiri dan kanan juga harus merupakan BST yang valid.

Visualisasi Struktur BST

         50          ← Root
        /  \
      30    70       ← Level 1
     / \    / \
   20  40  60  80   ← Leaf Nodes

Inorder traversal → 20 · 30 · 40 · 50 · 60 · 70 · 80 (terurut ascending)

Operasi yang Diimplementasikan

insert()

Insert Menambahkan node baru sesuai aturan BST

search()

Search Mencari nilai tertentu di dalam tree

inorder()

Traversal Menelusuri seluruh node secara terurut

Program 1 — Implementasi BST Dasar

Program pertama mengimplementasikan BST fundamental: membuat node, memasukkan data, melakukan Inorder Traversal, dan mencari nilai tertentu.

bst_dasar.cpp C++

#include <iostream>
using namespace std;

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

Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data  = value;
    newNode->left  = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->data)
        root->left  = insert(root->left,  value);
    else if (value > root->data)
        root->right = insert(root->right, value);
    return root;
}

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

bool search(Node* root, int key) {
    if (root == NULL)        return false;
    if (root->data == key)   return true;
    if (key < root->data)
        return search(root->left,  key);
    else
        return search(root->right, key);
}

int main() {
    Node* root = NULL;

    root = insert(root, 50);
    insert(root, 30);  insert(root, 70);
    insert(root, 20);  insert(root, 40);
    insert(root, 60);  insert(root, 80);

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

    int key = 60;
    if (search(root, key))
        cout << "Data ditemukan" << endl;
    else
        cout << "Data tidak ditemukan" << endl;

    return 0;
}

Output Program

Terminal Output

Inorder Traversal: 20 30 40 50 60 70 80

Data ditemukan

Penjelasan Fungsi-Fungsi Utama

struct NodeMendefinisikan node BST: menyimpan nilai data, pointer ke anak kiri, dan pointer ke anak kanan.
createNode()Membuat node baru di heap memory dengan nilai yang diberikan, lalu mengembalikan pointer-nya.
insert()Memasukkan nilai baru ke posisi yang tepat secara rekursif — ke kiri jika lebih kecil, ke kanan jika lebih besar.
inorder()Traversal Left → Root → Right, menghasilkan data yang otomatis terurut dari kecil ke besar.
search()Mencari nilai secara rekursif — setengah tree bisa langsung diabaikan tiap langkahnya, jauh lebih efisien dari linear search.

Program 2 — Studi Kasus: Ranking Game Online

BST sangat cocok digunakan untuk sistem ranking. Setiap skor pemain disimpan sebagai node, dan dengan traversal descending (Right → Root → Left) kita bisa menampilkan ranking dari skor tertinggi ke terendah secara otomatis.

Struktur BST yang Terbentuk

Data skor: 500, 300, 700, 200, 400, 600, 800

         500          ← Root (skor pertama yang dimasukkan)
        /   \
      300   700
     / \    / \
   200 400 600 800

Descending traversal → 800 · 700 · 600 · 500 · 400 · 300 · 200

ranking_game.cpp C++

#include <iostream>
using namespace std;

struct Node {
    int score;
    Node* left;
    Node* right;
};

Node* createNode(int score) {
    Node* newNode = new Node();
    newNode->score = score;
    newNode->left  = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int score) {
    if (root == NULL) return createNode(score);
    if (score < root->score)
        root->left  = insert(root->left,  score);
    else if (score > root->score)
        root->right = insert(root->right, score);
    return root;
}

// Traversal descending: Right → Root → Left (terbesar ke terkecil)
void descending(Node* root) {
    if (root != NULL) {
        descending(root->right);
        cout << root->score << endl;
        descending(root->left);
    }
}

bool search(Node* root, int score) {
    if (root == NULL)           return false;
    if (root->score == score)   return true;
    if (score < root->score)
        return search(root->left,  score);
    else
        return search(root->right, score);
}

int main() {
    Node* root = NULL;

    root = insert(root, 500);
    root = insert(root, 300);
    root = insert(root, 700);
    root = insert(root, 200);
    root = insert(root, 400);
    root = insert(root, 600);
    root = insert(root, 800);

    cout << "=== Ranking Player ===" << endl;
    descending(root);

    int findScore = 600;
    if (search(root, findScore))
        cout << "Score ditemukan" << endl;
    else
        cout << "Score tidak ditemukan" << endl;

    return 0;
}

Output Program

Terminal Output

=== Ranking Player ===
800
700
600
500
400
300
200

Score ditemukan

Penjelasan Studi Kasus

insert()Setiap skor pemain baru langsung ditempatkan di posisi yang benar dalam BST, menjaga struktur tetap valid.
descending()Traversal dilakukan ke kanan lebih dulu (Right → Root → Left), sehingga nilai terbesar tampil pertama cocok untuk leaderboard.
search()Mengecek apakah suatu skor sudah ada dalam sistem. Jauh lebih cepat dari loop biasa karena tiap langkah membuang setengah kemungkinan.

⚠️ Catatan Penting — Bug Umum Di versi awal kode, baris insert(root, 500) tanpa assignment ke root akan menyebabkan tree tidak terbentuk karena root tetap NULL. Pastikan selalu menulis root = insert(root, nilai) khususnya pada saat insersi data pertama.

Kelebihan & Kekurangan BST

✅ Kelebihan

Pencarian data efisien O(log n) pada tree seimbang
Data tersimpan terurut secara otomatis
Insert dan delete relatif mudah diimplementasikan
Bisa diterapkan di banyak kasus nyata (ranking, database, dll)

⚠️ Kekurangan

Performa bisa menurun ke O(n) jika tree tidak seimbang (skewed)
Tidak ada mekanisme auto-balance seperti AVL atau Red-Black Tree
Butuh memori tambahan untuk dua pointer di setiap node

Kesimpulan

Binary Search Tree adalah fondasi penting dalam mempelajari struktur data. Lewat dua program di atas, kita telah memahami bagaimana proses insert, search, dan traversal bekerja serta melihat penerapannya secara langsung pada studi kasus sistem ranking game online.

Pemahaman BST yang kuat akan menjadi bekal untuk mempelajari struktur data pohon yang lebih canggih:

AVL Tree Red-Black Tree B-Tree Heap Trie

Search This Blog

Struktur Data (D) - Jonathan Evan