BINARY TREE SEARCH
Pisco Yudha A, Regie Nugraha, Krisna Joko Pramudyo
Program Studi Sarjana Teknik Informatika
Fakultas Ilmu Komputer, Universitas Pembangunan Nasional “Veteran” Jakarta
yudha@programmer.net, regi_gokil@yahoo.com, krisna.08it@gmail.com
Introduction
In computer science, a binary search tree (BST) is a node-based binary tree data structure which has the following properties:[1]
* The left subtree of a node contains only nodes with keys less than the node's key.
* The right subtree of a node contains only nodes with keys greater than the node's key.
* Both the left and right subtrees must also be binary search trees.
From the above properties it naturally follows that:
* Each node (item in the tree) has a distinct key.
Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.
Pembahasan
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 :

n Struktur Binary Tree banyak digunakan untuk membantu memecahkan persoalan suatu algoritma, contohnya untuk memecahkan masalah organisasi file direct.
n Penggunaan Binary Tree sebagai suatu struktur file yang disebut Binary Search Tree (BST).
n Aturan Insert ke dalam File BST
<>Ã Masuk Ke Kiri
> Node à Masuk Ke Kanan
Operasi Binary Search Tree
Ada 3 Operasi pada Binary Search Tree, yaitu :
– INSERT()
– UPDATE()
– DELETEKEY()
Untuk ketiga operasi tsb perlu dilakukan modifikasi terhadap posisi node sehingga BST tetap terurut.
1 . Insert
Langkah
– Pencarian lokasi utk node yg akan diinsert (baru) selalu dimulai dr ROOT.
– Jika node baru <>
– Jika node baru > ROOT,maka insert pd RIGHT SUBTREE.
–
Contoh Insert ke File Binary Search Tree
Key : 30, 62, 69, 41, 25, 39, 14, 93
Hasilnya :

2. Delete
Jika yang dihapus adalah LEAF maka tidak perlu dilakukan modifikasi terhadap lokasi.
Contoh : Delete(65)

Jika yang dihapus adalah NODE yang hanya memiliki 1 child, maka child tersebut langsung menggantikan posisi dari parentnya..
Contoh : Delete(60)

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)





3 . Update
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
![]()



Ketidakefisienan Binary Search Tree
Ini adalah contoh dari ketidak efisienan dari operasi algoritma Binary Search Tree
Key : 14, 25, 30, 39, 41, 62, 69, 93

AVL TREE (Adelson, Velskii, Landis)
BST Yang “Seimbang”
Balance Factor
B ---> level 1
A D ---> level 2
C F ---> level 3
E ---> level 4
n Subtree : Tree yang terbentuk disebelah kanan atau kiri dari suatu node. (Catatan : Node tsb disebut root subtree)
n Tinggi subtree : Level node terbawah dari subtree dikurang level root subtree tsb
n Balance Factor : Tinggi subtree kanan dikurang tinggi dari subtree kiri dari suatu node
AVL Tree
n Binary Search Tree yang memiliki aturan setiap node selalu memiliki balance factor 0, +1 atau -1
n Maka : setiap kali key baru diinsert ke dalam file, setiap node dilihat balance factornya
n Apabila ada node yang balance factornya tidak 0, +1 atau -1 (tidak imbang) maka struktur file dilakukan transformasi :
n Pemutaran dan atau penggeseran
n
n Kemungkinan tidak imbang hanya 2 dan diselesaikan dengan solusi :
n Rotasi Tunggal dan Rotasi Ganda
Kemungkinan Transformasi 1
(Rotasi Tunggal)


ROTASI KE KIRI




Program C++ Binary Search Tree
#include
#include
#include
//struct dari binary tree yang berisi subtree kanan dan subtree kiri//
struct tree
{ int data;
struct tree *kanan,*kiri;
};
//Proses insert data ke simpul/node dengan typedef struct tree simpul//
typedef struct tree simpul;
simpul *t=NULL;
simpul* insert(int x,simpul *t)
{
if(t==NULL)
{
t=(simpul*)malloc(sizeof(simpul));
t->data=x;
t->kiri=NULL;
t->kanan=NULL;
}
else
if(x
t->kiri=insert(x,t->kiri);
else
if(x>t->data)
t->kanan=insert(x,t->kanan);
return t;
}
//Cari data yang diminta pada binary tree//
void cari(simpul *t,int x)
{ if(t==NULL)
printf("\nElement Ketemu");
else
{ if(t->data==x)
printf("\nElement Tidak Ketemu");
else
if(x
cari(t->kiri,x);
else
cari(t->kanan,x);
}}
//Cari data maximum dari binary tree//
void cari_maximum(simpul *t)
{ if(t!=NULL)
{ if(t->kanan==NULL)
printf("\nMaximum element=%d",t->data);
else
cari_maximum(t->kanan);
}}
//Cari data minimum dari binary tree//
void cari_minimum(simpul *t)
{ if(t!=NULL)
{ if(t->kiri==NULL)
printf("\nMinimum element=%d",t->data);
else
cari_minimum(t->kiri);
}}
//Menampilkan seluruh data simpul binary tree//
void tampil(simpul *t)
{ if(t!=NULL){
tampil(t->kiri);
printf(" %d",t->data);
tampil(t->kanan);
}}
//Proses utama//
void main()
{
int data,ch,s;
char c;
while(1)
{
void clear_screen();
printf("\a\n*INSERT (Tekan 1)");
printf("\n*SEARCH (Tekan 2)");
printf("\n*CARI DATA MINIMUM (Tekan 3)");
printf("\n*CARI DATA MAXIMUM (Tekan 4)");
printf("\n*TAMPILKAN DATA (Tekan 5)");
printf("\n*KELUAR (Tekan 6)");
printf("\n\nMasukan Pilihan:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nMasukan data:\a");
scanf("%d",&data);
t=insert(data,t);
break;
case 2: printf("\nMasukan Element yang akan dicari:");
scanf("%d",&s);
cari(t,s);
break;
case 3: cari_minimum(t);
break;
case 4: cari_maximum(t);
break;
case 5: printf("\nTampilan Inorder:\n");
tampil(t);
break;
case 6: exit(0);
break;
default:printf("\a\a\a\n\nPilih yang benar ya!");
}
getch();
}

