Leftist tree, Tries and Hashing

Leftist tree adalah sebuah implementasi dari tumpukan heap yang gunanya untuk menemukan elemen terkecil atau terbesar dari sebuah tree dan memudahkan penggabungan dari dua buah tree lalu mudah diimplementasikan dalam penggunaan linked list.

Binary tree dikatakan leftist tree jika pada setiap simpul internal nilai x  anak kiri lebih besar dari atau sama dengan nilai x dari anak kanan.

Combine 

Combine ini adalah merupakan operasi utama dari leftist tree dengan menggabungkan dua pohon (A dan B) menjadi satu tree kiri yang berisi elemen elemen dari pohon A dan B


Tries

Tries ini adalah tree yang berbentuk prepix yang gunanya seperti auto complete 

contoh gambar dari Tries : 

 


dari gambar di atas terdapat kata - kata :

1. KAN
2. KEY
3. KIND
4. KNIFE
5. KNOP
6. KOP

Nama : Setiawan Faisal.K

NIM  :1701307501

www.binus.ac.id || www.skyconnectiva.com

Heap

Secara umum heap ada 2 yaitu min heap dan max heap

*Min heap

Min heap adalah nilai parent harus lebih kecil dari nilai anak nya      
    

*Max heap

Max heap adalah nilai parent harus lebih besar dari nilau anak nya





Insertion

Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.


Deletion

Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.
Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

Nama : Setiawan Faisal.K

NIM  :1701307501

www.binus.ac.id || www.skyconnectiva.com

Red Black Tree (RBT)

RBT adalah sebuah binary search tree yang dimana setiap node nya memiliki warna merah atau hitam. Warna dari root selalu hitam dan warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut. Selain atribut yang dimiliki oleh BST, kita memerlukan persyaratan berikut untuk memnentukan.

Aturan pada Red Black Tree 

1. Setiap simpul/node adalah berwarna merah atau hitam

2. Akar selalu berwarna hitam

3. Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.

4. Jika node berwarna merah, anaknya harus berwarna hitam

5. Node berwarna merah secara berturut-turut tidak diperkenankan.

6. Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.

7. Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.

8. Node dibawah root yang berada pada level yang sama disebut sibling.


Insertion

Penyisipan dimulai dengan menambahkan node seperti penyisipan pohon pencarian biner dilakukan dan dengan mewarnai merah. Sedangkan dalam pohon pencarian biner, kita selalu menambahkan daun, merah-hitam daun pohon tidak mengandung informasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, di tempat yang ada daun hitam.

Apa yang terjadi berikutnya tergantung pada warna terdekat lain node. Paman (saudara parent) dalam istilah node akan digunakan untuk merujuk pada saudara kandung dari node orangtua, seperti dalam pohon keluarga manusia.
catatan :

Baik anak-anak dari setiap node merah hitam terancam hanya dengan menambahkan simpul merah, mengecat node hitam merah, atau rotasi.

Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam terancam hanya dengan menambahkan node hitam, mengecat simpul merah hitam, atau rotasi.


Delete

Menghapus sebuah node di RBT, hamper sama dengan menghapus node di BST ( Binary Search Tree) , jika sebuah node yang dihapus memiliki 2 anak, maka node yang dari anak kiri terbesar, atau anak kanan terkecil yang akan menggantikan si parent tersebut. Jika si parent berwarna merah dan anaknya merah, langsung digantikan dan tidak masalah, jika parent hitam dan anaknya merah, gantikan si parent dengan anaknya, lalu diwarna menjadi hitam, bagaimana jika kedua-duanya hitam? Jika keduanya hitam, gantikan si parent dengan anaknya, lalu rotasikan dan sesuaikan dengan treenya, sehingga tidak merusak aturan dalam RBT

Nama : Setiawan Faisal.K

NIM  :1701307501

www.binus.ac.id || www.skyconnectiva.com

Pertemuan 5


Stack and Implementation

Stack

Stack (tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack.

Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selsnjutnya meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring dari tumpukan tersebut, tentu yang diambil adalah piring teratas (yang terakhir kali ditaruh), bukan yang terbawah (yang pertama kali diletakkan). 

Didalam stack terdapat 2 istilah atau 2 variable yang digunakan yaitu TOP dan MAX yang dimana TOP adalah merupakan data yang paling atas dan MAX merupakan jumlah dari seluruh data yang ada 

Infix,Postfix dan Prefix

Infix      = a+b  (operator terletak di tengah tengah operand)

Postfix = +ab (operand terletak di depan operand )

Prefix   = ab+ (operand terletak di depan operator)

Depth First Search(DFS) dan Breath First Search(BFS)

Depth First Search

adalah sebuah pencarian uninformed yang berlangsung dengan memperluas simpul anak pertama dari pencarian pohon yang muncul dan dengan demikian akan semakin dalam sampai node tujuan ditemukan, atau sampai hits node yang tidak memiliki anak. Kemudian pencarian backtracks , kembali ke node terakhir kebanyakan belum selesai menjelajahi. Dalam implementasi non-rekursif, semua node yang baru diperluas ditambahkan ke stack untuk eksplorasi.

Breath First Search 

adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

contoh DFS dan BFS

DFS

BFS

nama : Setiawan Faisal.K

NIM  :1701307501

www.binus.ac.id || www.skyconnectiva.com

pertemuan 4



Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut root atau akar.

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

ada beberapa jenis dari binary tree yatu : 

a) Full Binary Treeb

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

      

b) Complete Binary Tree

    Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree

Skewdi Binary Tree adalah tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Rumus untuk mencari node pada tree :

- mengambil yang bagian kiri      = 2p+1

- mengambil yang bagian kana n = 2p+2

- mengambil parentnya               = (p-1)/2

Expresion Tree Concept

infix     = a + c * b (a+b)

postfix  =-a * cb (+ab)

prefix    =abc-* (ab+)

contoh soal  

c/a*2+3/12+21 tentukan infix, postfix dan prefix

infix     =c/a*2+3/12+21

postfix =++*/ca2/3 12 21

prefix   =21 3 12 /2ca/*++

Setiawan Faisal.K

1701307501

www.binus.ac.id || www.skyconnectiva.com

Sabtu 15-03-2014

Pertemuan 3 

Pada kelas besar kemaren kita kedatangan seorang pembicara Okky pribadi, s.kom dia merupakan lulusan binus yang ingin mengshare beberapa pengalaman dan mengajarkan sedikit materi tentang perbedaan Array dan Linked List.

            

Array

1. Bersifat statis

2. Setiap elemen pada array berisi data saja

3. Cara mengakses nya bersifat random acces

4. Penambahan dan penghapusan data terbatas tergantung jumlah memori yang di pesan

Linked List

1.Bersifat dinamis

2.Setiap elemen pada linked list berisi data dan pointer addres

3. Cara mengakses nya bersifat sequential acces

4. Penambahan dan penghapusan data tidak terbatas

Selebihnya kak Okky hanya bercerita tentang pengalaman pekerjaan nya sekarang ia bekerja sendiri sebagai progarmer seperti yang kak Okky bilang pekerjaan dia hanya mencari costumer yang ingin menggunakan jasa dia untuk membikin sebuah program lalu kak Okky bilang bahwa satu program yang sangat simpel saja ia jual dengan harga puluhan juta blom ditambah tiap bulan ia mengadakan maintance.Lalu kak Okky berkata jangan pernah menyesal untuk masuk ke jurusan teknik informatika karna prospek ke depan nya sangat menjamin.

Nama : Setiawan Faisal.K

NIM  : 1701307501

www.binus.edu || www.skyconnectiva.com

LINKED LIST IMPLEMENTATION I

Linked List atau kadang-kadang disebut dengan Senarai berantai dalam ilmu komputer merupakan sebuah struktur datayang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemendata yang tersimpan dalam senarai dilakukan secara lebih efektif.

Linked list di bagi menjadi 3 yaitu :

1. Single Linked List

2. Double Linked list

3. Circular Linked List

a. Single Linked List 

Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.

Contoh gambar single LL :

b. Double Linked List

Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.

Contoh gambar double LL:

c. Circular Linked List

Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih kosong,

Contoh Gambar Circular LL :

d. Push depan dan Push belakang

Di bagian ini biasa nya kita akan memakai 3 variable yaitu head, curr(current), dan tail dalam penggunaan LL biasanya dibagi menjadi 2 yaitu :
1. Push depan yaitu penambahan data yang dilakukan dibagian depan
2. Push belakang yaitu penambahan data yang dilakukan dibagian belakang

berikut contoh koding dari push depan dan push belakang :

*Push depan 

head=tail=curr;
if(head==NULL)
{
      head=tail=curr;
      tail => next = NULL
}
else
{
      curr => next = head;
      head = curr;
}


*Push belakang

head=tail=curr;
if(tail==NULL)
{
      head=tail=curr;
      tail => next = NULL
}
else
{
      tail => next = curr;
      tail = curr;
      tail => next = NULL;
}

e. POP(hapus)

POP(hapus) adalah cara untuk menghapus data dalam menggunakan LL, Pop terbagi menjadi 2 yaitu :
1.POP Depan yaitu menghapus data di bagian awal
2.POP Belakang yaitu menghapus data di bagian akhir

berikut contoh koding dari POP depan dan POP belakang :

*POP depan

void hapusDepan (){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}


*POP belakang

void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
if(head->next == head){
head = NULL;
}else{
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}

Nama  : Setiawan Faisal.K

Kelas : 02PFT

NIm   : 1701307501

www.skyconnectiva.com || www.binus.ac.id