BINARY TREE SEARCH


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(xdata)

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(xdata)

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

}

Read Users' Comments (0)