Pertemuan 5 - Binary Search Tree

Binary Search Tree

OPERASI BINARY SEARCH TREE

Binary Search Tree memiliki operasi dasar berikut:

o Find (x): menemukan kunci x di Binary Search Tree

o Insert (x): memasukkan kunci baru x ke Binary Search Tree

o Remove (x): menghapus kunci x dari Binary Search Tree

OPERASI: SEARCH

o Karena properti dari Binary Search Tree, mencari dari Binary Search Tree sangat mudah.

o Kunci yang ingin kita cari adalah X. Kita mulai pada root.

o Jika root berisi X, maka pencarian akan berakhir dengan sukses.

o Jika X lebih kecil dari kunci root, maka mencari secara rekursif pada sub tree sebelah kiri, jika tidak, mencari secara rekursif di sub tree sebelah kanan.

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

}

OPERASI: INSERTION

o Memasukkan ke Binary Seacrh Tree dilakukan secara rekursif.

o kunci simpul baru menjadi X.

ü Kita mulai dari root.

ü Jika X lebih kecil dari kunci node, maka masukkan X ke dalam sub tree sebelah kiri, jika tidak, masukkan X ke dalam sub tree kanan.
üUlangi hingga menemukan simpul kosong untuk menempatkan X (X akan selalu berupa leaf baru)

Algorithm:

Step 1: 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]

Step 2: End

Example:

Masukan Kunci Baru (35)

OPERASI: DELETION

Ada 3 cases yang harus diperhatikan:

o Jika kuncinya adalah leaf, hapus saja nodenya

o Jika kuncinya adalah node yang hanya mempunyai satu anak, hapus nodenya dan konek anaknya kepada orangtuanya.

o Jika kuncinya adalah node mempunyai dua anak, temukan anak yang paling benar yang mempunyai sub tree disebelah kiri, gantikan kuncinya dengan kunci P’s dan hapus P secara recursive.

Step 1: 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