Binary Search Tree

Konsep Dasar Binary search tree (BST) merupakan binary

tree dengan sifat berikut: Semua item pada left subtree bernilai kurang

dari root. Semua item pada right subtree bernilai lebih

atau sama dengan root. Setiap subtree merupakan BST.

2

3

Binary Search Tree (BST) adalah Binary Tree yang terurut, dengan ketentuan :• semua LEFT CHILD harus lebih kecil dari PARENT dan RIGHT CHILD.• semua RIGHT CHILD harus lebih besar dari PARENT dan LEFT

CHILD.

Target NODE : Node yang diinginkan/dicari

Keuntungan :Searching/Pencarian Target Node menjadi lebih efisien dan cepat.

Contoh :

4

Karakteristik

54

30 70

20 35 60

65

Binary Search Tree

OPERASI• Traversals• Searches• Insertion• Deletion

5

Semua operasi pd Binary Tree bisa diimplementasikan langsung pd BST,kecuali:

INSERT() UPDATE() DELETEKEY()

Untuk ketiga operasi tsb perlu dilakukan modifikasi terhadap posisi node sehingga BST tetap terurut.

6

Operasi

Langkah Pencarian lokasi utk node yg akan diinsert (baru) selalu

dimulai dr ROOT. Jika node baru < ROOT,maka insert pd LEFT

SUBTREE. Jika node baru > ROOT,maka insert pd RIGHT

SUBTREE.

Contoh :

7

Insert

54

70

60

Insert(54)

54 54

70

Insert(70) Insert(60)

Jika yang dihapus adalah LEAF maka tidak perlu dilakukan modifikasi terhadap lokasi.

Contoh : Delete(65)

8

Delete

54

30 70

20 35 60

65

Sesudah didelete

54

30 70

20 35 60

Sebelum didelete

Jika yang dihapus adalah NODE yang hanya memiliki 1 child, maka child tersebut langsung menggantikan posisi dari parentnya..

Contoh : Delete(60)

9

Delete(2)

54

30 70

20 35 60

65

Sesudah didelete

54

30 70

20 35 65

Sebelum didelete

Jika yang dihapus adalah NODE dengan 2 children (2 SUBTREE), maka node yang diambil untuk menggantikan posisi node yang dihapus adalah :

berasal dari LEFT SUBTREE, yang diambil adalah node yang paling kanan (yang mempunyai nilai terbesar).

atau dari RIGHT SUBTREE, yang diambil adalah node yang paling kiri (yang mempunyai nilai terkecil).

Contoh : Delete(54)

10

Delete (3)

54

30 70

20 35 60

65

Right SubTree

60

30 70

20 35 65

Sebelum dideleteLeft SubTree

35

30 70

20 60

65

Update terhadap suatu node akan mempengaruhi lokasi node tersebut setelah diupdate. Bila node tersebut setelah diupdate menimbulkan Tree yang bukan BST, maka harus diregenerate Tree tersebut.

Pendekatan yang lebih sederhana untuk menyelesaikan operasi UPDATE adalah dengan penggabungan antara operasi DELETE dengan INSERT.

Contoh :

UPDATE node 70 dengan node 80

11

Sebelum UPDATE

Update

54

30 70

20 35 60

65

Sesudah DELETE

54

30 65

20 35 65

Sesudah INSERT

54

30 65

20 35 65 80

Representasi

12

Data

Data

Data

struct node {Key_Type Key;Elemen_Type Data;struct node *Left;struct node *Right;struct node *Parent;

};

Key

Left Right

Parent

KeyLeft Right

ParentKeyLeft Right

KeyLeft Right

ParentNULL

NULL NULL

NULL

Data

NULL

Parent

Implementasi#include <stdio.h>#include <stdlib.h>

#define compLT(a,b) (a < b)#define compEQ(a,b) (a == b)

typedef enum { STATUS_OK,

STATUS_MEM_EXHAUSTED,

STATUS_DUPLICATE_KEY, STATUS_KEY_NOT_FOUND} statusEnum;

typedef int keyType;typedef int ElmDataType;

13

typedef struct nodeTag { struct nodeTag *left; struct nodeTag *right; struct nodeTag *parent; keyType key; ElmDataType ElmData;} nodeType;

nodeType *root = NULL;

Dikutip dari :http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_man.htm

Implementasi(2)statusEnum insert(keyType key, ElmDataType *ElmData) {

nodeType *x, *current, *parent;

/* find future parent */ current = root; parent = 0; while (current) { if (compEQ(key, current->key)) return STATUS_DUPLICATE_KEY; parent = current; current = compLT(key, current->key) ? current->left : current->right; }

/* setup new node */ if ((x = malloc (sizeof(*x))) == 0) { return

STATUS_MEM_EXHAUSTED; }

x->parent = parent; x->left = NULL; x->right = NULL; x->key = key; x->ElmData = *ElmData;

/* insert x in tree */ if(parent) if(compLT(x->key, parent->key)) parent->left = x; else parent-

>right = x; else root = x; return STATUS_OK; } 14

Traversals Preorder traversal

23 18 12 20 44 35 52 Postorder traversal

12 20 18 35 52 44 23 Inorder traversal

12 18 20 23 35 44 52

15

Inorder traversal pada BST menghasilkan nilai yang terurut dari kecil ke besar

Traversals Bagaimana aturan tranversal yang

menghasilkan urutan dari besar ke kecil?

52 44 35 23 20 18 12

16

17

Searches Beberapa jenis algoritma search:

Mencari node dengan nilai terkecil Mencari node dengan nilai terbesar Mencari node dengan nilai tertentu (BST

search)

18

Find the smallest node

19

Find the smallest node

20

Find the largest noderight subtree

not empty

right subtree not empty

right subtree empty return

21

Insertion BST insertion dilakukan pada leaf node

22

BST Insertion

23

Deletion Untuk menghapus sebuah node dari BST,

mula – mula lakukan search untuk mencari node yang akan dihapus.

Terdapat empat kasus pada penghapusan sebuah node di BST. Node yang dihapus : Tidak memiliki child Hanya punya right subtree. Hanya punya left subtree Punya dua subtree

24

Four cases when we delete a node

1. Node tidak memiliki child Hapus node

2. Node hanya memiliki right subtree. Hapus node Sambungkan right subtree ke parent node

yang akan dihapus.

3. Node hanya memiliki left subtree. Hapus node Sambungkan left subtree ke parent node

yang akan dihapus.

25

Four cases when we delete a node

4. Node memiliki dua subtree. Temukan node dengan nilai terbesar pada

left subtree node yang dihapus kemudian pindahkan node tersebut untuk menggantikan node yang dihapus or

Temukan node dengan nilai terkecil pada right subtree node yang dihapus kemudian pindahkan node tersebut untuk menggantikan node yang dihapus.

Selesai

26