Summary Binary Search Tree

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

•          Subtree kiri dari sebuah node hanya berisi node dengan kunci lebih rendah dari kunci node.
•          Subtree kanan sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
•          Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner.

Cara mengubah array menjadi binary search tree :

#include<stdio.h>

#include<stdlib.h>

 

struct TNode

{

    int data;

    struct TNode* left;

    struct TNode* right;

};

 

struct TNode* newNode(int data);

struct TNode* sortedArrayToBST(int arr[], int start, int end)

{

    /* Base Case */

    if (start > end)

      return NULL;

 

    int mid = (start + end)/2;

    struct TNode *root = newNode(arr[mid]);

 

    root->left =  sortedArrayToBST(arr, start, mid-1);

    root->right = sortedArrayToBST(arr, mid+1, end);

 

    return root;

}

struct TNode* newNode(int data)

{

    struct TNode* node = (struct TNode*)

                         malloc(sizeof(struct TNode));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

 

    return node;

}

 

void preOrder(struct TNode* node)

{

    if (node == NULL)

        return;

    printf("%d ", node->data);

    preOrder(node->left);

    preOrder(node->right);

}

int main()

{

    int arr[] = {1, 2, 3, 4, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

 

    struct TNode *root = sortedArrayToBST(arr, 0, n-1);

    printf("PreOrder Traversal of constructed BST ");

    preOrder(root);

 

    return 0;

}

Operasi yang dapat dilakukan dalam binary serach tree :

• -         Insert  => memasukkan data kedalam binary search tree
• -          Delete => menghapus node data dari binary tree
• -          Search => mencari data tersebut
• -          Print  => memperlihatkan data yang sudah disimpan

Apakah kegunaan binary search tree ?

Untuk mempermudah mengakses dan menyimpan data. Contohnya :

Ok, langsung saja kecontohnya. Misal kita memiliki urutan angka yang dimasukkan kedalam data dengan urutan sebagai berikut : 4 2 7 1 3 . Bagaimana binary tree nya akan terbentuk ? Binary tree nya akan berbentuk seperti berikut :

       4

       / \

      2   7

     / \

    1   3

Aturan saat “insert” kedalam binary tree ini adalah dengan membandingkan data yang akan dimasukkan dengan kondisi root saat itu. Ok, mari kita telaah ! angka pertama yang akan menjadi “root” adalah 4, maka angka tersebut akan menjadi paling atas. Lalu berikut nya 2, nah disini kita akan membandingkan 2 dengan 4, 2 lebih kecil dibanding 4, maka dia akan diletakkan dikir. Lalu 7, karena 7 lebih besar dari 4, maka 7 diletakkan disebelah kanan. Lalu 1, 1 lebih kecil dibandingkan 4 maka akan masuk ke sebelah kiri, namun karena sebelah kiri sudah memiliki “root” yaitu 2, maka 1 akan dibandingkan kembali dengan 2, karena 1 lebih kecil dibandingkan dengan 2, maka 1 diletakkan disebelah kiri dari 2. Begitu juga berlaku dengan 3.

Dari, penjelasan diatas, dapat disimpukan bahwa binary tree saat “insert” data mengurutkan datanya terlebih dahulu. Lalu apa hubungannya dengan pertanyaan “Apa kegunaan binary tree dalam pemrograman ? ”. Kita ambil kasus simple saja, kita diminta untuk menangani deretan angka yang tidak berurutan, lalu diminta untuk menentukan manakah angka yang terbesar, dengan mudah kita akan langsung mengambil data yang paling kanan sampai tidak memiliki cabang lagi. Kenapa bisa seperti itu ? karena otomatis angka yang memiliki posisi paling kanan dan sudah tidak memiliki cabang dialah angka yang paling besar.

refrensi :

https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/

https://www.geeksforgeeks.org/binary-search-tree-data-structure/#construction