BST, penjelasan fungsi dan kegunaan

 Nama : Fakhrian Elanta

NRP : 5025251019

Kelas : D

Full Code : 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

/* Node structure */

struct BSTNode {
    BSTNode *left, *right;
    int key;
};

/* uniqueBST */

struct BST {
    // Member
    BSTNode *_root;
    unsigned int _size;

    // Function
    void init() {
        _root = NULL;
        _size = 0u;
    }

    bool isEmpty() {
        return _root == NULL;
    }

    bool find(int value) {
        BSTNode *temp = __search(_root, value);
        if (!temp)
            return false;
       
        if (temp->key == value)
            return true;
        else
            return false;
    }

    void insert(int value) {
        if (!find(value)) {
            _root = __insert(_root, value);
            _size++;
        }
    }

    void remove(int value) {
        if (find(value)) {
            _root = __remove(_root, value);
            _size++;
        }
    }

    void traverseInorder() {
        __inorder(_root);
    }

    void traversePreorder() {
        __preorder(_root);
    }

    void traversePostorder() {
        __postorder(_root);
    }

    int maxnode(){
        if (isEmpty()) {
            return -1;
        }
       
       
        BSTNode* maxNode = __findMaxNode(_root);
        return maxNode->key;
    }

private:
    // Utility Function
    BSTNode* __createNode(int value) {
        BSTNode *newNode = (BSTNode*) malloc(sizeof(BSTNode));
        newNode->key = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
   
    BSTNode* __search(BSTNode *root, int value) {
        while (root != NULL) {
            if (value < root->key)
                root = root->left;
            else if (value > root->key)
                root = root->right;
            else
                return root;
        }
        return root;
    }

    BSTNode* __insert(BSTNode *root, int value) {
        if (root == NULL)
            return __createNode(value);
       
        if (value < root->key)
            root->left = __insert(root->left, value);
        else if (value > root->key)
            root->right = __insert(root->right, value);
       
        return root;
    }

    BSTNode* __findMinNode(BSTNode *node) {
        BSTNode *currNode = node;
        while (currNode && currNode->left != NULL)
            currNode = currNode->left;
       
        return currNode;
    }

    BSTNode* __findMaxNode(BSTNode *node) {
        BSTNode *currNode = node;
        while (currNode && currNode->right != NULL)
            currNode = currNode->right;
       
        return currNode;
    }

    BSTNode* __remove(BSTNode *root, int value) {
        if (root == NULL) return NULL;

        if (value > root->key)
            root->right = __remove(root->right, value);
        else if (value < root->key)
            root->left = __remove(root->left, value);
        else {

            if (root->left == NULL) {
                BSTNode *rightChild = root->right;
                free(root);
                return rightChild;
            }
            else if (root->right == NULL) {
                BSTNode *leftChild = root->left;
                free(root);
                return leftChild;
            }

            BSTNode *temp = __findMinNode(root->right);
            root->key     = temp->key;
            root->right   = __remove(root->right, temp->key);
        }
        return root;
    }

    void __inorder(BSTNode *root) {
        if (root) {
            __inorder(root->left);
            printf("%d ", root->key);
            __inorder(root->right);
        }
    }

    void __postorder(BSTNode *root) {
        if (root) {
            __postorder(root->left);
            __postorder(root->right);
            printf("%d ", root->key);
        }
    }

    void __preorder(BSTNode *root) {
        if (root) {
            printf("%d ", root->key);
            __preorder(root->left);
            __preorder(root->right);
        }
    }
};

int main(int argc, char const *argv[])
{
    BST set;
    set.init();

    int N;
    cout<<"Masukkan banyaknya skor yang ingin dimasukkan: ";
    cin>>N;
    while(N--){
        cout<<"Masukkan skor: ";
        int x;
        cin>>x;
        set.insert(x);
    }

    cout<<"Skor tertinggi adalah: ";
    int bigest = set.maxnode();
    cout<<bigest<<endl;
   
}

1. Fungsi Utama / Publik (Interface BST)

Fungsi-fungsi ini adalah interface yang dipanggil oleh pengguna dari luar struktur data (seperti di dalam fungsi main).

  • void init()

    Inisialisasi objek BST saat pertama kali dibuat. Fungsi ini memastikan pointer akar (_root) bernilai NULL dan ukuran pohon (_size) dimulai dari 0.

  • bool isEmpty()

    Memeriksa apakah pohon kosong atau tidak. Mengembalikan nilai true jika _root masih NULL, dan false jika sudah terisi data.

  • bool find(int value)

    Mencari keberadaan suatu nilai di dalam pohon. Fungsi ini memanggil utilitas privat __search(). Jika nilai ditemukan, ia mengembalikan true; jika tidak, mengembalikan false.

  • void insert(int value)

    Memasukkan nilai baru ke dalam pohon. Fungsi ini memeriksa terlebih dahulu menggunakan find(value) agar tidak ada nilai duplikat (karena ini dirancang sebagai unique BST). Jika belum ada, data dimasukkan dan ukuran pohon (_size) ditambah.

  • void remove(int value)

    Menghapus nilai dari pohon jika nilai tersebut ditemukan.

  • void traverseInorder(), traversePreorder(), traversePostorder()

    Fungsi pembuka untuk mencetak/menelusuri semua elemen pohon dengan urutan tertentu. Fungsi-fungsi ini bertindak sebagai jembatan untuk memanggil fungsi utilitas rekursifnya masing-masing dengan menyerahkan _root sebagai titik mulainya.

  • int maxnode()

    Mencari dan mengembalikan skor/nilai tertinggi di dalam pohon. Fungsi ini memanfaatkan sifat BST di mana nilai terbesar selalu berada di ujung paling kanan pohon. Jika pohon kosong, fungsi mengembalikan -1.

2. Fungsi Utilitas Privat (Helper Functions)

Fungsi-fungsi ini diawali dengan dua garis bawah (__) dan berada di bawah akses private. Fungsinya adalah menyelesaikan operasi-operasi kompleks di balik layar, biasanya menggunakan teknik rekursif atau perulangan (loop).

Manajemen Node & Pencarian

  • BSTNode* __createNode(int value)

    Mengalokasikan memori baru di heap menggunakan malloc untuk membuat sebuah node baru, mengisi datanya dengan value, serta mengatur pointer anak kiri (left) dan kanan (right) menjadi NULL.

  • BSTNode* __search(BSTNode *root, int value)

    Melakukan pencarian nilai menggunakan perulangan (while). Jika nilai yang dicari lebih kecil dari node saat ini, pencarian bergeser ke kiri. Jika lebih besar, bergeser ke kanan. Jika sama, node tersebut langsung dikembalikan.

  • BSTNode* __insert(BSTNode *root, int value)

    Menempatkan node baru secara rekursif. Fungsi ini menelusuri pohon ke kiri atau ke kanan sesuai aturan BST hingga menemukan posisi kosong (NULL), lalu membuat node baru di sana menggunakan __createNode.

Penghapusan & Optimasi Pencarian Nilai Ekstrem

  • BSTNode* __findMinNode(BSTNode *node)

    Mencari node dengan nilai terkecil mulai dari titik node yang diberikan. Caranya dengan terus berjalan ke cabang paling kiri (currNode->left) hingga mentok.

  • BSTNode* __findMaxNode(BSTNode *node)

    Mencari node dengan nilai terbesar mulai dari titik node yang diberikan. Caranya dengan terus berjalan ke cabang paling kanan (currNode->right) hingga mentok. Fungsi inilah yang mendasari logika pencarian skor tertinggi pada maxnode().

  • BSTNode* __remove(BSTNode *root, int value)

    Fungsi rekursif untuk menghapus node. Fungsi ini menangani 3 kondisi penghapusan:

    1. Node yang dihapus tidak punya anak (langsung dihapus).

    2. Node hanya punya 1 anak (anaknya naik menggantikan posisi node tersebut).

    3. Node punya 2 anak (mencari nilai terkecil di cabang kanan menggunakan __findMinNode untuk menggantikan node yang dihapus, lalu menghapus node duplikatnya).

Penelusuran Pohon (Tree Traversal)

  • void __inorder(BSTNode *root)

    Menelusuri pohon dengan urutan: Kiri $\rightarrow$ Akar $\rightarrow$ Kanan. Pada BST, cara ini otomatis akan mencetak data secara berurutan dari yang terkecil hingga terbesar.

  • void __preorder(BSTNode *root)

    Menelusuri pohon dengan urutan: Akar $\rightarrow$ Kiri $\rightarrow$ Kanan. Biasanya digunakan untuk menduplikasi atau mengkloning struktur pohon.

  • void __postorder(BSTNode *root)

    Menelusuri pohon dengan urutan: Kiri $\rightarrow$ Kanan $\rightarrow$ Akar. Biasanya digunakan saat proses penghapusan seluruh pohon dari memori (destruksi).

3. Fungsi Utama Program

  • int main()

    Tempat program pertama kali dieksekusi. Fungsi ini membuat objek pohon bernama set, meminta input dari pengguna mengenai berapa banyak skor yang ingin dimasukkan, melakukan perulangan untuk memasukkan skor-skor tersebut ke dalam BST menggunakan fungsi insert(), dan terakhir menampilkan skor tertinggi menggunakan fungsi maxnode().

Komentar

Posting Komentar

Postingan populer dari blog ini

overviewc++

Gambar
 Review C++ dalam pemograman      C++ merupakan bahasa pemograman yang dikenal akan kecepatannya serta low level memory management.     Penggunaan C++ masih relevan hingga saat ini, biasanya C++ banyak digunakan untuk membuat game engine, Operating System, Software Aplikasi, dan masih banyak lagi.     Untuk menggunakan C++ sendiri kita perlu memiliki Source Code, dimana kita menulis program yang akan dijalankan menggunakan bahasa C++, penulisannya sendiri bisa menggunakan Text Editor atau IDE lain yang dapat membuat programnya, seperti Code Block, Visual Studio Code dan sebagainya, selanjutnya kita memerlukan Compiler untuk membuat file executable.     Berikut merupakan beberapa pemograman dasar sebagai pengenalan C++. Menggunakan cout untuk print suatu kalimat : source code :  https://github.com/ealnt/Strukdat_Elan/blob/pertemuan2/cout.cpp Menggunakan puts untuk print suatu kalimat : source code :  https://github.com/ealnt/Str...
Baca selengkapnya

Stack

Gambar
  Pengertian Stack Stack adalah struktur data linear yang bekerja dengan prinsip LIFO (Last In, First Out) . Artinya, data yang terakhir dimasukkan ke dalam tumpukan akan menjadi data yang pertama kali dikeluarkan. Bayangkan seperti tumpukan piring atau tumpukan buku; Anda hanya bisa menambah atau mengambil elemen dari bagian paling atas. Operasi Dasar Stack Dalam mengelola tumpukan, terdapat beberapa operasi utama yang digunakan: Push : Operasi untuk menambahkan atau memasukkan elemen baru ke posisi paling atas tumpukan. Pop : Operasi untuk menghapus atau mengeluarkan elemen yang berada di posisi paling atas. Setelah operasi ini, elemen di bawahnya akan menjadi posisi teratas yang baru. Top : Digunakan untuk melihat nilai dari elemen yang berada di posisi paling atas tanpa menghapus elemen tersebut dari tumpukan. isEmpty : Digunakan untuk mengecek apakah tumpukan sedang kosong atau tidak. Ini penting dilakukan sebelum melakukan operasi Pop agar tidak terjadi error. isFull : Digun...
Baca selengkapnya