Search

 

22 March 2009

[STRUKTUR DATA] Tree/Pohon dalam Bahasa Java

Download PDF Version : Struktur Data Tree/Pohon dalam Bahasa Java

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:

Ilustrasi 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)

    Full Binary Tree

  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)

    Complete Binary Tree

  3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak

    Skewed Binary Tree


BINARY SEARCH TREE
Binary tree dengan sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya.
Contoh :

Binary Search Tree

Contoh Implementasi Binary Search Tree :
/**
* Program membuat binary tree yang memiliki 2 anak dimana insertion
* dilakukan secara terurut, dimana data yang lebih kecil diletakkan di kiri
* dan yang lebih besar diletakkan di kanan.
* @author : Jeffrey Hermanto Halimsetiawan
* Selasa, 1 April 2008
**/

import java.util.*;

class Node{
int data;
Node left;
Node right;
Node(int x){
this.data = x;
}
}

public class BinTree{
private Node root;

/**
* Mengecek apakah tree masih kosong
**/
private boolean isEmpty(){
return (root == null);
}
/**
* Memasukkan suatu nilai ke dalam tree.
* Jika nilai tersebut lebih kecil dari nilai node, maka bergerak ke kiri terus
* hingga menjadi child, begitu juga sebaliknya.
**/
public void insert(int input){
Node temp = new Node(input);
if (isEmpty())
root = temp;
else {
Node cursor = root,
parent = null;
while (cursor != null){
parent = cursor;
if (input < cursor.data)
cursor = cursor.left;
else
cursor = cursor.right;
}
/**
* Menambahkan Node baru pada kiri/kanan Node parent bergantung
* pada nilai input dan nilai yang disimpan Node parent
**/
if (input < parent.data){
parent.left = temp;
return;
}
else {
parent.right = temp;
return;
}
}
}
/**
* Mencari suatu nilai dalam tree berdasarkan prinsip :
* Selama belum menemukan nilai yang sama,
* Jika nilai yang dicari lebih kecil dari nilai yang disimpan dalam Node
* maka bergerak ke left Child begitu juga sebaliknya.
**/
public Node find(int key){
Node cursor = root;
while (cursor != null){
if (cursor.data == key)
return cursor;
else if (key < cursor.data)
cursor = cursor.left;
else
cursor = cursor.right;
}
return null;
}
public boolean delete(int key){
Node cursor = root,
parent = null;
boolean found = false,
isLeftChild = true; //menandai apakah Node yang dihapus merupakan left child
if (!isEmpty()){
while (cursor != null){
parent = cursor;
if (key == cursor.data){
found = true;
break;
}
else if (key < cursor.data){
isLeftChild = true;
cursor = cursor.left;
}
else {
isLeftChild = false;
cursor = cursor.right;
}
}
if (!found)
return false;
else {

/**
* Untuk menghapus leaf (tidak punya child)
**/
if (cursor.left == null && cursor.right == null){
if (cursor == root)
root = null;
else if (isLeftChild)
parent.left = null;
else
parent.right = null;
}
/**
* Jika node yang akan dihapus hanya memiliki salah satu subtree
* maka tinggal memindahkan subtree menggantikan node yang dihapus
**/
else if (cursor.left == null){
if (cursor == root)
root = cursor.right;
else if (isLeftChild)
parent.left = cursor.right;
else
parent.right = cursor.right;
}
else if (cursor.right == null){
if (cursor == root)
root = cursor.left;
else if (isLeftChild)
parent.left = cursor.left;
else
parent.right = cursor.left;
}

/**
* Jika node yang akan dihapus memiliki 2 child, maka cari successornya
* dengan fungsi getSuccessor kemudian hubungkan subtree bagian kanan
* dari node yang dihapus dengan successor
**/
else {
Node successor = getSuccessor(cursor);
if (cursor == root)
root = successor;
else if (isLeftChild)
parent.left = successor;
else
parent.right = successor;
//menyambung successor dengan cursor.right
successor.right = cursor.right;
}
}
}
return true;
}
/**
* Mencari nilai terbesar yang mendekati nilai yang disimpan Node
* yang dihapus, Ilustrasi :
*
* 65
* 59 72
* 32 64
* 62
* misal : nilai yang dihapus 65, maka nilai terbesar yang mendekati adalah 64.
* maka ambil 64 sebagai successor, kemudian gabungkan
* 59
* 32 63
* Kemudian satukan keduanya :
* 64
* 59
* 32 63
* Jadilah urutan tree yang masih memenuhi syarat Binary Search Tree
**/
private Node getSuccessor(Node localNode){
Node parent = null,
successor = localNode,
cursor = localNode.left;
while (cursor != null){
parent = successor;
successor = cursor;
cursor = cursor.right;
}
if (successor != localNode.left){
parent.right = successor.left;
successor.left = localNode.left;
}
return successor;
}
/**
* Method traverse untuk mengelilingi Node-Node dalam tree
**/
public void traverse(int tipe){
switch (tipe){
case 1:
System.out.print("\nPreorder traversal:\n");
preOrder(root);
break;
case 2:
System.out.print("\nInorder traversal:\n");
inOrder(root);
break;
case 3:
System.out.print("\nPostorder traversal:\n");
postOrder(root);
break;
}
System.out.println('\n');
}
private void preOrder(Node localRoot){
if (localRoot == null) return;
System.out.print(localRoot.data+" ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
private void inOrder(Node localRoot){
if (localRoot == null) return;
inOrder(localRoot.left);
System.out.print(localRoot.data+" ");
inOrder(localRoot.right);
}
private void postOrder(Node localRoot){
if (localRoot == null) return;
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data+" ");
}

}

[Database] Access Database (mdb) and Java Connectivity

Mungkin banyak yang masih bingung (termasuk saya), cara untuk mengkoneksikan database access (.mdb) dengan Java. Nah di sini, saya akan mencoba untuk mengulas langkah-langkahnya.

  1. Buat database Access dengan format .mdb, misalnya : hospital.mdb
    Misalnya, dalam hospital.mdb terdapat tabel Dokter terdapat field-field sebagai berikut :
    ID Nama Alamat Telp Golongan_ID Spesialisasi_ID ShiftKerja_ID

  2. Membuat ODBC
    ODBC merupakan aturan yang digunakan untuk mengakses sebuah database. Caranya :
    ~ Start - Control Panel - Administrative Tools - Data Sources(ODBC)

    Data Sources (ODBC)

    ~ Pilih tab User DSN - Add
    ~ Pilih Select

    Select Database

    ~ Pilih OK
    ~ Isi textbox Database Source Name, misalnya hospital

    Database Source Name

    ~ Klik Advanced, kemudian isi textbox Login Name dan Password misalnya: Login Name --> admin dan Password --> admin

    Login Name and Password

    ~ Klik OK
    ~ Kemudian klik OK lagi, dan pada User Data Sources akan muncul 'hospital'

  3. Membuat codingan javanya
    Contohnya seperti ini:
    import java.sql.Connection;
    import java.sql.DriverManager;
    import java.sql.ResultSet;
    import java.sql.Statement;

    /**
    *
    * @author Jeffrey
    */
    public class Main {
    private class tes{

    }
    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
    // TODO code application logic here
    try {
    Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
    String cs = "jdbc:odbc:hospital;uid='admin';pw='admin";
    Connection cn = DriverManager.getConnection(cs);
    String qry = "SELECT * FROM Dokter";
    Statement stm = cn.createStatement();
    ResultSet rs = stm.executeQuery(qry);
    while(rs.next()) {
    System.out.println("ID : "+rs.getString("ID"));
    System.out.println("Nama : "+rs.getString("Nama"));
    System.out.println("Alamat : "+rs.getString("Alamat"));
    }
    cn.close();
    } catch (Exception ex) {
    ex.printStackTrace();
    }
    }

    }



Ya, program diatas akan menampilkan query : "SELECT * FROM Dokter", yaitu: mengambil semua record pada tabel Dokter. Kemudian,
           while(rs.next()) {
System.out.println("ID : "+rs.getString("ID"));
System.out.println("Nama : "+rs.getString("Nama"));
System.out.println("Alamat : "+rs.getString("Alamat"));
}

hanya akan menampilkan field ID, Nama dan Alamat dari record-record pada tabel Dokter.

[Database] Oracle Database (Oracle XE) and C# Connectivity

Download PDF Version : Oracle Database (Oracle XE) dan C# Connectivity

Langkah-langkah yang harus dilakukan sebelum mengkoneksikan Oracle Database dengan aplikasi desktop C# adalah :

  1. Menginstall Oracle XE kemudian menggunakan user yang otomatis di-generate “system” atau membuat user baru,

  2. Jika service database masih belum berjalan maka lakukan Start Database,

  3. Menginstall IDE yang mendukung C#, sebagai contoh kali ini menggunakan Visual C#,

  4. File – New – Project kemudian pilih Windows Forms Application beri nama Solution yang diinginkan,

  5. Pada Solution Explorer, klik kanan pada References kemudian Add References. Pilih Oracle.DataAccess.dll dan klik OK,

  6. Pada Solution Explorer, klik kanan pada nama project anda misal “Kepegawaian” kemudian

  7. Add – New Item pilih C# Class dan beri nama semisal Koneksi.cs,

  8. Bagian yang paling penting dari Koneksi.cs adalah
    private string OracleServer = "Data Source=(DESCRIPTION="
    + ADDRESS_LIST=(ADDRESS=(PROTOCOL=TCP)(HOST=localhost)(PORT=1521)))"
    + "(CONNECT_DATA=(SERVER=DEDICATED)(SERVICE_NAME=XE)));"
    + "User Id=jeffrey;Password=jeffrey;";

    HOST merupakan alamat IP dari server database Oracle, jika menggunakanOracle XE maka database
    Oracle terdapat pada localhost.
    SERVICE NAME adalah XE jika menggunakan Oracle XE.
    User Id dan Password diisi sesuai dengan User ID dan Password pada database server.

    Koneksi.cs :
    using System;
    using System.Collections.Generic;
    using System.Text;
    using System.Data;
    using System.Windows.Forms;
    using Oracle.DataAccess.Client;

    public class Koneksi
    {
    private OracleConnection conn;

    private string OracleServer = "Data Source=(DESCRIPTION="
    + "(ADDRESS_LIST=(ADDRESS=(PROTOCOL=TCP)(HOST=localhost)(PORT=1521)))"
    + "(CONNECT_DATA=(SERVER=DEDICATED)(SERVICE_NAME=XE)));"
    + "User Id=jeffrey;Password=jeffrey;";

    public bool Open()
    {
    try
    {
    conn = new OracleConnection(OracleServer);
    conn.Open();
    return true;
    }
    catch (Exception ex)
    {
    MessageBox.Show(ex.Message);
    }
    return false;
    }

    public void Close()
    {
    conn.Close();
    conn.Dispose();
    }

    public DataSet ExecuteDataSet(string sql)
    {
    try
    {
    DataSet ds = new DataSet();
    OracleDataAdapter da = new OracleDataAdapter(sql, conn);
    da.Fill(ds, "result");
    return ds;
    }
    catch (Exception ex)
    {
    MessageBox.Show(ex.Message);
    }
    return null;
    }

    public OracleDataReader ExecuteReader(string sql)
    {
    try
    {
    OracleDataReader reader;
    OracleCommand cmd = new OracleCommand(sql, conn);
    reader = cmd.ExecuteReader();
    return reader;
    }
    catch (Exception ex)
    {
    MessageBox.Show(ex.Message);
    }
    return null;
    }

    public int ExecuteNonQuery(string sql)
    {
    try
    {
    int affected;
    OracleTransaction mytransaction = conn.BeginTransaction();
    OracleCommand cmd = conn.CreateCommand();
    cmd.CommandText = sql;
    affected = cmd.ExecuteNonQuery();
    mytransaction.Commit();
    return affected;
    }
    catch (Exception ex)
    {
    MessageBox.Show(ex.Message);
    }
    return -1;
    }
    }

  9. Mengakses database dengan memanfaatkan method-method pada class Koneksi.cs, semisal menggunakan Form1.cs
    Form1.cs :
    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Windows.Forms;
    using Oracle.DataAccess.Client;

    namespace WindowsFormsApplication2
    {
    public partial class Form1 : Form
    {
    public Koneksi con;

    public Form1()
    {
    InitializeComponent();
    this.con = new koneksi();
    }

    private void button1_Click(object sender, EventArgs e)
    {
    this.con.Open();
    OracleDataReader odr;
    odr = this.con.ExecuteReader(textBox2.Text);
    while (odr.Read()) {
    Console.Write(odr["KARYAWAN_ID"]+"\t");
    Console.Write(odr["KARYAWAN_NAMA"] + "\t");
    Console.WriteLine(odr["KARYAWAN_TGLMASUK"] + "\t");
    }
    this.con.Close();
    }

    private void button2_Click(object sender, EventArgs e)
    {
    this.con.Open();
    this.con.ExecuteNonQuery(textBox1.Text);
    this.con.Close();
    }
    }
    }

  10. Selain menggunakan method ExecuteReader(string sql) dan ExecuteNonQuery(sql), akses database
    dapat juga menggunakan method ExecuteDataSet(string sql) dengan return value DataSet yang ditampilkan langsung dengan menggunakan DataGridView.