31 - may 2016
HEAP

adalah salah satu binary complete tree dan harus memenuhi syarat berikut
min heap : Setiap node memiliki nilai lebih kecil dari anak nya
max heap : setiap node memiliki nilai lebih besar dari anak nya
min-max heap : root bernilai terkecil pada level ganjil nilainya selalu maximal sedangkan pada level genap nilainya selalu minimal


Min Heap :

Sehingga Root adalah nilai terkecil sedangkan nilai terbesar ada di Leaf-leaf
Heap dapat di aplikasikan di Linked list tapi lebih mudah kita membuat nya melalui Array

contoh :

Pada saat menginsert di Min-Max Heap kita harus ingat membandingkan nya hanya pada level yang sesama seperti genap dengan genap - ganjil dengan ganjil

heap di gunakan atau di aplikasikan di
  - Priority Queue
  - Selection Algorithm (find min/max, median, k-th largest, dll)
  - Dijkstra's Algorithm (find shortest path pada graph)
  - Prim Algorithm (find min spanning tree)

Hubungan antara Node :
Parent X = X / 2
Left Child X = 2*X
Right Child X = 2*X+1

Insertion
-Masukan node yang ingin dimasuki ke node paling terakhir di masukan
-bandingkan dengan parent nya jika dia lebih kecil dari parent nya maka tukar dengan parent tersebut
 jika memang nilai tersebut dapat di bandingkan terus maka dia dapat mencapai root



Deletion
delete root
-Nilai root di ganti dengan elemen yang terakhir dimasukan
-cocokan nilai yang di pindahkan itu dengan  nilai child left & right
-jika lebih besar nilai nya maka kita dapat memindahkan itu ke child nya kemudian dapat di check lagi jika dia masih punya child berikut nya








Tries

Struktur data tree yang digunakan untuk menyimpan sebuah string
di ambil dari kata retrieval 
karena kita dapat mencari yang kita inginkan cukup dengan menulis beberapa huruf saja





Jika anda liat di atas saat  anda memilih A makanya akan bsa menjadi ALGO / API
dan jika anda memilih B maka perlu di tambahkan O untuk mendapat BOM / BOSAN / BOR

Hashing
adalah transformasi daripada suatu string dengan mengambil karakter terdepan dan

mengubahnya menjadi value atau key yang mewakili suatu string. Digunakan di database untuk

mengindex
contoh:

Cara cara untuk memasukan string ke table:
- Mid Square
- Division
- Folding
Jika suatu string mirip dengan string lainnya (misal char dengan charm) dan menghasilkan index
yang sama, maka akan terjadi collision, untuk mengatasinya maka ada beberapa metode:
- Linear Probing – dengan menstore string ke index setelahnya misal Char - Charm char berlokasi di index 2 lalu charm akan berada di index ke 3
- Chaining – dengan menstore string dalam suatu ( Char -> Charm )chain menggunakan linked list.

Pertemuan 7

Nama : Emilio Joshua Adiputra

NIM : 1901460171

Red Black Tree 

Adalah sebuah binary search tree dimana tiap node diberi warna hitam dan merah

dan juga red black tree adalah salah satu cara self balance tree

Aturan Red black tree adalah :

-Setiap node adalah berwarna merah atau hitam 

-Akar/Root selalu berwarna hitam
- Node yang baru dimasukan itu harus berwarna merah
-  Jika node berwarna merah, anaknya harus berwarna hitam 
-Node berwarna merah secara berturut-turut tidak diperbolehkan. 
 Salah Satu Contoh Red Black Tree :

 
NIL di gambar adalah external node dimana itu tidak ada di tree yang sebenarnya hanya untuk membantu jika ada node baru yang masuk maka NIL yang akan di ganti
 
1. Insertion 

 

yang di input adalah X : tidak terjadi masalah maka tree masih dalam kondisi "Balance"

  
Uncle dan parent yang di input adalah X itu berwarnah merah kita dapat mengubah parent dan uncle yang di input menjadi hitam untuk membalancekan kembali

 
 Seperti syarat red black tree dimana tidak boleh merah bertemu merah maka ini tidak berkondisi balance sehingga kita perlu rotasikan 
gambar di atas adalah cara untuk membalancekan dengan cara single rotation

Left - Left rotation : Y yaitu parent dari X menjadi parent X dan Z lalu X dan Z menjadi merah dan Y sendiri dari awal nya merah menjadi Hitam lalu C menjadi anak nya Z
Right- Right rotation : Y yaitu parent dari Z menjadi parent X dan Z lalu X dan Z menjadi merah dan Y sendiri dari awal nya merah menjadi Hitam lalu B menjadi anak nya X

 
 Ini adalah cara dengan Double Rotation

Left Right Rotation  : Y menjadi  parent dari X dan Z lalu B di berikan ke X dan C diberikan ke Z
setelah itu ubah parent yaitu Y menjadi Hitam dan anak nya menjadi merah
Right left Rotation :  Y menjadi  parent dari X dan Z lalu B di berikan ke X dan C diberikan ke Z
setelah itu ubah parent yaitu Y menjadi Hitam dan anak nya menjadi merah

2. Deletion
Syarat-syarat 
-Bila yang mau dihapus punya 2 anak carilah successor dari elemen paling besar di kiri atau elemen paling kecil di kanan tergantung dari cara anda
-Bila node yang mau dihapus berwarna merah, langsung dapat diganti dengan anaknya yang berwarna hitam.
-Bila node yang mau dihapus berwarna hitam & anaknya merah, gantilah dengan anaknya lalu ubah warna anaknya menjadi hitam. 
-Bila yang mau di hapus dan anak nya berwarna hitam diperlukan perlakuan khusus:

• Ganti node yang mau dihapus dengan anaknya.

• Bila sibling berwarna merah, tukar warna sibling dan parent, lalu lakukan rotasi seperti berikut

• 

•  Bila sibling berwarna hitam dan keduanya anaknya juga hitam, maka cukup mengubah warna sibling tersebut menjadi warna merah

•  

• Bila sibling merah dan ada anaknya yang berwarna merah (salah satu saja), maka lakukan rotasi seperti berikut
•  

 2-3 Tree

2-3 tree BUKAN sebuah Binary Tree
salah satu struktur data dimana node mempunyai anak
jika anak nya 2 maka setiap anak mempunyai 1 data
sedangkan jika anak nya 3 setiap anak mempunyai maksimal 2 data




Aturan 2-3 Tree :

• Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak tengah). Sebuah 3-node berisi dua item data dan memiliki 3 anak/children (anak kiri, tengah, dan kanan).
• Semua leaf harus berada dilevel yang sama
• Semua data yang disimpan akan diurutkan kekiri adalah lebih kecil dari root dan kekanan lebih besar dari root 

Contoh Insertion
 
memasukan 45 cukup memasukan saja karena masih memiliki tempat untuk 45 tersebut sehingga tidak ada masalah
 
jika yang di masukan seperti 75 maka nilai dari 80 90 diperbandingkan dengan 75 lalu nilai tengah nya apa.. di sini adalah 80 
 
lalu 80 naik ke atas dan 75 dan 90 berpisah menjadi node sendiri - sendiri
 
24 langsung ke atas dan 23 berpisah dengan 25 menjadi node- node sendiri  
 










 di atas pun 24 tetap nilai tengah sehingga 24 berpindah ke atas di sebelah 50




lalu kita perlu memisahkan 20 dan 30 menjadi node node sendiri dan tadikan ada 4 node yang berlokasi sebagai anak 20 | 30 maka yang di bagian kiri menjadi milik 20 lalu yang di bagian kanan menajdi milik 30

Deletion 2-3 Tree
 -Jika leaf-nya sudah 3-node, maka kita tinggal menghapus saja data tersebut dan menjadikannya      
     2-node.
-Jika leaf-nya adalah 2-node :

• Jika parent-nya 3-node, maka ambil 1 nilai dari 3-node tersebut. Jika Sibling/Saudaranya adalah 3-node, maka push nilai tersebut dari sibling ke parent untuk membuat parent menjadi 3-node lagi. Jika sibling adalah 2-node, buat parent menjadi 2-node dan gabungkan node dengan sibling-nya.
• Jika parent-nya 2-node, Jika sibling-nya adalah 3-node, maka ambil satu nilai dari parent dan push satu nilai dari sibling ke parent-nya sendiri. Hal lainnya yaitu mengabungkan parent dengan sibling.

 23 ingin di hapus lalu karena itu adalah 3 node maka menghapus 23 tidak terjadi masalah



50 ingin di hapus maka kita mencari element terkanan dari node kiri 50 dihapus lalu 40 berpindah ke 40 lalu lokasi 40 sebelum nya di 3 node menjadi kosong


di sini kita perlu menurunkan 30 ke anak nya di bagian paling besar supaya yang tadi nya bertotal 3 node anak menjadi 2 node anak saja sehingga menjadi seperti ini

16 May 2016
emilio joshua - 1901460171 
Pertemuan Ke 6 - AVL Tree
Guest Lecturer - Selvakumar Man Ickam
website untuk latihan AVL Tree
http://visualgo.net/bst

Tree adalah data structure yang tidak linear yang menghubungkan data-data dengan sebuah garis kebawah nya
dimana garis tersebut dinamakan Edges
sedangkan data-data nya di sebut dengan vertices

Tree yang akan kita pelajari sekarang adalah AVL tree

AVL tree adalah cara untuk membuat tree tersebut menjadi "balance tree"

AVL ditemukan oleh Georgy Adelson-Velsky dan Evgenii Landis .


AVL tree adalah salah satu jenis tree yang berasal dari BST,
akan tetapi AVL dapat membuat  hasil tree yang seimbang

Salah satu contoh tree tidak seimbang

untuk mengetahui nilai yang hitam
nilai yang hitam adalah nilai dari vertice terjauh dan paling bawah lalu semakin ke atas maka nilai tersebut semakin tinggi
jika ada anak nya yang lain yang lebih pendek maka anak yang paling jauh lah yang di hitung untuk nilai teratas
lalu untuk nilai yang merah
nilai merah berasal dari nilai hitam kiri - nilai hitam kanan dan merah tersebut dimasukan ke "bapak" nya
jika yang merah bernilai lebih dari 1 maka kita dapat menyebutkan tree tersebut memiliki ketidak seimbangan
leaf nilai hitam nya selalu 1.

untuk double rotation dan proses nya

untuk single rotation dan prosesnya
Left Left rotation

Right Right rotation