Modul 2 [Binary Search Tree]

Pengertian Binary Search Tree

Binary Search Tree adalah struktur data pohon biner berbasis node yang memiliki properti sebagai berikut :

• Subtree kiri dari sebuah node hanya berisi node dengan data/key yang lebih kecil dari kunci node.
• Subtree kanan dari sebuah node hanya berisi node dengan data/key lebih besar dari kunci node.
• Subtree kiri dan kanan masing-masing juga harus berupa binary search tree.

Sumber Gambar : https://courses.engr.illinois.edu/cs225/fa2022/assets/notes/bst/bsttreetraversal.png (dengan perubahan)

Implementasi Binary Search Tree

Properti

Node

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

Binary Search Tree

  struct BSTNode {
    BSTNode *_root;
    unsigned int _size;
};

// Fungsi-Fungsi...

Fungsi

is_empty

Untuk mengecek apakah BST kosong atau tidak

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

Find

Berikut adalah cara melakukan pencarian node pada implementasi ini

1. Mulai dari root
2. Jika value yang dicari lebih kecil dari node yang sedang dicek, pindah ke kiri
3. Jika value yang dicari lebih besar dari node yang sedang dicek, pindah ke kanan

Sumber gambar : https://courses.engr.illinois.edu/cs225/fa2022/assets/notes/bst/bstsearch.png

Primary Function

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

Utility Function

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

Insert

Untuk menambahkan node, pertama-tama harus ditentukan dulu posisi node yang akan ditambahkan. Setelah mendapat posisi yang sesuai, maka akan dilakukan pembuatan node baru yang berisi value yang ingin ditambahkan. Node baru yang akan ditambahkan akan selalu berada di posisi daun (leaf).

Primary Function

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

Utility Function

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

Remove

Terdapat 3 kondisi pada saat akan remove.

Kondisi 1 Node yang akan dihapus adalah node leaf (tanpa child)

Pada kondisi ini, node akan langsung dihapus

Sumber gambar : https://courses.engr.illinois.edu/cs225/fa2022/assets/notes/bst/removeleaf.png

Kondisi 2 Node yang akan dihapus mempunyai 1 child (kiri atau kanan)

Setelah node dihapus, maka child akan diposisikan pada node yang telah dihapus.

Sumber gambar : https://courses.engr.illinois.edu/cs225/fa2022/assets/notes/bst/onechildremove.png

Kondisi 3 Node yang akan dihapus mempunyai 2 child

Sebelum node dihapus, maka akan dilakukan pencarian node terkecil dari subTree kanan child, kemudian akan dilakukan pertukaran. Setelah itu, dilakukan penghapusan node.

Primary Function

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

Utility Function

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

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

Skewed Tree

Jika urutan insertion tree yang dilakukan adalah 5,4,3,2,1 maka bentuk tree akan seperti gambar di bawah, dan ini dinamakan Skewed Tree

Referensi

• https://www.geeksforgeeks.org/binary-search-tree-data-structure/
• https://courses.engr.illinois.edu/cs225/fa2022/resources/bst/