Tree pada java
Terminologi
binary tree
maaf saya menggunakan istilah asing untuk
terminologinya. soalnya saya sudah terbiasa pakai istilah ini, kalaupun
diterjemahkan kuq hasilnya malah jadi aneh…
Path
Bayangkan seperti orang yang berjalan dari node ke node lain melalui garis yang menghubungkannya. Garis-garis penghubung yang delewati itulah yang dinamakan dengan path.
Root
Node pada posisi paling atas disebut root. Dalam sebuah tree hanya terdapat satu root saja.
Parent
Setiap node (kecuali
root) mempunyai cabang yang menguhubungkan tepat satu node lain di atasnya. Node di atasnya inilah yang disebut
parent.
Child
Setiap node bisa mempunyai satu atau lebih cabang yang menghubungkan ke
node lainnya. Node di bawahnya inilah yang disebut dengan
child.
Leaf
Node yang tidak mempunyai child disebut dengan
leaf. Dalam sebuah tree hanya ada satu
root saja tetapi bisa mempunyai banyak
leaf.
Subtree
Setiap node bisa dipertimbangkan menjadi root nya
subtree, yang terdiri dari beberapa
children, dan
children nya
children.
Visiting
Sebuah node dikatakan dikunjungi ketika kendali program sampai pada
sebuah node, biasanya untuk tujuan menyelesaikan beberapa operasi pada
node, seperti mengecek nilai datanya kemudian menampilkannya.
Traversing
Traverse maksudnya mengunjungi semua node dalam tree untuk tujuan tertentu, misalnya: untuk mengurutkan datanya.
Level
Level node adalah banyaknya generasi node yang dihitung mulai dari root.
Jika kita mengasumsikan bahwa root adalah level 0, maka children adalah
level 1, grandchildren adalah level 2, dan seterusnya.
Key
Medan data dalam sebuah objek biasanya didesain dengan menggunakan sebuah
key. Nilai dari
key ini digunakan untuk melakukan pencarian data atau operasi lainnya.
Tree menggunakan Java
Beberapa class untuk mendemonstrasikan binary tree di java
Class Node –> untuk membuat node
class Node
{
int iData; // data yang digunakan sebagai kunci
double fData; // data lain
node childKiri; // node child kiri
node childKanan; // node child kanan
public void tampilNode()
{
// (bagian dari tubuh method)
}
}
Class Tree –> membuat susunan Tree nya dimana di dalamnya juga terdapat beberapa method untuk:
pencarian node
penyisipan node
penghapusan node
class Tree
{
private Node root; // satu-satunya data dalam tree
public void cari(int key)
{
tempat penulisan statemen cari
}
public void sisip(int id, double dd)
{
tempat penulisan statemen sisip
}
public void hapus(int id)
{
tempat penulisan statemen hapus
}
// klo ada method laen tulis di sini
} // akhir dari kelas tree
Map pada JAVA
Map pada JAVA
Suatu
array yang berisi N elemen bisa juga dilihat sebagai asosiasi
(pemetaan) antara elemennya dengan bilangan 0, 1, ..., N-1 yang
merupakan indeksnya. Jika i adalah salah satu bilangan ini, maka kita
bisa mengambil elemen yang dipetakan oleh bilangan i, dan juga kita bisa
meletakkan elemen baru pada posisi ke-i.
Suatu peta (
map) adalah
generalisasi dari array. Seperti array, map juga memiliki operasi untuk
mengambil dan meletakkan elemen. Akan tetapi pada map, operasi ini tidak
dilakukan pada bilangan 0, 1, ... N-1, akan tetapi pada sembarang
Object.
Beberapa bahasa pemrograman menggunakan istilah
array asosiatif (associative array) karena kesamaan perintah dengan array biasa. Pada bahasa pemrograman tersebut, kita bisa menuliskan
A["joko"] yang digunakan untuk memetakan "joko" pada suatu elemen di dalam array.
Java tidak menggunakan perintah yang sama pada map, akan tetapi
idenya serupa : Map adalah seperti array yang indeksnya adalah objek
sembarang, bukan integer. Pada map, objek yang digunakan sebagai
"indeks" disebut kunci (
key). Objek yang ditunjuk oleh indeks tersebut disebut nilai (
value).
Satu kunci hanya boleh menunjuk pada satu nilai, akan tetapi satu nilai bisa ditunjuk oleh beberapa kunci.
Dalam Java, map didefinisikan dalam interface
java.util.Map, yang memiliki beberapa metode untuk bekerja dengan map. Jika
map adalah variabel dengan tipe
Map, maka berikut ini adalah beberapa metodenya :
map.get(kunci) -- mengembalikan Object yang ditunjuk oleh kunci. Jika map tidak memiliki nilai yang ditunjuk oleh kunci, maka nilai null akan dikembalikan. Tapi ingat juga bahwa mungkin saja kuncinya ada akan tetapi memang menunjuk pada nilai null. Menggunakan "map.get(kunci)" sama dengan perintah "A[kunci]" pada array A. (Akan tetapi pada map tidak ada pengecualian IndexOutOfBoundsException)map.put(kunci, nilai) -- Mengisi map dengan pasangan kunci dan nilai. Kedua-dua kunci dan nilai bisa berupa objek apa saja. Jika map tersebut telah memiliki kunci maka nilai yang ditunjuk akan diganti dengan yang baru diberikan. Perintah ini mirip dengan "A[kunci] = nilai" pada array.map.putAll(map2) -- jika map2 adalah map lain, maka perintah ini akan mengkopi semua isi pada map2 ke dalam map.map.remove(kunci) -- Jika map memiliki kunci yang menunjuk pada suatu nilai, perintah ini akan menghapus kunci beserta nilai yang ditunjuknya, atau dengan kata lain menghapus pasangan kunci dan nilai pada map sekaligus.map.containsKey(kunci) -- mengembalikan nilai boolean true jika map memiliki kunci yang merujuk pada suatu nilaimap.containsValue(nilai) -- mengembalikan nilai boolean true jika map memiliki nilai yang ditunjuk oleh kunci apapun.map.size() -- mengembalikan int yang berisi jumlah pasangan asosiasi pada map.map.isEmpty() -- mengembalikan boolean true jika map tidak berisi pasangan asosiasi apa-apa.map.clear() -- menghapus semua pasangan asosiasi dalam map.
Metode
put dan
get
jelas merupakan metode yang paling sering digunakan dalam map. Dalam
banyak aplikasi, metode ini mungkin hanya metode ini yang kita butuhkan.
Artinya, menggunakan map sama mudahnya dengan menggunakan array biasa.
Java memiliki dua kelas yang mengimplementasikan interface
Map, yaitu :
TreeMap dan
HashMap.
Dalam
TreeMap,
pasangan kunci/nilai disimpan secara berurutan dalam pohon terurut,
yaitu diurut berdasarkan kuncinya. Supaya bisa bekerja dengan benar,
maka hanya objek yang bisa dibandingkan saja yang bisa digunakan sebagai
kunci. Artinya kelas kunci harus berupa kelas yang mengimplementasikan
interface
Comparable, atau
Comparator harus diberikan pada konstruktornya pada saat
TreeMap dibuat.
HashMap
tidak menyimpan pasangan kunci/nilai dalam urutan tertentu, sehingga
tidak ada batasan objek apa yang bisa disimpan di dalamnya. Hampir semua
operasi dapat berjalan lebih cepat pada
HashMap dibandingkan dengan
TreeMap.
Secara umum, lebih baik menggunakan
HashMap kecuali kita butuh struktur data dalam urutan tertentu yang hanya bisa dilakukan dengan
TreeMap. Atau dengan kata lain, jika kita hanya menggunakan perintah
put dan
get, gunakan
HashMap.
Misalnya progrma direktori telefon, yaitu pada kelas
BukuTelepon yang memiliki pasangan nama/nomor telepon. Kelas ini memiliki operasi
tambahEntri(nama, nomor) dan
ambilNomor(nama), di mana
nama dan
nomor bertipe
String.
Dalam aplikasi pemrograman sebenarnya, kita tidak perlu lagi membuat kelas baru untuk mengimplementasikan
BukuTelepon tersebut, artinya kita bisa langsung menggunakan
Map. Akan tetapi menggunakan
Map mungkin memiliki sedikit kerugian, karena kita dipaksa harus menggunakan
Object bukan
String.
Jika ini masalahnya, maka kita bisa membuat kelas baru yang menggunakan
Map dalam implementasinya, seperti berikut :
import java.util.HashMap;
public class BukuTelepon {
// Menyimpan data telepon
private HashMap info = new HashMap();
public void tambahEntri(String nama, String nomor) {
// Menyimpan nomor telepon pada nama yang sesuai
info.put(nama,nomor);
}
public String ambilNomor(String nama) {
// Mengambil nomor telepon dari nama
// Kembalikan null jika tidak ada nomor telepon untuk nama tsb
return (String)info.get(nama);
}
} // akhir kelas BukuTelepon
Dalam metode
ambilNomor di atas, nilai kembalian dari
info.get(nama) di-type-cast ke dalam
String. Karena kembalian dari metode
get() bertipe
Object maka type cast menjadi penting sebelum nilainya bisa digunakan.
Dengan "membungkus"
Map di dalam kelas
BukuTelepon,
kita menyembunyikan type-cast dalam implementasinya sehingga interaksi
kelas ini dengan kelas lain yang menggunakannya menjadi lebih natural.
Graph pada java
Graf adalah salah satu jenis struktur
data yang terdiri dari titik(vertex) dan garis(edge), dimana dalam graf
tersebut, vertex vertex yang ada dihubungkan oleh edge, hingga menjadi
suatu kesatuan yang disebut graf.
Sebagai contoh
dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai
vertex dan jalur yang menghubungkannya berlaku sebagai edge. Agar lebih
jelas perhatikan gambar dibawah ini : 
Dalam gambar tersebut, terdapat beberapa kota yang berada dipulau jawa
dimana kota kota tersebut dihubungkan oleh beberapa jalur jalur yang
ada. Untuk contoh diatas kita bisa menganggap bawah kota kota yang ada
merupakan vertex, dan jalur jalur yang menghubungkan kota kota tersebut
sebagai edge. Sehingga secara keseluruhan peta diatas dapat dibuat
pemodelannya sebagai sebuah graf. Ada terdapat beberapa jenis graf yang
bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut :
~
Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh
edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A,
harus diperoleh dari edge lain, yaitu edge BA, dan jika edge BA tidak
ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B
memiliki hubungan
~
Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah,
sehigga jika edge AB menghubungkan vertex A ke B, maka secara otomatis
juga menghubungkan vertex B ke A.
~ Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu.
~ Graf Tak Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai.
Untuk
merepresentasikannya dalam pemrograman komputer, graf dapat disusun
dari LinkedList yang berada dalam LinkedList. Perhatikan contoh graf
berarah dibawah ini : 
Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana
baris dan kolom di matriks tersebut menunjukan vertex yang ada. 
Dalam matrik diatas dapat kita lihat bahwa kotak yang berisi angka
satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang
menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal
tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua
vertex tersebut. Untuk representasi dalam pemorgraman komputer, graf
tersebut dapat digambarkan seperti dibawah ini : 
Heap pada java
Stack dan Heap
·
Dalam java, dikenal 2 buah jenis memory, yaitu [1&2]:
1. Stack
(tempat local variable dan tumpukan method)
2. Heap
(tempat instance variable dan object)
·
Bila ada program berikut [1] :
|
Program xx
|
|
1.
public class A {
2.
B b1 = new B();
3.
String s = "halo";
4.
int i = 10;
5.
6.
public static void main(String[] args) {
7.
A a = new A();
8.
a.myMethod();
9.
}
10.
11.
private void myMethod() {
12.
System.out.println(s);
13.
}
14.
}
class
B {}
|
Yang terletak di stack :
1.
Method main()
2.
Method myMethod()
3. Variable
reference a
(baris 7)
Yang terletak di heap :
1. Variable
reference b1
(baris 2)
2. Variable
reference s
(baris 3)
3. Variable
i (baris 4)
4. Object
dari kelas B
(baris 2)
5. Object
String dengan
nilai “halo”
(baris 3)
6. Object
dari kelas A
(baris 7)
2. Garbage Collector
·
Pembahasan garbage collector ini dibatasi hanya pada
object-object non String
[2].
·
Garbage collector (GC) menyediakan solusi otomatis dalam memory
management [2]. Pada kebanyakan kasus, GC membebaskan
kita dari mengatur logic memory management dalam aplikasi [2].
·
Tugas utama GC adalah
menyediakan free space pada heap sebanyak mungkin. Hal ini dilakukan dengan
menemukan dan menghapus object pada heap yang sudah tidak direference oleh
variable apapun [1&2]. Meskipun tugas utama GC adalah
menyediakan free space pada heap sebanyak mungkin, tapi tidak ada jaminan bahwa
di heap ada memory yang cukup untuk berjalannya program java [1&2].
·
Kapan GC berjalan ? JVM
memutuskan kapan menjalankan GC. Melalui program, kita dapat menyarankan
JVM untuk menjalankan GC, akan tetapi yang memutuskan apakah GC perlu berjalan
atau tidak tetaplah JVM (kita hanya dapat menyarankan saja!). Biasanya JVM akan
menjalankan GC bila dirasa free memory sedang rendah [2].
·
Kita tidak dapat mengetahui algoritma yang
digunakan dalam GC [2].
·
Apakah java dapat ”run out of memory” ? Ya, program java
dapat mengalami run out of memory, hal ini terjadi karena terlalu banyak object
“hidup” di dalam heap.
2.1 Kode program yang membuat suatu object layak untuk dihapus
·
Kapan suatu object memenuhi syarat untuk dihapus ? Suatu
object layak untuk dihapus bila tidak ada thread yang dapat mengakses object
ini [2].
·
Setidaknya ada 4 hal yang membuat suatu object layak dihapus,
yaitu [2] :
1.
Memberikan nilai null
pada variable reference.
2.
Mengassign suatu variable reference dengan object lain.
3.
Object yang direference oleh local variable.
4.
Isolating reference
·
Contoh memberikan nilai null pada variable reference [1] :
|
Program 01
|
|
public class GC1
{
public static void main(String[] args)
{
Object o = new Object();
o = null; //memberi nilai null
pada reference variable
}
}
|
·
Contoh mengassign variable reference dengan object lain [1]:
|
Program 02
|
|
public class GC2
{
public static void main(String[] args)
{
Object o1 = new Object();
Object o2 = new Object();
o2 = o1; //mengassign dengan
object lain
}
}
|
·
Suatu object yang hanya direference oleh local variable akan
memenuhi syarat untuk di hapus oleh GC begitu method (tempat local varible)
tersebut selesai dijalankan [1&2].
Contoh [1]:
|
Program 03
|
|
public class GC3
{
public static void main(String[] args)
{
myMethod();
}
public static void myMethod()
{
Object o = new Object();
/*
* object yang direference oleh
local variable o di atas
* memenuhi syarat untuk
dihapus oleh GC begitu method
* ini selesai dijalankan.
*/
//do something!!
}
}
|
·
Isolating reference adalah suatu bentuk hubungan antar object
yang memenuhi syarat untuk dihapus oleh GC meski object-object tersebut ada
yang mereferensi [1&2].
Contoh [2]
:
|
Program 04
|
|
class X
{
X x;
}
public class GC4
{
public static void main(String[] args)
{
X x1 = new X(); //membuat object
X x2 = new X(); //membuat object
/*
* 2 statement di bawah membuat
"circular reference"
*/
x1.x = x2;
x2.x = x1;
/*
* 2 statement di bawah membuat dua
buah object
* kelas X yang dibuat
diatas tidak dapat di
* reference oleh thread
manapun, meskupun
* kedua object itu saling membuat
"circular
* reference"
*/
x1 = null;
x2 = null;
}
}
|
2.2 Meminta JVM melakukan GC
·
Melalui kode program, kita dapat meminta agar JVM
melakukan GC. JVM akan berusaha memenuhi permintaan kita, meski tidak ada
jaminan permintaan kita akan terpenuhi [1&2].
·
Ada 2 cara untuk meminta JVM melakukan GC, yaitu
melalui [2]:
1. System.gc() (lebih direkomendasikan dari pada cara ke dua)
2.
Method gc()
dari suatu instance Runtime
·
Contoh penggunaan method gc() dari
suatu instance Runtime
[2] :
|
Program 05
|
|
package garbageCollector;
import java.util.Date;
public class GC5
{
public static void main(String[] args)
{
Runtime rt = Runtime.getRuntime();
System.out.println("Total memory
JVM = " +
rt.totalMemory());
System.out.println("Free memory
sebelum proses = " +
rt.freeMemory());
//--------------------------proses
Date d = null;
for(int i = 0; i < 10000; i++)
{
d = new Date();
d = null;
}
//--------------------------------
System.out.println("Free memory
setelah proses = " +
rt.freeMemory());
rt.gc(); // Request melakukan GC!!
System.out.println("Free memory
setelah GC = " +
rt.freeMemory());
}
}
|
|
Program di atas
akan menghasilkan :
Total memory
JVM = 2031616
Free memory
sebelum proses = 1862240
Free memory
setelah proses = 1617528
Free memory
setelah GC = 1917448
|
·
Contoh penggunaan System.gc() [2] :
|
Program 06
|
|
package garbageCollector;
import java.util.Date;
public class GC6
{
public static void main(String[] args)
{
Runtime rt = Runtime.getRuntime();
System.out.println("Total memory
JVM = " +
rt.totalMemory());
System.out.println("Free memory
sebelum proses = " +
rt.freeMemory());
//--------------------------proses
Date d = null;
for(int i = 0; i < 10000; i++)
{
d = new Date();
d = null;
}
//--------------------------------
System.out.println("Free memory
setelah proses = " +
rt.freeMemory());
System.gc(); // Request melakukan GC!!
System.out.println("Free memory
setelah GC = " +
rt.freeMemory());
}
}
|
|
Program di atas
akan menghasilkan :
Total memory
JVM = 2031616
Free memory
sebelum proses = 1862240
Free memory
setelah proses = 1617528
Free memory
setelah GC = 1917448
|
2.3 Method finalize()
·
Java menyediakan suatu mekanisme untuk menjalankan
suatu kode sebelum suatu object dihapus oleh GC. Method tersebut terletak pada
method finalize dari yang diturunkan dari kelas Object [2] .
·
Karena kita tidak dapat mengantungkan pada GC untuk
menghapus suatu object, maka kode yang terdapat di method finalize tidak dijamin akan dijalankan [2].
·
Method finalize maksimal dijalankan 1
kali (yang berarti dapat tidak dijalankan) [2].
·
Contoh [1]
|
Program 07
|
|
class Y
{
private String nama = null;
Y(String nama)
{
this.nama = nama;
}
public void finalize()
{
System.out.println(nama
+ " dihapus");
}
}
public class GC7
{
public static void main(String[] args)
{
Y y1 = new Y("Hallo");
Y y2 = new Y("ini");
Y y3 = new Y("percobaan");
Y y4 = new Y("method");
Y y5 = new Y("finalize");
y1 = null;
y2 = null;
y3 = null;
y4 = null;
y5 = null;
System.gc();
}
}
|
|
Program di atas
akan menghasilkan :
finalize
dihapus
method dihapus
percobaan
dihapus
ini dihapus
Hallo dihapus
|
James Gosling, pencipta bahasa komputer Java, mengkonfirmasi pada hari Senin bahwa ia telah bergabung
