Pertemuan 6-Binary Search Tree -Benedick Asdyo-2101631090

Tree adalah graf yang tidak ada loop.
Binary tree adalah tree yang anak setiap node maksimal 2.
Binary search tree adalah Binary Tree yang memiliki aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node atau sebaliknya. Penggunaan binary search tree atau BST ini adalah untuk mempercepat atau memperkecil waktu untuk mencari sebuah data.

Operasi - operasi dalam BST atau Binary Search Tree ini adalah: Search, Insertion, dan Deletion.
seperti namanya search merupakan operasi untuk memasukan data ke dalam Binary Search tree, Search adala pencarian data dalam Binary Search Tree dan deletion adalah penghapusan data dalam Binary search tree. 

Search

Algoritma dalam mencari sebuah data dalam Binary Search Tree:
Cek data yang ingin di cari dari lvl tertinggi jika yang dicari lebih kecil dari node yang kira tunjuk geser ke bagian kiri tree, jika lebih besar kita cari di node paling kanan , begitu seterusnya hingga datanya ketemu

struct node* search (struct node *curr, int X) {

  if ( curr == NULL ) return NULL;

  // X is found

  if ( X == curr->data ) return curr;

  // X is located in left sub tree

  if ( X  < curr->data ) return find(curr->left, X);

•

  // X is located in right sub tree

  return find(curr->right, X);

 

Insertion

Algoritma dalam memasukan data kedalam Binary Search Tree adalah sama seperti insertion, namum setiap memasukan data kita harus seperti men search data dari root treenya lalu menaruh data itu jika child dari node yang dikunjungi kurang dari dua ,untuk penempatan mengikuti aturan biasa dikiri jika lebih kecil dari parent atau dikanan jika lebih besar
psuedo code:

IF TREE = NULL, then 

  Allocate memory for TREE

            SET TREE->DATA = VAL

      SET TREE->LEFT = TREE ->RIGHT = NULL

        ELSE

      IF VAL < TREE->DATA

       Insert(TREE->LEFT, VAL)

      ELSE

  Insert(TREE->RIGHT, VAL)

           [END OF IF]

       [END OF IF]

Step 2: End

contoh gambar :

Deletion
dalam penghapusan ada beberapa kasus yang perlu diperhatikan antara lain :
- Jika data yang ingin di hapus ada di leaf maka langsung saja hapus data tersebut
-Jika data yang ingin di hapus memiliki satu child maka hapus node tersebut dan sambungkan anaknya ke parent yang tadi kita hapus
-Jika data yang ingin di hapus memiliki 2 child maka cari child paling kiri dari node tersebut dan ganti node yang ingin di hapus dengan left most child lalu hapus left most child pada tempat asalnya


psuedo-code:

: IF TREE = NULL, then 

       Write “VAL not found in the tree”

        ELSE IF VAL < TREE->DATA

         Delete(TREE->LEFT, VAL)

        ELSE IF VAL > TREE->DATA

       Delete(TREE->RIGHT, VAL)

        ELSE IF TREE->LEFT AND TREE->RIGHT

       SET TEMP = findLargestNode(TREE->LEFT)

       SET TREE->DATA = TEMP->DATA

       Delete(TREE->LEFT, TEMP->DATA

 ELSE

  SET TEMP = TREE

  IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL

  SET TREE = NULL

  ELSE IF TREE->LEFT != NULL

  SET TREE = TREE->LEFT

  ELSE

  SET TREE = TREE->RIGHT

  FREE TEMP  





Nama : Benedick Asdyo
NIM   : 2101631090