STRUKTUR DATA PROGRAM INPUT DATABSE MAHASISWA MENGGUNAKAN APLIKASI DEV C++ 5.1.1

MAKALAH

STRUKTUR DATA

PROGRAM INPUT DATABSE MAHASISWA MENGGUNAKAN

APLIKASI DEV C++ 5.1.1 

Disusun 0leh:

Ambok tatang (1560100207)

Suci rahmadiany (1660100148)

Doli juliadi (1660100174)

Dosen Pengampuh: Eka Sahputra, S.kom, M.kom

FAKULTAS TEKNIK

PROGRAM STUDI INFORMATIKA

UNIVERSITAS MUHAMMADIYAH BENGKULU

2018-2019

KATA PENGANTAR

Puji serta syukur kehadirat Allah SWT,  karena dengan rahmat dan hidayah-Nyalah kami dapat menyelesaikan makalah ini tepat pada waktunya.  Shalawat beriring salam selalu kita panjatkan kepada Rasullullah SAW,  karena kegigihan beliau dan ridho-Nyalah kita dapat merasakan kenikmatan dunia seperti sekarang ini.

Adapun  tujuan  dari penulisan  makalah  ini  adalah untuk  memenuhi tugas yang diberikan olah  Bapak  Eka Sahputra S.kom,M.kom. selaku dosen pembimbing. makalah  ini juga bertujuan untuk menambah pengetahuan dan wawasan bagi pembaca sekalian.

Kami sekelompok  mengucapkan  terima kasih kepada Bapak Eka Sahputra S.kom,M.kom selaku dosen pembimbing mata kuliah Struktur data.

Kami sekelompok  menyadari bahwasanya makalah ini masih jauh dari kesempurnaan, oleh karena itu  kritik dan saran penulis harapkan dari pembaca sekalian demi terciptanya kesempurnaan dalam  penyusunan  makalah  ini. Semoga makalah ini bermanfaat bagi yang membacanya.Terimakasih.

Bengkulu, 23 Oktober 2018

Penyusun

…………………

DAFTAR ISI

KATA PENGANTAR................................................................................................... ..i

DAFTAR ISI ................................................................................................................... ii

BAB 1 PENDAHULUAN................................................................................................ 1

1.1.Latar belakang........................................................................................................... 1

1.2.Rumusan masalah...................................................................................................... 1

1.3.Tujuan....................................................................................................................... 1

BAB II............................................................................................................................. 2

2.1.Dasar teori................................................................................................................. 2

a.Algoritma.......................................................................................................... 2

b.StrukturData...................................................................................................... 2

BAB III PEMROGRAMAN DAN HASIL........................................................................ 3

3.1Pemrograman  procedural........................................................................................... 3

3.2Prosedur...................................................................................................................... 3

3.3Array /larik................................................................................................................. 3

3.4Gambaran  umum  program........................................................................................ 4

3.5Flowchat program....................................................................................................... 4

3.6Source Code............................................................................................................... 5

PENUTUP........................................................................................................................ 8

KESIMPULAN................................................................................................................ 8

SARAN............................................................................................................................ 8

DAFTAR PUSTAKA....................................................................................................... 9

BAB I

PENDAHULUAN

1.1 Latar belakang

Perkembangan teknologi saat ini sangat berkembang dengan pesat. Setiap jam, menit, detik selalu berkembang dan terus berkembang. Hal ini dapat kita lihat di kehidupan kita sehari-hari dimana kita tidak bisa lepas dari namanya handphone, komputer, pc tablet, iphone dan lain-lain.

Dengan kemajuan jaman maka saat ini pendataan mahasiswa dengan menggunakan penulisan manual dapat membuang banyak waktu, tenaga, dan juga biaya yang dikeluarkan.Dengan menggunakan teknologi saat ini maka kita dapat menggunakan komputer sebagai alat atau media untuk menginput dan menyimpan data-data mahasiswa.Sehingga dapat menghemat waktu, tenaga, dan juga biaya yang dikeluarkan.

Dengan menggunakan bahasa pemrograman pascal kita dapat melakukan pendataan mahasiswa secara komputerisasi. Sehingga dapat membantu para staff dalam melakukan pendataan mahasiswa.Pascal sendiri Pascal sebagai salah satu bahasa tingkat tinggi (high-level language) untuk dapat dapat dikenali oleh computer harus diterjemahkan menjadi bahasa mesin. Untuk itu dikembangkan sebuah program penerjemah yang disebut dengan kompilator (compiler).

1.2 Rumusan masalah

Berdasarkan latar belakang yang telah dipaparkan di atas, maka penulis telah menentukan beberapa rumusan masalah dalam pembuatan program perhitungan nilai akhir dan data mahasiswa.yaitu:

1. Gambaran umum program;

2. Flow Chart program;

3. Koding program;

4. Lay out program.

1.3 Tujuan

Sejalan dengan rumusan masalah di atas, makalah ini disusun dengan tujuan untuk mengetahui dan mendeskripsikan:

1. Pembaca  dapat mengerti fungsi prosedur pada pascal;

2. dapat / bisa menjalankan program aplikasi database mahsiswa;

3. Implementasi sebuah program.

BAB II

PEMBAHASAAN

2.1 Dasar Teori

A. Algoritma       

Ditinjau dari asal-usul katanya, kata Algoritma sendiri mempunyai sejarah yang aneh. Orang hanya menemukan kata algorism yang berarti proses menghitung dengan angka arab. Anda dikatakan algorist jika Anda menghitung menggunakan angka arab. Para ahli bahasa berusaha menemukan asal kata ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut yang berasal dari nama penulis buku arab yang terkenal yaitu Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi. Al-huwarizmi dibaca orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal-Muqabala yang artinya “Buku pemugaran dan pengurangan” (The book of restoration and reduction).Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra).Perubahan kata dari algorism menjadi algorithm muncul karena kata algorism sering dikelirukan denganarithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa, maka lambat laun kata algorithm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam bahasa Indonesia, kata algorithm diserap menjadi algoritma.“Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis”.

 Kata logis merupakan kata kunci dalam algoritma.Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar.Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu.Pertimbangan dalampemilihan algoritma adalah, pertama, algoritma haruslah benar. Artinya algoritma akan memberikan keluaran yang dikehendaki dari sejumlah masukan yang diberikan. Tidak peduli sebagus apapun algoritma, kalau memberikan keluaran yang salah,

B. Struktur Data

            Dalam istilah ilmu komputer, sebuah Struktur 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.

BAB III

PEMROGRAMAN DAN HASIL

3.1 Pemrograman Prosedural

Pada pemrograman dikenal beberapa paradigma yang dipakai dalam memecahkan suatu masalah. Penggunaan suatu paradigm ditujukan sebagai cara pemrogram dalam memandang setiap entitas dalam dunia nyata dan relasi antara entitas tersebut, sehingga memudahkannya dalam menerjemahkannya menjadi suatuprogram. Di sisi lain, penggunaan suatu paradigma akan membatasi/mempersempit cara pandang pemrogram. Dalam tulisan ini akan digunakan pemrograman dengan paradigma prosedural.

Pemrograman prosedural didasari oleh konsep mesin Von Neumann yang disebut stored program concept. Suatu program terdiri atas dua bagian yaitu algoritma dan struktur data. Bagaimana cara kerja dari suatu program ditentukan oleh sekumpulan perintah yang akan dilaksanakan secara sekuensial oleh suatu pemroses tunggal. Inilah yang disebut algoritma. Dalam proses pelaksanaan sampai mengeluarkan suatu hasil, program membutuhkan data yang akan diolahnya. Data tersebut akan disimpan dalam memory komputer. Dalam program data tersebut akan distrukturisasikan sehingga akan memudahkan dalam pengolahannya. Inilah yang disebut struktur data. Paradigma prosedural membatasi cara penyusunan algoritma dan strukturisasi data sehingga dekat dengan konsep mesin Von Neumann. Meskipun pemrograman ini sangat tidak manusiawi, namun sangat efisien karena kedekatannya dengan mesin.

3.2Prosedur

Adalah suatu program terpisah dalam blok sendiri yang berfungsi sebagai subprogram (program bagian).  Diawali dengan kata PROCEDURE  didalam bagian deklarasi prosedur .  Prosedur banyak digunakan pada program  yang terstruktur karena  merupakan penerapan konsep program modular, yaitu memecah-mecah program yang rumit menjadi program-program  bagian yang lebih sederhana dalam bentukm prosedur-prosedur . Untuk hal-hal yang sering dilakukan berulang-ulang,  cukup dituliskan sekali saja dalam prosedur dan dapat dipanggil atau dipergunakan sewaktu-waktu bila diperlukan.

3.3 Array / Larik

Adalah tipe terstruktur yang terdiri dari sejumlah komponen komponen yang mempunyai tipe data yang sama. Array dapat bertipe sederhana byte, word, integer, real, boolean, char, string dan tipe scalar atau subrange. Suatu array mempunyai jumlah komponen yang banyaknya tetap dan ditunjukkan oleh suatu indeks yang disebut index type (tipe indeks) Setiap komponene dalam array dapat diakses dengan menunjukkan nilai indeksnya atau disebut juga dengan istilah subscrip.

3.4  Gambaran umum program

Program Database  mahasiswa ini dibuat untuk memudahkan dalam pendataan , dimana seorang guru atau dosen dengan mudah dan cepat memasukan atau mencari data mahasiswa, Program ini dibuat dengan menggunakan bahasa pemrograman Pascal dan ditulis dengan aplikasi Dev C++ For Window dengan lay out program yang sederhana sehingga user dapat dengan mudah mengoperasikannya.

 Gambar 1. Pemrograman dev C++

3.5  Flowchat Program

Diagram alur (flowchart) merupakan gambar atau bagan yang memperlihatkan urutan dan hubungan antar proses beserta instruksinya. Bagan ini dinyatakan dengan simbol. Dengan emikian setiap simbol menggambarkan proses tertentu sedangkan hubungan antar proses digambarkan dengan garis penghubung. Simbol-simbol diagram alur.

Flowchat program database mahasiswa :

3.6 Source code

Pada Pembuatan Program database mhs ini ketentuan yang saya buat adalah seperti ini :

           Nama :             ...........

           Alamat             :..........

           Tempat Lahir   :.........

           Tanggal Lahir  :..........

           NPM                :.........

           Jurusan            :..........

           Jenis Kelamin  :.......... 

            Atau Tidak seperti ini juga tidak apa kalian tinggal ganti saja sesuai apa yang kalian inginkan ketentuan diatas hanya contoh saja untuk source codenya bisa dilihat dibwah ini :

 #include<iostream>

#include<stdio.h>

#include<conio.h>

using namespace std;

int main()

{

    char nm[20];

    char alm[100];

    char tmplhr[30];

    char tgllhr[30];

    char npm[40];

    char jrs[30];

    char jk[40];

    {

    cout<<"\tPROGRAM DATA DIRI "<<endl;

    cout<<"*****************************"<<endl;

    cout <<" Nama\t\t : ";

    cin.getline(nm, sizeof(nm));

    cout <<" Alamat\t\t : ";

    cin.getline(alm, sizeof(alm));

     cout <<" Tempat Lahir\t : ";

    cin.getline(tmplhr, sizeof(tmplhr));

    cout <<" Tanggal Lahir\t : ";

    cin.getline(tgllhr, sizeof(tgllhr));

    cout <<" NPM\t\t : ";

    cin.getline(npm, sizeof(npm));

    cout <<" Jurusan\t : ";

    cin.getline(jrs, sizeof(jrs));

    cout <<" Jenis Kelamin\t : ";

    cin.getline(jk, sizeof(jk));

    cout<<endl;

    cout<<"***************************************"<<endl;

    cout<<" Data Pribadi Saya"<< endl;

    cout <<" Nama Anda\t\t : "<< nm << endl;

    cout <<" Alamat Anda\t\t : "<< alm << endl;

    cout <<" Tempat Lahir Anda\t : "<< tmplhr << endl;

    cout <<" Tanggal Lahir Anda\t : "<< tgllhr << endl;

    cout <<" NPM Anda\t\t : "<< npm << endl;

    cout <<" Jurusan\t\t : "<< jrs << endl;

    cout <<" Jenis Kelmin Anda\t : "<< jk << endl;

    cout <<" By<Budiman_Blog>"<<endl;

    }

    getch();

}

            Setelah itu kita compile program tersebut jika sudah dicompile maka tinggal kita Run programnya maka akan seperti ini :

Gambar 2. Hasil akhir pemrograman devC++

PENUTUP

4.1KESIMPULAN

Program hitung nilai akhir dan database mahasiswa ini dibuat untuk memudahkan dalam pekerjaan dimana seorang user dengan mudah dan cepat dalam menghitung nilai akhir dan menginputkan data mahasiswa.Program ini dibuat dengan menggunakan bahasa pemrograman Pascal. Diagram alur (flowchart) merupakan gambar atau bagan yang memperlihatkan urutan dan hubungan antar proses beserta instruksinya. Koding program adalah perintah program dengan struktur pemrograman bahasa Pascal dan Lay out program adalah hasil akhir dari pemrograman yang akan diimplementasikan.

4.2SARAN

sesuai dengan pepatah “tiada gading yang tak retak” dengan demikian kami kelompok 3 menyadari sepenuhnya bahwa makalah ini masih sangat jauh dari kesempurnaan, hal ini dikarenakan keterbatasan wawasan maupun sumber-sumber data yang dimiliki penulis, dengan demikian kritik dan saran dari berbagai pihak sangat dinanti guna penyempurnaan malah ini.

DAFTAR PUSTAKA

Bryon Goffried, 1986. Programming with PASCAL, Schaum Series, New York.  

http://www.wikipedia.com

http://www.nusinau.com

STRUKTUR DATA

MAKALAH

STRUKTUR DATA

Penerapan Teori Pohon Dalam Kajian Struktur Data

Disusun 0leh:

Ambok tatang

Npm:1560100207

PROGRAM STUDI INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS MUHAMMADIYAH BENGKULU

2015-2016

KATA PENGANTAR

Makalah ini membahas tentang penerapan teori pohon dalam kajian struktur data dimana beberapa penerapannya merupakan salah satu struktur penyimpanan data terbaik.

Salah satu penerapan teori pohon yang paling berguna dan dipakai yaitu konsep binary search tree dimana konsep ini memberikan struktur data yang memudahkan operasi pencarian, penambahan, dan penghapusan terhadap data. Operasi tersebut lebih efisien dan jauh lebih baik pada konsep ini dibanding sequential search pada senarai berkait dalam waktu eksekusi / run-time.

Dari konsep binary search tree ini dikembangkan lagi suatu struktur penyimpanan data yang merupakan modifikasi dari binary search tree tersebut yaitu AVL-Tree dan Splay Tree yang masing-masing mempunyai keunggulan pada kasus tertentu yang sekarang ini sering dijumpai.

AVL- Tree merupakan modifikasi binary search tree yang tinggi setiap upapohon kiri dan upapohon kanan sama atau setidaknya selisih antara keduanya tidak lebih dari 1. Keunggulan dari AVL-Tree antara lain untuk mengoptimasi pencarian data terutama untuk kasus pohon yang condong ke kiri atau ke kanan sehingga pencarian akan jauh lebih mudah apabila pohon tersebut seimbang. Kasus pohon yang condong ke kiri atau kanan itu mungkin saja terjadi terutama apabila penambahan elemen dan penghapusan elemen dilakukan terus-menerus dan tidak dapat diketahui urutannya.

Sedangkan Splay-Tree justru kebalikan dari AVL-Tree yang tidak mempermasalahkan kecondongan upapohonnya namun setiap kali data diakses maka simpul dari data yang diakses tersebut akan dinaikkan keatas mendekati akar pohon. Konsep ini sangat berguna untuk struktur data jaringan rumah sakit.

Dengan demikian dapat disimpulkan bahwa penerapan teori pohon sangatlah bermanfaat dalam kajian struktur data.

DAFTAR ISI

KATA PENGANTAR................................................................................................... ......... i

DAFTAR ISI.................................................................................................................. ......... ii

BAB 1

PENDAHULUAN......................................................................................................... ......... 1

a.       Latar belakang............................................................................................ ......... 1       

b.      Rumusan masalah....................................................................................... ......... 1

c.       Batasan masalah......................................................................................... ......... 1

d.      Tujuan......................................................................................................... ......... 1

BAB II

LANDASAN TEORI.................................................................................................... ......... 2

a.       Struktur penyimpanan data........................................................................ ......... 2

a.       Penyimpanan data static................................................................. ......... 2

b.      Penyimpanan data dinamik............................................................. ......... 4

BAB III

IMPLEMENTASI TEORI POHON.............................................................................. ......... 6

a.       Binary search tree....................................................................................... ......... 6

a.       Gambaran permasahan..................................................................... ......... 6

b.      Definisi Binary Search Tree............................................................. ......... 7

a.       Operasi Pencarian................................................................ ......... 7

b.      Operasi Penambahan Elemen............................................... ......... 9

c.       Operasi Penghapusan Elemen............................................. ......... 9

b.      AVL-Tree                                                                                                     ......... 11

a.       Definisi AVL-Tree........................................................................ ......... 11

b.      Operasi Pada AVL-Tree................................................................ ......... 12

a.       Operasi Pencarian Elemen................................................... ......... 13

b.      Operasi Penambahan Elemen............................................... ......... 15

c.       Operasi Penghapusan Elemen.............................................. ......... 15

PENUTUP....................................................................................................................... ......... 16

KESIMPULAN................................................................................................................ ......... 16

DAFTAR PUSTAKA....................................................................................................... ......... 17

    

BAB I

PENDAHULUAN

A.  Latar belakang

Teori pohon merupakan salah satu teori yang cukup tua karena sudah dikenal sejak tahun 1857, dimana ketika itu matematikawan Inggris Arthur Cayley menggunakan teori pohon ini untuk menghitung jumlah senyawa kimia.¹

Teori pohon ini sebenarnya adalah suatu mekanisme penyelesaian suatu masalah dengan menganalogikan permasalahan tersebut kedalam struktur pohon untuk memudahkan pencarian solusi masalah tersebut. Teori pohon ini juga merupakan salah satu penerapan konsep graf Dimana pohon itu dapat didefinisikan sebagai graf tak-berarah terhubung yang tidak mengandung sirkuit. ¹

Kajian struktur data merupakan kajian yang sangat penting dalam bidang informatika. Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan struktur data yang efisien yang dapat meningkatkan kinerja program

B.  Rumusan masalah

Kajian struktur data merupakan kajian yang sangat penting dalam bidang informatika. Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan struktur data yang efisien yang dapat meningkatkan kinerja program

C.  Batasan masalah

Teori pohon ini merupakan teori yang sangat berguna dalam struktur data dimana aplikasi-aplikasi dari teori pohon ini dapat dijadikan struktur penyimpanan data yang sangat baik dalam kasus tertentu yang mana kasus tersebut sudah umum ditemui sekarang ini.

D.  Tujuan

Oleh karena itu dalam makalah ini akan dijelaskan beberapa aplikasi teori pohon yang dipakai untuk membentuk suatu struktur penyimpanan data yang efisien.

BAB II

LANDASAN TEORI

2. Struktur Penyimpanan Data

Terdapat 2 garis besar struktur penyimpanan data yang telah diimplementasikan secara global yaitu penyimpanan secara statik dan dinamik.

2.1 Penyimpanan Data Statik

Penyimpanan data secara statik merupakan penyimpanan data dimana memori yang disiapkan untuk dipakai sudah ditentukan dari awal. Implementasi dari penyimpanan data seperti ini lebih kepada struktur data yang menggunakan tabel kontigu. Penyimpanan data dengan cara seperti ini tentunya memiliki kelebihan dan kekurangan.

Kelebihan dari penyimpanan data statik ini adalah data dapat diakses langsung asalkan kita mengetahui diindeks keberapa data disimpan atau dapat juga disebut pengambilan data (data retrieval) lebih mudah.

Kekurangan dari penyimpanan data statik ini adalah kita tidak tahu apakah tabel terisi penuh atau tidak dan kita juga tidak tahu batas indeks yang dipakai dan juga elemen tabel hanya bisa sejenis, tidak bisa terdapat jenis elemen yang berbeda pada sebuah tabel kontigu. Dan juga walaupun data masukan tidak ada atau tabel kosong, memori yang dipakai tetap sama dengan tabel penuh, sehingga dapat dikatakan penyimpanan data secara statik ini boros dalam pemakaian memori.

Dengan melihat kekurangan dari penyimpanan data statik ini dapat ditarik kesimpulan bahwa penggunaan penyimpanan data secara statik ini sangat tidak bagus untuk kasus dimana data masukan berbeda tipenya dan tidak diketahui jumlah maksimum data yang akan ditampung.

Sehingga kita akan mengalami kesulitan dalam mendeklarasikan tabel kontigu yang dapat menampung data masukan yang masih belum diketahui secara jelas dan bisa bermacam-macam jenisnya.

Gambar 1. Tabel Kontigu Kosong

Gambar 2. Tabel Kontigu Terisi Sebagian

Gambar 3. Tabel Kontigu Terisi Penuh

Tentunya dari penjelasan tadi kita dapat mengetahui kasus apa yang cocok untuk memakai penyimpanan data statik ini.

Ya, penyimpanan data statik ini sangat cocok dipakai untuk data yang statik yang tidak akan diubah-ubah dan hanya digunakan sebagai resource data. Misalnya untuk sebuah database yang tidak akan diubah nilainya dan hanya untuk dipakai saja pada proses-proses lainnya. ²

2.2 Penyimpanan Data Dinamik

Penyimpanan data secara dinamik lebih banyak dipakai daripada penyimpanan data statik karena kasus yang lebih baik menggunakan penyimpanan data dinamik ini jauh lebih banyak daripada penyimpanan data statik. Hal ini dikarenakan pada penyimpanan data dinamik mempunyai beberapa keunggulan yang sangat kontras dibanding penyimpanan data statik antara lain :

1.      Pada penyimpanan data dinamik pemesanan memori hanya dilakukan saat ada data masukan yang baru atau dengan kata lain program tidak akan meminta memori pada komputer apabila tidak ada data masukan sehingga untuk data kosong tidak akan memakai memori sama sekali

2.      Tipe setiap elemen dapat diatur sedemikian sehingga tipe data setiap elemennya dapat berbeda-beda.

Penyimpanan data secara dinamik ini umumnya diimplementasikan dengan senarai berkait (linked list). Dimana sebuah list itu mempunyai sebuah penunjuk elemen pertama (First) list yang dijadikan sebagai acuan sebuah list tersebut kosong atau berisi. ²

Berikut ini gambar dari kondisi list yang terisi dan kosong :

Gambar 4. Senarai Berkait dengan 3 elemen

Gambar 5. Senarai Berkait Kosong

Namun implementasi dengan senarai berkait ini memiliki kekurangan dimana untuk operasi pencarian, penambahan, dan penghapusan data kita harus menelusuri elemennya dari elemen pertama. Untuk program yang berskala menengah kebawah mungkin ini bukan menjadi suatu permasalahan yang genting. Namun untuk suatu program atau software yang berskala besar yang membutuhkan kecepatan eksekusi (run-time) yang tinggi untuk setiap perintah-perintah yang ada, hal ini tentunya merupakan suatu permasalahan yang harus dipandang serius. Karena untuk program skala besar ini kompleksitas algoritma sangatmemegang peran penting dalam kecepatan eksekusi. Untuk itu diperlukan suatu cara baru untuk mengimplementasikan penyimpanan data dinamik dengan kecepatan eksekusi yang tinggi. Disinilah peran penting penerepan teori pohon pada kajian struktur data sangat terasa efeknya. Penerapan teori pohon yang dimaksud adalah konsep Binary Search Tree yang memberikan kecepatan eksekusi yang lebih tinggi dari pada implementasi senarai berkait terutama pada operasi pencarian, penambahan, dan penghapusan data. Namun selain konsep Binary Search Tree masih banyak lagi implementasi penerapan teori pohon yang merupakan pilihan struktur penyimpanan data yang merupakan solusi dari masalah-masalah yang dihadapi dii bidang informatika saat ini antara lain AVL-tree, Splay-tree, Lexicographic Search Tree / tries , External Search Tree / B-tree, dsb. ³

BAB III

IMPLEMENTASI TEORI POHON

3. Implementasi Teori Pohon

Implementasi teori pohon merupakan salah satu pilihan struktur data terbaik yang pernah ada dan masing-masing implementasi tersebut tentunya merupakan pilihan terbaik untuk kasus-kasus tertentu. Berikut beberapa contoh implementasi dari teori pohon :

1.      Binary Search Tree

2.      AVL-Tree (The Height Balance Tree)

3.      Splay-Tree (The Self-Adjusting Tree)

3.1 Binary Search Tree

3.1.1 Gambaran Permasalahan

Bayangkan apabila kita ingin mencari sebuah data pada sebuah senarai berkait, tentunya tidak ada cara selain mencarinya secara sekuensial dari pointer elemen pertama senarai. Bandingkan jika kita melakukan pencarian di tabel kontigu dan dengan pencarian biner (binary search), tentunya pencarian akan lebih cepat.Dan sekarang

bayangkan  jika  kita  ingin  melakukan  operasi penambahan dan penghapusan elemen senarai. Operasi tersebut akan lebih lambat pada table kontigu daripada senarai       berkait.           Hal ini disebabkan karena       operasi penambahan dan penghapusan  pada  tabel  kontigu  memerlukan pemindahan        banyak entri data setiap saat,dibandingkan dengan senarai berkait yang hanyamembutuhkan sedikit permainan pointer. ³Dari  permasalahan  diatas  tentunya  dapat  kita simpulkan  bahwa  alangkah  baiknya  jika  kitadapat melakukan operasi pencarian dengan kecepatan eksekusi tinggi(seperti pada table kontigu dan pencarian biner)   dan operasi

penambahan dan penghapusan dengan kecepatan eksekusi tinggi (seperti pada senarai berkait). Disinilah keunggulan Binary Search Tree akan sangat berguna, dimana Binary Search Tree dapat menjadi solusi permasalahan tersebut karena pencarian serta penambahan dan penghapusan elemennya memiliki kecepatan eksekusi yang tinggi. Operasi pencarian, penambahan, dan penghapusan pada Binary Search Tree memiliki run-time O (log n). ³

3.1.2 Definisi Binary Search Tree

Binary Search Tree adalah sebuah pohon biner yang mempunyai properti tambahan. Properti ini adalah :

1.   Semua elemen pada upapohon (subpohon) kiri nilainya lebih kecil atau sama dengan nilai akar.

2.      Semua elemen pada upapohon kanan nilainya lebih besar dari nilai akar.

3.      Upapohon kiri dan kanan merupakan Binary Search Tree. ⁶

Gambar 6. Contoh Binary Search Tree 3.1.3 Operasi Pada Binary Search Tree

Terdapat 3 operasi yang sangat mendasar dan juga sangat penting pada binary search tree yaitu operasi pencarian, penambahan, dan penghapusan elemen. Ketiga operasi tersebut merupakan operasi yang sangat mendasar yang harus ada pada setiap struktur penyimpanan data.

3.1.3.1 Operasi Pencarian

Untuk melakukan operasi pencarian pada Binary Search Tree, pertama-tama kita bandingkan

dahulu kunci data yang ingin kita cari dengan kunci dari data akar, jika tidak cocok maka cari pada upapohon kiri atau kanan sampai kunci data yang ingin dicari cocok.³

Berikut sketsa kasar algoritma operasi pencarian pada Binary Search Tree :

Algoritma Cari Simpul (kunci K, pohon P) ⁷

1.      Jika pohon P kosong kembalikan nilai NULL (tak terdefinisi)

2.      Jika kunci K cocok dengan kunci akar t maka kembalikan simpul P

3.      Jika kunci K > kunci akar simpul P

maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kanan (P) )

Jika kunci K <= kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kiri(P)

3.1.3.2 Operasi Penambahan Elemen

Dalam penambahan elemen pada Binary Search Tree, terdapat 2 kasus yang harus kita perhatikan yaitu penambahan ke pohon kosong dan penambahan ke pohon pencarian biner (Binary Search Tree) yang sudah terisi. Penambahan ke pohon kosong tentunya cukup mudah, sedangkan untuk penambahan ke Binary Search Tree yang sudah terisi maka kita harus membandingkannya dengan kunci dari akar pohon yang bersangkutan. Jika kuncinya lebih kecil maka tambahkan simpul baru ke upapohon kiri, jika lebih besar maka tambahkan ke upapohon kanan, dan jika kunci nya sama atau simpul dengan kunci yang ingin ditambahkan sudah ada, maka tidak akan melakukan apa-apa.³

Berikut sketsa kasar penambahan elemen pada

Binary Search Tree :

Algoritma Insert (kunci K, pohon P) ⁷

1.      Jika pohon P kosong maka kembalikan pohon baru dengan kunci akar = K <basis 0>

2.      Jika kunci akar P = K, kembalikan P (tanpa diubah)

3.      Jika kunci K > kunci akar P,maka Insert (kunci K, upapohon kanan(P) )

4.      Jika kunci K < kunci akar P, maka Insert (kunci K, upapohon kiri(P) )

Gambar 7. Operasi Penambahan Elemen pada Binary Search Tree

3.1.3.3 Operasi Penghapusan Elemen

Penghapusan elemen pada Binary Search Tree merupakan operasi yang paling kompleks dari ketiga operasi ini. Dalam penghapusan elemen ini ada 3 kasus yang harus kita perhatikan, antara lain :

1.      Menghapus daun : menghapus simpul yang tidak mempunyai upapohon.

2.      Menghapus simpul yang mempunyai sebuah

upapohon             kiri/kanan              :

hapus dan gantikan dengan upapohonnya

3.      Menghapus simpul yang mempunyai 2 upapohon : timpa simpul yang ingin dihapus dengan simpul yang mempunyai kunci terbesar pada upapohon kiri

Gambar 8. Operasi Penghapusan Elemen

Pada Binary Search Tree

Berikut sketsa kasar penghapusan elemen pada

Binary Search Tree :

Algoritma DelNode(kunci K, pohon P) ⁵

1.      Cari simpul yang mengandung kunci K

2.      Jika simpul dengan kunci K ketemu maka :

2.1. Jika upapohon kiri kosong maka tukar simpul P dengan upapohon kanan P, lalu hapus simpul yang sudah ditukar tersebut

2.2. Jika upapohon kanan kosong maka tukar simpul P dengan upapohon kiri P, lalu hapus simpul yang sudah ditukar tersebut

3.2 AVL-Tree

Kebanyakan aplikasi saat ini melakukan operasi penambahan dan penghapusan elemen secara terus -menerus tanpa urutan yang jelas urutannya. Oleh karena itu sangatlah penting untuk mengoptimasi waktu pencarian dengan menjaga agar pohon tersebut mendekati seimbang sepanjang waktu. Dan hal ini telah diwujudkan oleh 2 orang matematikawan Russia ,

G.M. Adel’son-Vel’skii dan E.M. Landis. Oleh karena itu Binary Search Tree ini disebut AVL-tree yang diambil dari nama kedua matematikawan Russia tersebut.[3]

Tujuan utama dari pembuatan AVL-Tree ini adalah agar operasi pencarian, penambahan, dan penghapusan elemen dapat dilakukan dalam waktu O(log n) bahkan untuk kasus terburuk pun. Tidak seperti Binary Search Tree biasa yang dapat mencapai waktu O(1.44 log n) untuk kasus terburuk. ³

3.2.1 Definisi AVL-Tree

Dalam pohon yang benar-benar seimbang, upapohon kiri dan kanan dari setiap simpul mempunyai tinggi yang sama. Walaupun kita tidak dapat mencapai tujuan ini secara sempurna, setidaknya dengan membangun Binary Search Tree dengan metode penambahan elemen yang nantinya akan kita bahas, kita dapat meyakinkan bahwa setiap upapohon kiri dan kanan tidak akan pernah berselisih lebih dari 1.

Jadi, sebuah AVL-Tree merupakan Binary Search Tree yang upapohon kiri dan kanan dari akarnya tidak akan berselisih lebih dari 1 dan setiap upapohon dari AVL-Tree juga merupakan AVL-Tree. Dan setiap simpul di AVL-Tree mempunyai faktor penyeimbang (balance factor) yang bernilai left- higher (upapohon kiri > kanan), equal-height (upapohon kiri = kanan), right-higher (upapohon kiri < kanan). ^3,4

3.2.2 Operasi Pada AVL-Tree

Operasi yang akan kita bahas ini adalah operasi yang sangat mendasar yaitu operasi pencarian, penambahan, dan penghapusan elemen.

3.2.2.1 Operasi Pencarian Elemen

Operasi pencarian elemen pada AVL-Tree relatif sama dengan operasi pencarian elemen pada binary search tree. Hal ini tentunya karena AVL-Tree itu sendiri merupakan binary search tree yang sedikit dimodifikasi dengan menambah properti khusus yaitu keseimbangan pohon.

3.2.2.2 Operasi Penambahan Elemen

Karena AVL-Tree ini juga merupakan binary search tree maka penambahan elemen pada AVL-Tree ini juga dapat kita lakukan dengan metode yang sama dengan binary search tree. Pada kebanyakan kasus, penambahan elemen itu sering sekali tidak membuat tinggi dari upapohonnya meningkat sedemikian sehingga dapat membuat selisih tinggi dari upapohon kiri dan kanan lebih dari 1. Namun, bukan tidak mungkin hal ini bisa terjadi. Satu-satunya kasus dimana masalah ini muncul adalah ketika simpul baru itu ditambahkan ke upapohon yang lebih tinggi dari upapohon lainnya sehingga tinggi nya akan bertambah dan membuat selisih tinggi nya menjadi lebih dari 1. ³

Berikut gambar contoh penambahan simpul sederhana, kita menggunakan ‘/’ sebagai tanda bahwa faktor penyeimbang bernilai left-higher, ‘-‘ untuk equal-height dan ‘\’ untuk right-higher.

Gambar 9. Penambahan Elemen Pada AVL-Tree yang Sederhana

Sekarang mari kita tinjau masalah dimana penambahan elemen tersebut akan membuat AVL-Tree tidak lagi memenuhi syarat sebuah AVL-Tree. Solusi yang ditawarkan untuk menyelesaikan masalah ini adalah dengan merotasi upapohon tersebut sedemikian sehinggaselisih tinggi setiap upapohon nya tidak lebih dari 1. Lebih jelasnya lagi, mari kita asumsikan kita telah menambahkan simpul baru sehingga selisih tinggi setiap upapohonnya lebih dari 1. Ada 3 kasus yang muncul pada keadaan ini yakni:

1.                  Upapohon kanan lebih tinggiYang harus kita lakukan adalah merotasi kiri / left rotation (seperti pada gambar.10) yaitu merotasi right_tree tersebut ke root dan menjadikan root tersebut menjadi upapohon kiri dari right_ tree. Lalu T2 dijadikan upapohon kanan dari root.

Gambar 10a. Penyeimbangan AVL-Tree dengan Merotasi kiri (Left Rotation)

2.                  Upapohon kiri lebih tinggi

Pada kasus kedua ini permasalahannya sedikit lebih rumit dimana kita harus memindahkan nya sejauh 2 tingkat ke simpul sub_tree (seperti pada gambar.11). Proses ini disebut rotasi ganda / double rotation karena transformasi dilakukan dalam 2 tahap. Pertama rotasi sub_tree ke right_tree sedemikian sehingga right_tree menjadi

upapohon kanan dari sub_tree dan upapohon kanan sub_tree sebelumnya menjadi upapohon kiri right_tree. Lalu rotasi sub_tree ke root sedemikian sehingga root menjadi upapohon kiri dari sub_tree dan upapohon kiri sub_tree yang sebelumnya menjadi upapohon kanan dari root.

Gambar 10b. Penyeimbangan AVL-Tree dengan Merotasi ganda (double Rotation)

Gambar 11. Penambahan AVL-Tree dengan Rotasi

3.2.2.3 Operasi Penghapusan Elemen

Pada operasi penghapusan elemen AVL-Tree kita akan menggunakan ide dasar yang sama dengan penambahan elemen, seperti memakai rotasi tunggal dan ganda. ³

Berikut metode penghapusan elemen AVL-Tree :

-    Isolasi masalah sedemikian sehingga kita sampai pada kasus dimana simpul x yang ingin dihapus paling banyak mempunyai 1 anak. Jika x mempunyai 2 anak, cari simpul y yang merupakan predecessor x dan tidak mempunyai upapohon kanan. Letakkan y keposisi x

-    Hapus simpul x, dari yang kita ketahui di tahap pertama tadi bahwa x maksimal memiliki 1 anak, sehingga kita tinggal menghapusnya dan memindahkan upapohonnya keposisi x. Namun kita harus memperhatikan efek yang ditimbulkan dari penghapusan x pada simpul-simpul sebelum x. Untuk itu kita pakai sebuah variable boolean shorter untuk melihat apakah tinggi dari upapohon menjadi lebih kecil.

-    variabel shorter diinisialisasi true, berikut adalah kasus-kasus yang harus ditangani untuk setiap simpul p yang merupakan simpul yang terdapat diantara akar pohon sampai x. Dan kasus-kasus berikut hanya akan ditangani jika variabel shorter masih bernilai true, dan jika nilainya sudah false maka algoritma diterminasi.

-    kasus 1 : simpul p mempunyai faktor penyeimbang equal-height, ubah faktor penyeimbangnya sesuai upapohon kiri atau kanan yang memendek, dan shorter menjadi false

kasus 2 : faktor penyeimbang p bukan equal-height, dan upapohon yang diperpendek adalah upapohon yang lebih tinggi, maka ubah faktor penyeimbang menjadi equal-height , dan shorter tetap bernilai true.

-  kasus 3 : faktor penyeimbang p bukan equal-height, dan upapohon yang diperpendek adalah upapohon yang lebih pendek. Maka syarat sebuah AVL-Tree tentunya telah dilanggar, dengan demikian kita harus melakukan rotasi untuk menyeimbangkan kembali AVL-Tree. Ambil q sebagai akar dari upapohon yang lebih tinggi dari p (yang tidak diperpendek). Dari sini kita mempunyai 3kasus berdasarkan faktor penyeimbang dari q, yakni :

a.       Faktor penyeimbang q equal-height, lakukan rotasi tunggal dan shorter menjadi false.

b.      Faktor penyeimbang q sama dengan faktor penyeimbang p, lakukan rotasi tunggal ubah faktor penyeimbang p dan q menjadi equal-height dan shorter tetap bernilai true.

c.       Faktor penyeimbang q berkebalikan dengan faktor penyeimbang p, lakukan rotasi ganda (pertama lakukan rotasi q dan sekitarnya lalu rotasi pada p dan sekitarnya ), ubah nilai faktor penyeimbang menjadi equal-height dan faktor penyeimbang dari simpul lainnya sebagaimana mestinya, dan nilai shorter tetap true.

Berikut ilustrasi penghapusan elemen pada AVL-

Gambar 12a. Ilustrasi Penghapusan Elemen AVL-Tree

PENUTUP

KESIMPULAN

Berdasarkan hal-hal diatas maka dapat diambil kesimpulan bahwa penerapan teori pohon sangatlah berguna dalam kajian struktur data dimana dengan teori pohon itu kita bisa mendapatkan struktur penyimpanan data alternatif yang relatif lebih baik dan efisien daripada struktur penyimpanan data lainnya, seperti representasi senarai berkait dan tabel kontigu misalnya.Terbukti bahwa representasi data dengan binary search tree jauh lebih baik daripada representasi data dengan tabel kontigu ataupun senarai berkait. Dan juga dapat kita tarik kesimpulan bahwa binary search tree sangat fleksibel dimana konsepnya ini masih dapat dikembangkan untuk menyelesaikan suatu permasalahan baru yang sekarang ini sudah umum ditemui.Modifikasi konsep binary search tree yang cukup terkenal yaitu AVL-Tree dan Splay Tree yang sangat efisien dalam menyelesaikan kasus-kasus tertentu.

DAFTAR PUSTAKA

[1]         Munir, Rinaldi (2005) Diktat Kuliah IF2153 Matematika Diskrit.

Program Studi Teknik Informatika, Institute Teknologi Bandung.

[2]         Liem, Inggriani (2005) Diktat Kuliah IF2182 Algoritma dan Struktur Data Program Studi Teknik Informatika Institute Teknologi Bandung.

[3]         Data Structure and Program Design in C++, Robert L. Kruse and Alexander J. Ryba

[4]         NIST.  (2004).  National  Institute  of

Standards and Technology. http://www.nist.gov/dads/HTML/binary SearchTree.html http://www.nist.gov/dads/HTML/avltree. html http://www.nist.gov/dads/HTML/splaytr ee.html

Tanggal akses: 20 Desember 2006 pukul 14:00