Binary Search Tree

Binary Search Tree 

      -        Pengertian

      Binary search tree (BST) adalah sebuah data struktur yang digunakan untuk mempercepat        searching, sorting, insertion dan deletion.

      BST juga dikenal sebagai binary tree yang sudah disortir

      Untuk sebuah node x dari BST :

è Value di subtree kiri lebih kecil dari value dalam x

è Value di subtree kanan lebih besar dari value dalam x

      -        Binary search tree operations

      BST mempunyai beberapa operasi :

è Search(x) : untuk mencari key x di dalam BST
Misalnya kita ingin mencari key x :

o   Pertama kita mulai dari root

o   Jika root adalah x maka proses selesai

o   Jika x lebih kecil dari key root maka dilakukan searching secara rekursif di subtree sebelah kiri, begitu pula sebaliknya

Berikut adalah source codenya :

struct node* search(struct node* root, int x)

{

    if (root == NULL || root->key == x)

       return root;

     

    if (root->key < x)

       return search(root->right, x);

  

    return search(root->left, x);

}

è Insert(x) : untuk memasukkan key baru x ke ke dalam BST
Operasi di BST dilakukan secara rekursif
Jika kita ingin memasukkan node baru yang valuenya x :

o   Pertama mulai dari root

o   Jika x kurang dari value node maka insert x di sub tree kiri, sebaliknya insert x di sub tree sebelah kanan

o   Ulangi sampai kita menemukan node yang kosong untuk x ( x selalu menjadi leaf baru)

Berikut adalah source code untuk insertion :

struct node* insert(struct node* node, int x)

{

      if (node == NULL) return newNode(x);

      xxx   

if (key < node->x)

        node->left  = insert(node->left, x);

      else if (key > node->x)

        node->right = insert(node->right, x);   

         

      return node;

}

è Remove(x) : untuk menghapus key x dari BST
Dalam operasi ini ada 3 macam kasus yang kita perlu perhatikan :

o   Jika key di dalam leaf, maka langsung hapus node tersebut

o   Jika key di dalam node yang mempunyai sebuah child, maka delete node tersebut dan connect child tersebut dengan parentnya

o   Jika key di dalam node yang mempunyai 2 children, cari child yang paling kiri, dan bandingkan dengan yang kanan

Berikut adalah source code untuk delete ( remove ) :

struct node* deleteNode(struct node* root, int x)

{

      if (root == NULL) return root;

     aa

      if (x < root->key)

        root->left = deleteNode(root->left, x);

      aa

      else if (x > root->key)

        root->right = deleteNode(root->right, x);

      else

      {

        if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

     aa

        struct node* temp = minValueNode(root->right);

      aa

        root->x = temp->x;

      aa

        root->right = deleteNode(root->right, temp->x);

        }

        return root;

}

Demikian penulisan saya tentang binary search tree, anda dapat mencoba langsung visualisasi dengan membuka link dibawah ini.

https://www.cs.usfca.edu/~galles/visualization/BST.html