Struktur Data Queue

Queue

queue menggunakan system FIFO (first in first out)

pada queue data yang di dequeue adalah data yang paling awal ditambahkan

kita bisa menemukan  system Queue di loket pembelian ticket

operasi umum  yang digunakan di queue yaitu Create, Enqueue, Dequeue, Head, Tail

bahasa pemrograman untuk queue

Create

isi.Size = New Point(kolom, lebar)          misalnya     ---- >       isi.size = New Point(panjang*15,18)

15 dan 18 itu hanya lebar dan panjang yg diinginkan aja..

Enqueue

isi.Text = isi.Text + textBox2.Text

ini artinya kita menyanbungkan textbox isi dengan textbox2, sehinnga nomor yang telah dimasukan sebelumnya bisa digabungkan dengan nomor yang baru dimasukan.

Dequeue

 isi.Text = Microsoft.VisualBasic.Right(isi.Text, Len(isi.Text) - 2)

artinya kita mengeluarkan angka dari arah kanan karena -2 itu

Head

head = Microsoft.VisualBasic.Left(chr, 1)

artinya angka yang ada pada bagian paling kiri akan menjadi Head.

Tail

Tail = Microsoft.VisualBasic.Right(chr, 1)

angka pada bagian paling kanan akan menjadi Tail

berikut ini contoh Queue :

Struktur Data STACK

STACK

stack menggunakan system LIFO (last In First Out)

contoh stack

misalnya kita menumpuk buku setingi tingginya.. dan ingin mengambil buku yang ada pada bagian bawah.. tentu saja tidak kita tarik yang di bawah secara langsung, karena jika dilakukan itu maka semua buku akan tumbang dan jadi berantakan. Sehingga kita harus mengeluarkan dulu yang paling atas sampai ke paling bawah.

perintah yang ada pada Stack

Create, Push, Pop , Head , Tail

Create

isi.Size = New Point(kolom, lebar)         

kolom dan lebar diisi sesuai dengan keinginan kita

Push

isi.Text = isi.Text + textBox2.Text

menyisipkan atau memasukan data ke dalam stack

Pop

isi.Text = Microsoft.VisualBasic.Left(isi.Text, Len(isi.Text) - 1)

nah kalo yang ini angka akan dikurangi dari bagian kiri karena kita menggunakan Left pada query itu dan stack sendiri juga di pop dari bagian kiri ..

Head

head = Microsoft.VisualBasic.Left(chr, 1)

artinya angka yang ada pada bagian paling kiri akan menjadi Head.

Tail

Tail = Microsoft.VisualBasic.Right(chr, 1)

angka pada bagian paling kanan akan menjadi Tail

Contoh pada Stack :

Struktur Data Tree

Tree Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

• Prodecessor : node yang berada diatas node tertentu.

• Successor : node yang berada di bawah node tertentu.

• Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

• Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

• Parent : predecssor satu level di atas suatu node.

• Child : successor satu level di bawah suatu node.

• Sibling : node-node yang memiliki parent yang sama dengan suatu node.

• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

• Size : banyaknya node dalam suatu tree.

• Height : banyaknya tingkatan/level dalam suatu tree.

• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

• Leaf : node-node dalam tree yang tak memiliki seccessor.

• Degree : banyaknya child yang dimiliki suatu node.

  Beberapa jenis Tree yang memiliki sifat khusus :

1) Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.


 
Jenis-jenis Binary Tree :

a) Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

 b) Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child. 

c) Skewed Binary Tree

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Implementasi Binary TreeBinary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :Type Tree = ^node;Node = recordIsi : TipeData;Left,Right : Tree;end;
Contoh ilustrasi Tree yang disusun dengan double linked list :

 (Ket: LC=Left Child; RC=Right Child)

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

v Empty : Function untuk memeriksa apakah binary tree masih kosong.

v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.
Langkah-Langkahnya Traverse :Ø PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Ø InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
Ø PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :

  2) Binary search 

Tree adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.

 Contoh binary search tree umum :

Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete. 

1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).

2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.


(Keadaan awal merupakan lanjutan gambar sebelumnya)

Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.

Shell sort (Ascending)

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.

Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :

Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2.

Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2). Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).

Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :

»       Jarak = N

»       Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9

»       Jarak = Jarak / 2. Sudah = false

»       Kerjakan baris 4 sampai dengan 8 selama Sudah = false

»       Sudah = true

»        j = 0

»       Selama (j < N – Jarak) kerjakan baris 8 dan 9

»       Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true

»       j = j + 1

Di bawah ini merupakan prosedur yang menggunakan metode Shell:

void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1)
{
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah)
{
Sudah = true;
for(j=0; j Data[i])
{
Tukar(&Data[j], &Data[i]);
Sudah = false;
} } } } }

Merge sort (Ascending)

Merge sort adalah metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data pertama (T1) adalah sebagai berikut :

3 11 12 23 31

Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :

9 15 17 20 35

Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya sehingga didapat hasil sebagai berikut :

3 9 11 12 15 17 20 23 31 35

Exchange sort (Ascending)

Exchange sort adalah perbandingan suatu pivot dengan elemen yang lainnya, dan melakukan pertukaran jika perlu. Letak pivot terurut dari awal sampai akhir.

Contoh :

Quick sort (Ascending)

Quick sort adalah membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sehingga elemen yang lebih kecil dari pivot berada di sisi kiri sedangkan yang lebih besar di sisi kanan. Suatu elemen tersebut bisa kita pilih secara acak maupun sesuka hati.

Contoh :