Download - Algoritma dan Struktur Data
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
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
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)
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.