TREE (POHON)
adalah salah satu bentuk sirkuit salah satu bentuk graph terhubung yang tidak mengandung sirkuit.
karena merupakan graph terhubung,maka pada pohon (tree) selalu terdapat path yang menghubungkan setiap simpul dalam pohon.
tree dapat juga didefinisikan sebagai kumpulan elemen yang salah satu elemenya di sebut akar(root) dan sisa elemen lainya (simpul)yang terpecah menjadi sebuah himpunan yang saling tidak berhubungan yang di sebut sub pohon (subtree) atau cabang.
Sifat sifat pohon
1. Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
2. Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
3. Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
4. Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1,sampai dengan level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara
5. Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.
Hutan (forest) adalah Kumpulan pohon yang tidak saling berhubungan
(klik untuk memperbesar gambar) Cara menggambarkan bentuk pohon :
* cara pertama
merupakan cara paling banyak digunakan dan paling mudah digunakan,caranya seperti gambar di atas.
* cara kedua
dengan membuat diagram venn seperti gambar di bawah ini
* Cara ketiga
dengan cara menggunakan notasi kurung untuk gambar pada diagram venn di atas.
hasilnya : (P(Q(R,S)),T(U(V,W)))
* Cara Keempat
dengan menggunakan notasi tingkat dan notasi garis
POHON BINAR (BINARY TREE)
Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.
Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul
Karakteristik Pohon binar
1. Setiap simpul paling banyak hanya memiliki dua buah anak.
2. Derajat tertinggi dari setiap simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimmungkinkan tidak memiliki simpul
dibawah ini contoh pohon binar dengan cabang kiri dan kanan
Istilah pada pohon binar(binary tree)
* Pohon binar penuh (full binary tree)
semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang ruas yang sama
* Pohon Binar lengkap(complate binary tree)
hampir sama dengan pohon biner penuh,bedanya tiap cabang memiliki ruas berbeda
* Pohon biner Similer
Dua pohon yang memiliki struktur sama tapi informasinya berbeda
* Pohon biner Ekivalent
Dua pohon yang memiliki struktur sama dan informasi yang sama
* Pohon biner Miring(skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak /turunan kecuali daun.
Deklarasi Pohon Biner dengan program C++
Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan dalam simpul tersebut.
* Tree dapat dibuat dengan menggunakan linked list secara rekursif
* Linked list yang digunakan adalah double linked list non circural
* data yang pertama kali masuk akan menjadi node root
* data yang lebih kecil dari node root akan masuk dan menempati node kiri dari node root,sedangkan jika lebih besar akan masuk dan menempati node sebelah kanan node root
Kamis, 17 Juni 2010
Struktur Pohon / Tree
Searching
Searching adalah pencarian data dengan cara menelusuri data-data tersebut.Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.empat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage
Sequential Search
Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
deklarasi dalam program c++
Binary Search
Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian.Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian.
Prinsip pencarian biner adalah:
• Data diambil dari posisi 1 sampai posisi akhir N
• Kemudian cari posisi data tengah dengan rumus: (posisi awal
+ posisi akhir) / 2
• Kemudian data yang dicari dibandingkan dengan data yang di
tengah, apakah sama atau lebih kecil, atau lebih besar?
• Jika lebih besar, maka proses pencarian dicari dengan posisi
awal adalah posisi tengah + 1
• Jika lebih kecil, maka proses pencarian dicari dengan posisi
akhir adalah posisi tengah –1
• Jika data sama, berarti ketemu.
Sorting
• Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.
• Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
• Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
• Contoh:
• Data Acak : 5 6 8 1 3 25 10
• Ascending : 1 3 5 6 8 10 25
• Descending : 25 10 8 6 5 3 1
Array
Struktur data Array adalah organisasi kumpulan data homogen yang ukuran atau jumlah elemen
maksimumnya telah diketahui dari awal. Array umumnya disimpan di memori komputer
secara kontigu (berurutan). Deklarasi dari array adalah sebagai berikut:
int A[5]; artinya variabel A adalah kumpulan data sebanyak 5 bilangan bertipe
integer.
Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung. Nilai
di masing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati
posisi-posisi lain.
Terdapat dua tipe operasi, yaitu:
1. Operasi terhadap satu elemen/posisi dari array
2. Operasi terhadap array sebagai keseluruhan
Dua operasi paling dasar terhadap satu elemen/posisi adalah
1. Penyimpanan nilai elemen ke posisi tertentu di array
2. Pengambilan nilai elemen dari posisi tertentu di array
1.3.1 Penyimpanan dan Pengambilan Nilai
Biasanya bahasa pemrograman menyediakan sintaks tertentu untuk penyimpanan
dan pengambilan nilai elemen pada posisi tertentu di array.
Contoh:
A[10] = 78, berarti penyimpanan nilai 78 ke posisi ke-10 dari array A
C = A[10], berarti pengambilan nilai elemen posisi ke-10 dari array A
1.3.2 Keunggulan dan Kelemahan Array
Keunggulan array adalah sebagai berikut:
1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu
secara langsung tanpa melalui elemen-elemen lain.
2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemen-
elemen tetangga, baik elemen pendahulu atau elemen penerus 3
3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga,
maka penggunaan penyimpanannya sangat efisien
Kelemahan array adalah sebagai berikut:
Array mempunyai fleksibilitas rendah, karena array mempunyai batasan sebagai berikut:
1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen
adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain
2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit
diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi
terus-menerus, maka representasi statis
• Tidak efisien dalam penggunaan memori
• Menyiakan banyak waktu komputasi
• Pada suatu aplikasi, representasi statis tidak dimungkinkan
Stack / tumpukan
1 DAFTAR LINER
Sebuah daftar linier atau list linier [linear list], merupakan suatu Struktur Data Umum yang terbentuk dari barisan hingga [yang terurut] dari satuan data,ataupun dari Record Elemen yang terdapat di dalam daftar di sebut simpul atou node
File merupakan saiah satu contoh dari daftar linier yang elemen-elemennya berupa Record.Sebagai contoh,Nomor di dalam Buku telepon membentu sebuah daftar linier, Yang apabila daftarmterebut di masukan ke dalam memori secara berangkai akan di dapat sebuah tab
2 stack atau tumpukan
Stack atau tumpukan adalah bentuk khusus dari list linier.Pada stack, penghapus Serta pemasukan elemenya hanya dapat dilakukan pada satu posisi yakni posisi akhir dari list. Posisi ini di sebut Puncak atau Top dari Stack. Elemen stack s pada posisi ini di nyatakan dengan top (S).
Jelasnya bila Stack (S)=[S1,S2….ST] maka top (S) adalah ST. Banyaknya elemen stack S pada saat tertentu biasa kita sebut sebagai NOEL (S)Jadi untuk stack kita di atas, NOEL (S)=T.
Operator penghapus elemen pada Stack disebut POP, sedangkan Operator pemasukan element , disebut PUSH.
E
D
B
S NOEL(S) = 4, TOP(S) = E, dan seterusnya
A
Kita pada hakekatnya tidak membatasi beberapa banyak element dapat masuk ke dalam Stack. Untuk suatu Stack S = [S1,S2….SNOEL], kita katakana bahwa elemen S1 berada di atas elemen Sj, jika I lebih besar dari j. Suatu element tidak dapat kita POP ke luar, sebelum semua elemen di atasnya di keluarkan.
3 OPERASI PADA STACK
Terdapat empat operasi pada Stack, yakni CEATE (Stack), ISEMPETY(Stack), PUSH(elemen,stack), dan POP(Stack). CREATE(S) adalah Operator yang menyebabkan Stack S menjadi Stack hampa.Jadi NOEL (CREATE(S)) adalah 0, dan TOP (CREATE(S)) tak terdevinisi. Operetor ISEMPETY(S) bermaksud memeriksa Stack S hampa atau tidak. Operator PUSH (E,S) akan berkerja menambahkn elemen E pada Stack S,E ditempatkan sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam Stack. TOP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan terjadi apabila kita mencoba melakukan POP(S) terhadap Stack S yang hampa.
4 DEKLARASI STACK DALAM VOBOL DAN PASKAL
Meskipun Stack amat luas digunakan, banyak bahasa pemprograman tidak mempunyai Type Data Stack secara built-in. Dalam hal ini, Pemrogram harus memanipulasi sendiri fasilitas yang dimiliki Bahasa Pemprogram tersebut, untuk dapat melakukan Operasi Stack terhadap Variabel Stack. Mungkin cara yang paling sederhana adalah membentuk Stack dalam bemtuk semacam Array. Satu hal yang nyata membedakan Stack dengan Array adalah banyaknya elemen Stack yang dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah Array selalu tetap. Deklerasi dari Variable S yang bertype data Stack. Diasumsikan bahwa elemen dari S masing – masing bertype data integer. Dan panjang Stack minimum 100 Elemen. Kita mendeklerasi bahwa sebuah Array yang dilengkapi dengan Variable TOP-PTR ini menyatakan subskrip dari elemen TOP(S) dari Stack . Kita menambahkan kombinasi dari Array dan indikator untuk TOP tersebut dengan nama STACK-STRUC. Dengan penyajian seperti ini, berlaku bahwa NOEL(S) = TOP-PTR, ISEMPETY(S) adalah true bila YTOP-PTR = 0, DAN false bila TOP-PTR lebih besar dari 0.
Dalam COBOL :
01 STACK-STRUCT
02 S PIC 9 (5)
OCCURS 100 TIMES.
Dalam Pascal :
Type stackstruct;
record Stack : Array [ 1..100] of integer;
topptr : integer
end
var S : stackstruct;
Kombinasi tidak mengerti aturan INFO yang kita inginkan. Untuk itu Pemprogram harus berhati-hati dan tidak member indeks kepada S sembarang tempat, selain dengan nilai TOP-PTR.
5 APLIKASI STACK
Stack sangat luas pemakaiannya dalam menyelesaikan dalam menyelesaikan problema. Kompiler, Sistem Operasi, dan berbagai Program Aplikasi banyak menggunakan Stack tersebut. Salah satu contoh adalah problema atau Matching Parantheses. Sebuah kapiler mempunyai tugas, salah satu di antaranya adalah menyelidiki apakan pemrogram telah dengan cepat mengikti aturan tatabahasa, atau sintaks, dari Bahasa pemprograman yang bersangkutan.
NOTASI POSTFIX
Aplikasi lain dari stack adalah pada kompilasi dari ekspresi dalam bahasa pemrograman tingkat tinggi. Kompilator harus mampu menyerahkan bentuk yang biasa, misalnya ((A+B)*C/D+E^F)/G ke suatu bentuk yang dapat lebih mudah dipergunakan dalam pembentukan kode objeknya. Cara yang biasa kita lakukan dalam menulis ekspresi aritmetik seperti di atas, dikenal sebagai notasi infix. Untuk operasi binar seperti menjumlah, membagi, mengurangi, mengalikan ataupun memangkatkan, operator tampil di antara dua operand, misalnya operator + tampil di antara operand A dan B pada operasi A + B. Stack dapat digunakan untuk mentransformasikan notasi infix ini menjadi notasi posfix. Pada notasi posfix, kedua operand tampil bersama di depan operator, misalnya AB+atau PQ* dan sebagainya. Kompilator akan lebih mudah menangani ekspresi dalam notasi posfix ini.
Berikut contoh melakukan pengalihan ekspresi infix ke postfix secara manual. Ekspresi infix = A + B / C * D akan dialihkan menjadi ekspresi postfix.
1. Pilih sub-ekspresi yang berisi “dua operand dan satu operator” yang memiliki level tertinggi
di ekspresi di atas. Didapat B / C dan C * D. Pilih yang paling kiri, maka kita peroleh: B / C.
2. Ubah sub-ekspresi tersebut menjadi sebuah operand, misalkan B / C menjadi E, maka
ekspresi semula menjadi: A + E * D.
3. Lakukan langkah ke (2) hingga ekspresi di atas menjadi “dua operand dan satu operator”
saja. Didapat: A + F
4. Alihkan menjadi bentuk postfix: operand-operand-operator, diperoleh A F +
5. Kembalikan setiap operand menjadi ekspresi semula. F tadinya adalah E * D, maka nilai
F = E * D. Satukan dengan ekspresi yang telah menjadi postfix. Hasilnya = A * E + D
6. Ulangi langkah ke (5) hingga terbentuk ekspresi postfix. Didapat A * B + C / D
Dengan demikian, ekspresi infix: A+B/C*D akan menjadi ABC/D*+ dalam notasi
postfix. Perhatikan dan pelajari tabel berikut ini:
Ekspresi Infix Ekspresi Postfix
A + B A + B
A + B * C A + B * C
(A + B) * C A + B * C
A * B + C A + B * C
Bila ada sub-ekspresi di dalam tanda kurung, maka sub-ekspresi tersebut harus dikerjakan terlebih dulu.
Berikut ini diberikan sebuah algoritma untuk mengubah notasi infix ke dalam notasi posfix. Sebuah stack digunakan untuk keperluan ini. Ekspresi diamati satu persatu dari kiri ke kanan. Pada algoritma ini terdapat 4 aturan dasar, sebagai berikut:
1. Jika simbol adalah ‘’(‘’ (kurung buka), maka ia kita PUSH ke dalam stack
2. Jika simbol adalah ‘’)’’ (kurung tutup), POP dari stack elemen-elemen stack, sampai pertama
kali kita POP simbol ‘’(‘’. Semua elemen stack yang di POP tersebu merupakan output,
kecuali ‘’(‘’ tadi.
3. Jika simbol adalah sebuah operand, tanpa melakukan perubahan elemen stack, operand
tersebut langsung merupakan output.
4. Jika simbol adalah sebuah operator, maka jika TOP stack adalah operator dengan\ level lebih
tinggi atau sama, maka elemen TOP kita POP, sekaligus keluar sebagai output, dilanjutkan
proses seperti ini sampai TOP merupakan ‘’(‘’ atau operator dengan level lebih rendah. Kalau
hal ini terjadi, operator (yang diamati) kita PUSH ke dalam stack. Biasanya ditambahkan
simbol ; (titik-koma) sebagai penutup ekspresi. Dalam keadaan ini, kita POP semua elemen
stack, sehingga stack menjadi hampa.
Dapat dicatat bahwa terdapat 3 level operator, yakni pemangkatan (level tertinggi), level menengahnya adalah perkalian (*) dan pembagian (/) dan level terendah adalah penjumlahan (+) dan pengurangan (-). Tabel berikut menunjukkan pelaksanaan algoritma di atas untuk mengubah ekspresi ((A+B)*C/D+E^F)/G; ke dalam notasi postfix. Jadi, ((A+B)*C/D+E^F)/G akan menjadi AB+C*D/EF^+G/ dalam notasi postfix.
Queue / Antrian
Queue (antrian) adalah struktur data dimana data yang pertama kali dimasukkan adalah data yang pertama kali bisa dihapus. Atau bisa juga disebut dengan struktur data yang menggunakan mekanisme FIFO (First In First Out).
queue
queue
Queue dalam kehidupan sehari-hari seperti antrian pada penjualan tiket kereta api, dimana orang yang pertama datang adalah orang yang pertama kali dilayani untuk membeli tiket. Jika ada orang baru yang datang akan membali tiket, maka posisinya berada pada urutan paling belakang dalam antrian tersebut. Orang yang berada pada posisi terakhir dalam antrian adalah yang terakhir kali dapat dilayani dan memperoleh tiket kereta api (kalau kurang beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di teller bank, paket data yang menunggu untuk ditransmisikan lewat internet, antrian printer dimana terdapat antrian print job yang menunggu giliran untuk menggunakan printer, dsb.
Istilah-istilah yang digunakan dalam queue (antrian)
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head).Circular Queue
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah? Situasi seperti itu bisa dilihat seperti gambar berikut:
circular queueUntuk menghindari permasalahan seperti itu (tidak bisa memasukkan data baru) – meskipun queue-nya belum penuh, maka front dan rear-nya berputar (kembali) ke bagian awal array. Kejadian seperti ini dinamakan dengan circular queue (atau kadang-kadang disebut juga dengan istilah ring buffer). Kejadian seperti ini seperti terlihat pada gambar berikut:
circular queue
circular queue
Perhatikan bahwa setelah rear berputar (kembali) ke bagian awal array, posisinya sekarang di bawah front, kebalikan dari posisi aslinya (front berada di bawah rear). Coba hapus beberapa data sehingga pada suatu saat front juga akan berputar (balik) ke bagian awal array, sehingga front dan rear akan ke susunan aslinya (front di bawah rear).
Queue.java
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//————————————————————–
public Queue(int s) // konstruktor
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//————————————————————–
public void insert(long j) // letakkan item (data) di posisi belakang dari queue
{
if(rear == maxSize-1) //
rear = -1;
queArray[++rear] = j; //naikkan rear dan masukkan item (data) pada posisi rear yang baru
nItems++; //tambah satu item lagi
}
//————————————————————–
public long remove() // hapus item (data) yang berada pada posisi front
{
long temp = queArray[front++]; //dapatkan nilainya dan naikkan front
if(front == maxSize) //
front = 0;
nItems–; // item (data) berkurang satu
return temp;
}
//————————————————————–
public long peekFront() //
{
return queArray[front];
}
//————————————————————–
public boolean isEmpty() //benar jika queue-nya kosong
{
return (nItems==0);
}
//————————————————————–
public boolean isFull() // benar jika queue-nya penuh
{
return (nItems==maxSize);
}
//————————————————————–
public int size() // jumlah ietm (data) dalam queue
{
return nItems;
}
//————————————————————–
} // end class Queue
QueueApp.java
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue menampung 5 item (data)
theQueue.insert(10); // masukkan 4 item (data)
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // hapus 3 item (data)
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // masukkan 4 item (data) lagi
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // hapus dan tampilkan
{ // all items
long n = theQueue.remove(); // (
System.out.print(n);
System.out.print(“ “);
}
System.out.println(“”);
} // end main()
} // end class QueueApp
method insert()
Method insert() mengasumsikan bahwa queue tidak penuh (full). Kita tidak melihatnya dalam main(), tetapi kita bisa memanggil insert() hanya setelah memanggil isFull() dan memperoleh nilai kembalian yang salah. Pengisian data dengan cara menaikkan rear dan mengisikan data baru tersebut pada rear yang baru sekarang. Tetapi, jika rear berada di puncak array, pada maxSize-1, maka harus kembali ke posisi terbawah array sebelum penyisipan dilakukan. Caranya dengan memberi nilai rear=-1, sehingga jika terjadi kenaikan pada pada rear, maka rear akan menjadi 0, dasar dari array. Dan akhirnya, nItem bertambah.
Method remove()
method remove mengasumsikan queue-nya tidak kosong. Untuk meyakinkan bahwa queue-nya tidak kosong, anda harus memanggil method isEmpty(). Penghapusan selalu dimulai dengan memperoleh nilai pada front dan kemudian mengurangi front. Jika front-nya terletak pada akhir array, maka harus kembali ke 0. Kemudian nItems dikurangi.
Method peek()
untuk mendapatkan nilai pada front.
Method isEmpty(), isFull(), and size()
untuk mengecek nItems, apakah kosong atau penuh.
Kunjungan pada Tree / pohon biner
Ada tida macam kunjungan pada pohon biner, yaitu kunjungan PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.
1. Kunjungan PreOrder
Kunjungan PreOrder LRO atau sering disebut dengan depth first order
menggunakan urutan sebagai berikut :
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Prosedur kunjungan PreOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini :
Procedure PreOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
Write (Root^.Info);
PreOrder (Root^.kiri);
PreOrder (Root^.kanan);
End;
End;
2. Kunjungan InOrder
Kunjungan InOrder LRO atau sering disebut dengan symmetric order,menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kanan.
Seperti pada kunjungan PreOrder, prosedur kunjungan InOrder dapat dilakukan
dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara InOrder LRO dengan rekursif disajikan berikut ini :
Procedure InOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
InOrder (Root^.kiri);
Write (Root^.Info);
InOrder (Root^.kanan);
End;
End;
3. Kunjungan PostOrder
Kunjungan PostOrder LRO menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Cetak isi simpul yang dikunjungi.
Seperti halnya PreOrde dan InOrder, prosedur kunjungan PostOrder juga dapat
dilakukan dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini :
Procedure PostOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
PostOrder (Root^.kiri);
PostOrder (Root^.kanan);
Write (Root^.Info);
End;
End;
4 Kunjungan LevelOrder
Kunjungan Level order mempunyai urutan sebagai berikut :
kunijungan dimulai dari simpul yang ada pada tingkat 1 (akar),
diteruskan pada simpul ditingkat 2 ,tingkat 3 dan seterusnya
single linked list non circular
Linked List
• Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.
• Linked List sering disebut juga Senarai Berantai
• Linked List saling terhubung dengan bantuan variabel pointer
• Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Bentuk Node Single Linked List non Circular
Pengertian:
• Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL
• Linked List : artinya node-node tersebut saling terhubung satu sama lain.
• Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
• Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Deklarasi Node
typedef struct TNode{
int data;
TNode *next;
};
Penjelasan:
• Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
• Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.
Pembuatan Single Linked List non Circular (2)
• Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Linked List
- Linked List
Merupakan suatu struktur data pengembangan dari konsep ADT (Abstrak Data Type) yang bersifat dinamis. Linked List dapat dimanfaatkan secara effektif sesuai dengan keperluan. Linked List juga dapat benar – benar dihapus / dibersihkan dari memory.Linked List sebenarnya merupakan suatu typedata tersendiri. Di bahasa Java, Linked List bisa berupa suatu Class ataupun Record. Ciri – ciri utama dari Linked List adalah, dia mempunyai minimal dua elemen utama. Elemen – elemen itu adalah data dan pointer untuk menunjukkan ke list berikutnya.- ArrayArray berbeda dengan Linked List. Array merupakan suatu struktur data yang bersifat statis. Array harus dialokasikan terlebih dahulu di dalam memory sebelum kita memakainya.
Perbedaan mendetail antara Array dan Linked List adalah sebagai berikut :
| Linked List | Array |
| - Pengaksesan Dinamis- Pengalokasian random pada alamat memory- Dapat dibebaskan dari memory- Tidak menggunakan konsep indexing
- Pengaksesan untuk searching /sorting lambat | - Pengaksesan Statis- Pengalokasian berurut pada alamat memory- Tidak dapat dibebaskan dari memory- Menggunakan konsep indexing
- Pengaksesan untuk searching atau sorting cepat |
5.
- Linked List
Kita akan lebih efektif jika kita menggunakan konsep Linked List jika kita memerlukan suatu pengaksesan pada struktur data yang lebih dinamis. Konsep yang lebih cocok menggunakan linked list adalah : Stack, Queue, Tree, dan Graph.
Hal ini dikarenakan oleh sifat dinamis dari Linked List. Kita tidak perlu untuk mengetahui berapa block memory yang akan kita akses. Jadi, jika kita butuh block baru pada memory, tinggal menyisipkan pada kanan atau kiri list yang telah ada.
- Array
Kita dapat memanfaatkan secara efektif konsep array dengan mengenal metode indexing pada array. Array merupakan struktur data statis yang mempunyai index penomoran alamat variable array yang dimaksud. Jadi, secara umum, kita dapat mengaksesnya dengan lebih cepat.
Konsep – konsep yang dapat memanfaatkan konsep indexing untuk mempercepat pengaksesannya adalah Sorting dan Searching.
Hal ini dikarenakan oleh penomoran alamat variable pada memory yang telah diketahui terlebih dahulu. Jadi, semisal kita menginginkan mencari variable dengan indeks tengah, kita bisa langsung menujuk ke indeksnya.
- Singly Linked List :
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.
Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.
- Double Linked List :
Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.
- Single Circular Linked List :
Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.
- Double Circular Linked List :
Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.
6. a. Node find(int key)
Suatu method java untuk mencari sebuah nilai pada linkedlist. Algoritma dari Operasi dasar adalah sebagai berikut :
| Node find(int key){ if(now.data==key)return now;else
{ now=now.next; return (find(key)); } } |
b. Void addFirst(int data)
Method untuk membuat Node untuk pertama kali. Algoritma dari Operasi dasar adalah sebagai berikut :
| void addFirst(Node input){ if (isEmpty()){head = input;
tail = input; } else { input.next = head; head = input; } } |
c. Void addFirst(int data)
Method untuk menambahkan list pada awal linked list. Algoritma dari Operasi dasar adalah sebagai berikut :
| void addLast(Node input){ if (isEmpty()){head = input;
tail = input; } else { tail.next = input; tail = input; } } |
d. Void romoveFirst()
Method untuk menghapus list pertama. Algoritma dari Operasi dasar adalah sebagai berikut :
| void removeFirst(){ Node temp = head;if (!isEmpty()){ if (head == tail)
head = tail = null; else { temp = temp.next; head = temp; temp = null; } } else System.out.println(“Data is empty!”); } |
e. Void romoveLast()
Method untuk menghapus list terakhir. Algoritma dari Operasi dasar adalah sebagai berikut :
| void removeLast(){Node temp = head;if (!isEmpty()){if (tail == head){
head = tail = null; } else { while (temp.next != tail){ temp = temp.next; } temp.next = null; tail = temp; temp = null; } } else System.out.println(“Data is empty!”); } |
e. Void romove(int key)
Method untuk menghapus list yang bersesuaian dengan kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :
| void remove(int key){ Node temp = head;if (!isEmpty()){
while (temp != null){ if (temp.next.data == key){ temp.next = temp.next.next; break;} else if ((temp.data == key)&&(temp == head)){ this.removeFirst(); break;} temp = temp.next;} } else System.out.println(“Data is empty!”); } |
f. void insertAfter(int key,int data)
Method untuk menyisipkan list yang serada setelah list yang dimaksud oleh parameter kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :
| void insertAfter(int key,Node input){ Node temp = head;do{if (temp.data == key){
input.next = temp.next; temp.next = input; System.out.println(“Insert data is succeed.”); break; } temp = temp.next; }while (temp!=null); } |
g. void insertBefore(int key,int data)
Method untuk menyisipkan list yang serada setelah list yang dimaksud oleh parameter kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :
void insertBefore(int key,Node input){ Node temp = head;while (temp != null){ if ((temp.data == key)&&(temp == head))
{ this.addFirst(input);
System.out.println(“Insert data is succeed.”);
break;
}
else if (temp.next.data == key)
{ input.next = temp.next;
temp.next = input;
System.out.println(“Insert data is succeed.”);
break;
}
temp = temp.next;
}
}
Read More..Minggu, 13 Juni 2010
Tipe Data
a. Integer ( Bilangan Bulat )
Integer merupakan nilai bilangan bulat baik dalam bentuk desimal maupun hexadecimal. Tipe data numerik yang termasuk integer adalah sebagai berikut :
- Byte : Memiliki nilai integer dari -128 sampai +127 dan menempati 1 byte ( 8 bits ) di memori
- Short : Memiliki nilai integer dari -32768 sampai 32767 dan menempati 2 bytes ( 16 bits ) di memori
- Int : Memiliki nilai integer dari -2147483648 sampai 2147483647 dan menempati 4 bytes ( 32 bits ) di memori
-Long : Memiliki nilai dari -9223372036854775808 sampai 9223372036854775807 dan menempati 8 bytes ( 64 bits ) di memori.
b. Char
Char adalah karakter tunggal yang didefinisikan dengan diawali dan diakhiri dengan tanda ‘ ( petik tunggal ).
c. String
Merupakan urutan-urutan dari karakter yang terletak di antara tanda petik tunggal. Nilai data string akan menempati memori sebesar banyaknya karakter string ditambah dengan 1 byte. Bila panjang dari suatu string di dalam deklarasi variabel tidak disebutkan, maka dianggap panjangnya adalah 255 karakter.
d. Real
Nilai konstanta numeric real berkisar dari 1E-38 sampai 1E+38. E menunjukkan nilai 10 pangkat, dan tipe data ini menempati memori sebesar6 byte.
e. Boolean
Tipe data boolean terdiri dari dua nilai saja, yaitu true dan false. Boolean sangat penting dalam mengevaluasi suatu kondisi, dan sering digunakan untuk menentukan alur program.
Pengertian Struktur data
Struktur Data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. 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.
Read More..Graph pada struktur data
Struktur Data Graph
Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many Keterhubungan dan jarak tidak langsung antara dua kota = data keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri. 1.
Struktur Data Linear = keterhubungan sekuensial antara entitas data 2.
Struktur Data Tree = keterhubungan hirarkis 3.
Struktur Data Graph = keterhubungan tak terbatas antara entitas data. Contoh graph :
Informasi topologi jaringan dan keterhubungan antar
Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge, arc). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Notasi matematis graph G adalah :
G = (V, E)
Sebuah sisi antara verteks x dan y ditulis {x, y}. Subgraph : graph yang merupakan suatu subset (bagian) graph yang connected Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E.
Jenis Graph
a. Directed Graph (Digraph)
Jika sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y, bukan dari y ke x; x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai vektor (x, y).
Contoh Digraph G = {V, E} :
V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}.
b. Graph Tak Berarah (Undirected Graph atau Undigraph)
Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.
Contoh Undigraph G = {V, E}
V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}. Khusus graph, undigraph bisa sebagai digraph (panah di kedua ujung edge berlawanan) Struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear ataupun hirarkis adalah verteks-verteks dalam
ngertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list (digraph), linear 2-way linked list (undigraph)
