Rabu, 29 Desember 2010

Tree

Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen. Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyak sekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan, pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi.

Ilustrasi struktur data tree:

Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : node E memiliki in degree 1 dan out degree 2

Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root

Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dari A dan tree B merupakan left subtree dari A
node G dan F merupakan child dari node C
node F merupakan parent dari node J dan K

Ancestor adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.

Leaf (daun) adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf

Sibling adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height (ketinggian) adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4

Weight (bobot) adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6


BINARY TREE
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

Binary tree terdiri dari :
1. Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)
2. Complete Binary Tree : mirip dengan full binary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf memiliki 2 anak)
3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak


BINARY SEARCH TREE
Binary tree dengan sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya.
Contoh :
42 77 60 90 85 97 50 25 35 15 10 5

Contoh Implementasi Binary Search Tree :

Graph

Graph adalah salah satu jenis struktur data, umumnya terdiri dari vertex dan edge. Vertex biasanya dihubungkan dengan edge sehingga menjadi suatu kesatuan yang disebut graph. Sebagai contohnya bisa dilihat pada peta kota, dimana kota disini menjadi sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge.

Terdapat 3 jenis graph, yaitu :

-Graph Berarah,

-Graph Berbobot, dan;

-Graph Tidak Berbobot.

Cara pengurutan elemen terdapat 3 cara, yakni :

1. Preorder : Node-Left-Right
2. Inorder : Left-Node-Right
3. Postorder : Left-Right-Node

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnGam_MOzGnTcdfEZnfLHsFgYU2a7-l3gHo9k-zLh1qnXx0a7nIuO-ZciAX1cEADnxu6IJRo5QdS2Vb-wBROiDHR1NGNZ2Ifvv3aH20RP7RYYpDmD6WfEomZka9EBtWiWO2rqnJpVNMdaM/s320/graph.jpg


Contoh Gambar Graph

Sifat-sifat Graph

· Sebuah graph mungkin hanya terdiri dari satu simpul.

· Sebuah graph belum tentu semuanya terhubung dengan simpul.

· Sebuah graph mungkin mempunyai simpul yang tak terbubung dengan simpul yang lain

· Sebuah graph mungkin semua simpulnya saling berhubungan.

Queue

Metode ini menggunakan konsep FIFO, dimana data yang pertama masuk, yang akan dihapus pertama kali juga data yang pertama.

Pengoperasian yang tersedia di metode ini adalah berikut ini :


Create : membuat antrian baru

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEis-RzZA4-R4KrcyrHr1hkFCeSP_EtG_PnXkud7LqsO6MP00KzoTdaTBAeiD9thPOKX3DzM4g9Oo8-_sx3MxMVUbx7Y49FsViToU_Jul6HyyVHJqSuQ4IK6jeXVdesHFrVoDR2cgvMHosIK/s1600/q4.jpg


Enqueue : menambah elemen ke antrian

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8VXufkf6fWBadQLQF_P6dnB1R5lLHLHbnqDh0KSPxhfmT9kkGNsH_oLqgHf0l8wD7vXDk3hoHWLk36eAze2HI6hyii5_NfKKE2j2Owt18f8pP3S53OMSNT0HZOXw1qZzZi54DFJBc9tCK/s1600/qi.jpg

Dequeue : menghapus elemen dari antrian.

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwgm6ImDUmutEuFexKdPKHQPIg6m1iMQ1R7Y8CM_UN3XWbbqDz3A4_ESZIWLOaIqek4OTr6mCi6bkY4D0fzjzs-DHoyxTpzkGbPNXErxgZnE5V9EzvMJ6OqnrkuDiMz-UYqQDGyW1FahAf/s320/dequeue.jpg


Isempty : fungsi untuk mengecek antrian tersebut kosong atau tidak.


Isfull : fungsi unutk mengecek antrian tersebut penuh atau tidak.


Overflow : peringatan ini akan muncul jika elemen ditambah ke antrian yang sudah penuh.


Underflow : peringatan ini akan muncul jika elemen dihapus dari antrian yang masih kosong.


Head / Front : elemen antrian paling depan.


Tail / Back : elemen antrian paling belakang.

Stack

Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri Stack :

  • Elemen TOP (puncak) diketahui
  • penisipan dan penghapusan elemen selalu dilakukan di TOP
  • LIFO

Pemanfaatan Stack :

  • Perhitungan ekspresi aritmatika (posfix)
  • algoritma backtraking (runut balik)
  • algoritma rekursif

Operasi Stack yang biasanya :

  1. Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
  2. Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
  3. IsEmpty ()
  4. IsFull ()
  5. dan beberapas selektor yang lain

Contohnya :

1

2

3

4

5

c

b

b

b

a

a

a

a

create (s,5)

Push (s,a)

Push(s,b)

Push(s,c)

Pop(s)

6

7

8

9

10

9

g

g

g

f

f

f

f

a

a

a

a

a

Pop(s)

Push(s,f)

Push(s,g)

Push(s,9)

Pop(s)

Create : pembuatan suatu stack.
Push : pengisian data kedalam stack.
Pop : penghapusan data dari stack (dari paling atas)
Overflow : Stack sudah penuh, jika diisi lagi akan muncul peringatan ini.
Underflow : Stack masih kosong, namun jika ingin hapus lagi, akan muncul peringatan ini.

Himpunan Data

Himpunan data adalah suatu metode struktur data untuk menentukan apa yang perlu ditampilkan atau tidak pada suatu himpunan.

Umumnya pengoperasian himpunan data terdiri dari 3 jenis :

1 Intersection : menemukan nilai yang sama pada kedua himpunan, dan menampilkan hasil pengoperasian tersebut.

2 Union : menggabungkan nilai kedua himpunan, tanpa mengulangi nilai yang sama.

3 Difference B : menemukan nilai yang yang tersedia pada himpunan yang terpilih, namun tidak tersedia pada himpunan tujuan.

Contoh himpunan tersebut dapat dilihat dibawah ini :

Himpunan A : { A , B , C , D , E , F }
Himpunan B : { A , B , G , H , I , J }

Jadi, pengoperasian dapat dilakukan seperti ini :

Intersection : { A , B }
Union : { A , B , C , D , E , F , G , H , I , J }
A Difference B : { C , D , E , F }
B Difference A : { G , H , I , J }

Array

(Array atau Larik) dalam ilmu komputer, Array adalah suatu tipe data terstruktur yang dapat menyimpan banyak data dengan suatu nama yang sama dan menempati tempat di memori yang berurutan (kontigu) serta bertipe data sama pula. Array dapat diakses berdasarkan indeksnya. Indeks array umumnya dimulai dari 0 dan ada pula yang dimulai dari angka bukan 0. Pengaksesan array biasanya dibuat dengan menggunakan perulangan (looping).


Array(1 dimensi)

array satu dimensi merupakan jenis array dasar dan jenis array yang paling sering digunakan, pemakaian array satu dimensi terutama dipakai dalam tipe data string (terutama dalam bahasa Pemograman C).

Terdapat 2 operasi array, adalah :


Pengoperasian terhadap satu elemen/posisi dari array


Pengoperasian terhadap array sebagai keseluruhan

Pengoperasian yang sering terjadi dalam array adalah proses pengambilan nilai elemen dari dank e posisi tertentu di array.

Berikut ini adalah contoh penyimpanan data kedalam array (satu dimensi) :


List[20] = 40, menyimpan nilai 40 kedalam posisi ke-20 dalam array List.


B[3] = “A”, menyimpan nilai “A” kedalam posisi ke-3 dalam array B.


Dan berikut ini adalah contoh pengambilan data dari array (dua dimensi):


Ambil = List[20], mengambil nilai dari posisi ke-20 dalam array List. (yakni : 40)


Txtnama.text = B[3], mengambil nilai dari posisi ke-3 dalam array B. (yakti : “A”)


Array (dua dimensi)

Array dua dimensi merupakan tipe array yang lain. A dua dimensi sering dipakai untuk merepresentasikan tabel dan matriks dalam pemrograman.

Perhatikan table berikut :

0

1

2

3

4

1

A

B

C

D

E

2

F

G

H

I

J

3

K

L

M

N

O

Contoh table Array dua dimensi.


Seperti yang anda dapat lihat, array dua dimensi sering digambarkan sebagai matriks, untuk mempermudah pengertian pada table tersebut. Perbedaan array satu dimensi dan dua dimensi adalah pada array satu hanya terdiri dari sebuah baris dan beberapa kolom, sedangkan array dua dimensi memiliki beberapa baris dan beberapa kolom yang bertipe sama.


Array dalam beberapa bahasa pemograman

1. Bahasa Pascal

array dalam bahasa Pascal dapat didefinisikan dengan indeks awal dan indeks akhirnya.

Contoh:


2. Bahasa C

Array dalam bahasa C selalu dimulai dari indeks 0. Array dapat didefinisikan secara statik atau dinamik. Jika didefinisikan statik, ukuran Array akan tetap dari awal program hingga akhir program. Jika didefinisikan dinamik, ukuran array dapat berubah selama program berjalan karena memesan tempat pada memori heap. Proses pemesanan tempat pada memori disebut dengan alokasi. Sedangkan proses pembebasan memori yang sudah dipesan disebut dengan dealokasi.

Contoh array statik:

Contoh Array dinamik:


3. Bahasa Java

Dalam bahasa Java tipe data array direpresentasikan sebagai sebuah objek khusus. Karena itu pada bahasa Java array yang dibuat selalu bersifat dinamik. Namun walaupun bersifat dinamik, array pada bahasa Java tidak perlu dihancurkan karena proes penghancuran dilakukan secara otomatis melalui suatu prosedur yang disebut denganPengumpulan sampah. Sama seperti bahasa C, indeks larik selalu dimulai dari 0.

Contoh:

4. PHP

Sama seperti di JAVA array di PHP juga merupakan sebuah object lebih tepatnya lagi map terorder. Ada dua tipe array di PHP, indexed array (simple array) dan associated array (key=>value array). Di PHP, element array bisa berupa string, Bilangan, boolean, dan semua tipe data primitive lainnya, termasuk larik juga bisa menjadi element larik lainnya.

Cara medefinisikan array:

Contoh indexed array (simple array):

Contoh associated array:

Penjelasan Struktur Data

Dalam istilah ilmu komputer, struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.


Struktur Data pada Umumnya

1. Array

2. Himpunan Data

3. Stack

4. Queue

5. Graph

6. Tree