Binary Search Tree

Regina

1901457321

Hari: Rabu, 30/03/2016

Kelas: CD01-CL

Lecturer: Rulyna ( D4689 ) dan Henry Chong ( D4460 )

Binary Search Tree ( BST )

Jika Binary Tree adalah sebuah Tree yang memiliki 2 anak, Binary Search Tree juga merupakan salah satu Tree yang juga memiliki 2 anak yaitu, left child dan right child. Dimana left child memiliki nilai yang lebih kecil dari parentnya dan right child memiliki nilai yang lebih besar dari parent. Sehinga BST memiliki ciri khas yaitu, peletakan isi dari nodenya yang terurut berdasarkan besarnya dari isinya tersebut. Isinya dapat berupa integer, karakter dan lain-lain.

Operasi-operasi BST:

• Find(x) : untuk mencari x
• Insert(x) : untuk menambah x baru
• Key(x): untuk menghapus x

1.       Searching / Find

Metode search pada BST efisien karena jalur yang dipilih tergolong spesifik. Sehingga, tidak perlu memeriksa semua elemen untuk mencari elemen tertentu.

Misalkan, key nya atau yg akan dicari adalah x.

Mulai dari Root sebuah tree.

Jika root tersebut NULL, maka return NULL.

Jika root adalah x, return karena x nya langsung ketemu.

Jika nilai x nya lebih kecil dari nilai sebuah root, maka akan mencari ke sub tree yang sebelah kiri atau left child.

Jika nilai x lebih besar dari nilai root, maka akan beralih dan mencari ke sub tree yang sebelah kanan atau right child.

Algoritma dari search pada BST :

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

}

2.       Insertion

Menambahkan nilai pada BST dilakukan dengan cara rekursif.

Misal, yang nilai yang akan dimasukkan adalah x.

Dimulai dari root.

Jika nilai x lebih besar dari nilai root maka, cek ke sebelah kanan.

Jika nilainya lebih kecil dari root cek ke sebelah kiri.

Maka, x akan menempati node yang kosong.

Sehingga, x akan selalu menjadi leaf yang baru.

Algoritma dari insertion:

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]

 

3.       Deletion
Ada 3 kasus yang perlu dipertimbangkan untuk menghapus data dalam BST:

·         Jika nilai yang ingin dihapus merupakan leaf, maka hapus node tersebut.

·         Jika node tersebut hanya memiliki 1 child, hapus node tersebut dan sambungkan child tersebut ke parentnya.

·         Jika nodenya ada 2, cari node dengan nilai yang paling besar dari sub-tree yang nilainya lebih kecil.

Algoritma dari deletion:

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