Struktur Data - Implementasi BST

Nama    : Aga Nafta Filadelfiano

NRP      : 5025251055
Kelas     : Struktur Data (D) 

Implementasi BST

Source Code: GitHub

1. Implementasi BST pada C++

Deskripsi: 

Program ini merupakan implementasi dasar struktur data Binary Search Tree (BST) menggunakan bahasa C++. Program berfungsi untuk menyisipkan sekumpulan data ke dalam pohon secara terurut sesuai aturan BST, melakukan penelusuran (traversal) secara inorder untuk menghasilkan data yang terurut menaik, serta melakukan pencarian (search) untuk memverifikasi apakah suatu data spesifik ada di dalam tree tersebut.

Syntax Program:

Output:

Penjelasan Code:

struct Node {

    int data;

    Node* left;

    Node* right;

};

Mendefinisikan struktur node BST. Setiap node menyimpan nilai integer data, pointer left ke child kiri, dan pointer right ke child kanan.

Node* createNode(int value) {

    Node* newNode = new Node();

    newNode->data = value;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

Fungsi untuk mengalokasikan memori baru dan membuat node dengan nilai value. Pointer left dan right diinisialisasi ke NULL karena node baru belum memiliki child, lalu node tersebut direturn.

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;

}

Fungsi rekursif untuk menyisipkan nilai baru ke dalam BST. Jika root kosong, node baru langsung dibuat. Jika nilai lebih kecil dari node saat ini, diteruskan ke subtree kiri, jika lebih besar, ke subtree kanan. Jika ada nilai duplikat maka tidak akan ditambahkan sebagai node baru.

void inorder(Node* root) {

    if (root != NULL) {

        inorder(root->left);

        cout << root->data << " ";

        inorder(root->right);

    }

}

Fungsi traversal inorder (kiri > root > kanan) secara rekursif. Karena sifat BST, traversal ini menghasilkan urutan data dari nilai terkecil hingga terbesar secara otomatis.

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);

}

Fungsi rekursif untuk mencari nilai key dalam BST. Memanfaatkan BST untuk menentukan arah pencarian, yaitu ke kiri jika key lebih kecil, ke kanan jika lebih besar.

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;

}

Fungsi utama yang mengisi BST dengan insert tujuh nilai, lalu menampilkan seluruh isi tree secara terurut menggunakan inorder, dan mencari nilai 60 menggunakan search.

2. Studi Kasus Game Online pengimplementasian BST

Deskripsi: 

Program ini adalah bentuk implementasi studi kasus game online yang menyimpan skor para pemain menggunakan struktur Binary Search Tree (BST). Fungsi utama program ini adalah untuk memasukkan skor pemain secara efisien, menampilkan ranking pemain secara terurut menurun dari skor terbesar, serta mempermudah pencarian terhadap skor pemain tertentu di dalam sistem.

Syntax Program:

Output:

Penjelasan code:

struct Node {

    int score;

    Node* left;

    Node* right;

};

Mendefinisikan struktur node untuk menyimpan data skor pemain. Pointer left dan right menghubungkan node ke skor yang lebih kecil dan lebih besar.

Node* createNode(int score) {

    Node* newNode = new Node();

    newNode->score = score;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

Fungsi untuk membuat node baru dengan nilai score yang diberikan, mengalokasikan memori secara dinamis dan menginisialisasi kedua pointer ke NULL.

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;

}

Fungsi rekursif untuk menyisipkan skor baru ke posisi yang sesuai dalam BST berdasarkan perbandingan nilai.

void descending(Node* root) {

    if (root != NULL) {

        descending(root->right);

        cout << root->score << endl;

        descending(root->left);

    }

}

Fungsi traversal reverse inorder (kanan > root > kiri) untuk menampilkan skor dari nilai tertinggi ke terendah. Digunakan sebagai tampilan ranking karena skor terbesar berada di subtree kanan BST.

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);

}

Fungsi rekursif untuk mencari apakah skor tertentu sudah terdaftar dalam sistem. 

int main() {

    Node* root = NULL;

    root = insert(root, 500);

    insert(root, 300);

    insert(root, 700);

    insert(root, 200);

    insert(root, 400);

    insert(root, 600);

    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;

}

Fungsi utama yang mengisi BST dengan tujuh data skor pemain, menampilkan ranking dari skor tertinggi ke terendah menggunakan descending, dan mengecek keberadaan skor 600 menggunakan search.