Pertemuan Kedelapan Head dan Tries

Heap

Heap adalah suatu Binary Tree lengkap yang menggunakan persyaratan Heap. Di dalam heap terdapat dua tipe heap yaitu Min Heap dan Max Heap. Min Heap adalah sebuah Binary Tree dimana root dari tree tersebut adalah angka terkecil atau memiliki nilai terkecil dibandingkan seluruh node didalam tree tersebut sedangkan Max Heap adalah sebaliknya yaitu Binary Tree dimana root dari tree tersebut adalah angka terbesar dari tree tersebut.

Berikut adalah contoh dari Min Heap dan Max Heap:

Min Heap

Aturan dalam membuat Min Heap:
1. Value dari suatu parent harus lebih kecil dari value anaknya
2. Root dari tree adalah value terkecil yang ada didalam tree
3. Value terbesar terdapat di salah satu node leaf
 

Max Heap

Aturan dalam membuat Max Heap:
1. Value dari suatu parent harus lebih besar dari value anaknya
2. Root dari tree adalah value terbesar yang ada didalam tree
3. Value terkecil terdapat di salah satu node leaf


Min-Max Heap

Min-Max Heap adalah gabungan dari Min Heap dan Max Heap. Karena Min-Max Heap adalah gabungan dari Min dan Max Heap maka aturan dari kedua heap  tersebut disatukan menjadi seperti berikut:

1. Root menggunakan aturan Min Heap.
2. Setiap node yang memiliki height ganjil mengikuti aturan Min Heap.
3. Setiap node yang memiliki height genap mengkuti atuan Max Heap.





Tries

Tries adalah Binary Tree dimana isi dari tersebut adalah kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).

Pertemuan Ketujuh Red Black Tree dan 2-3 Tree

Red Black Tree

Red Black Tree adalah bentuk kembangan dari Binary Search Tree. Red Black Tree seperti namanya didalam tree terdapat dua macam node yaitu node merah dan node hitam. Didalam Red Black Tree terdapat satu nama baru yaitu Uncle. Uncle ini adalah suatu node yang berdada pada baris yang sama dengan parent dari tree tertentu. Red Black Tree juga memiliki beberapa ciri-ciri yang membedakannya dari AVL Tree, yaitu:

- Root selalu berwarna hitam; misal berubah warna menjadi merah tetap dihitamkan
- Node yang baru dimasukkan harus berwarna merah
- Node merah memiliki dua anak yaitu node berwarna hitam
- Memiliki external node yang berwarna hitam

Didalam Red Black Tree terdapat dua proses yang dapat dilakukan, yaitu:

Insertion

 Cara Insert di Red Black Tree mirip seperti pada Binary Search Tree tetapi ada peraturan baru yaitu, jika Parent berwarna merah, anaknya tidak boleh merah.

Berikut adalah cara menyelesaikan masalah jika 2 node merah bertemu:


Caranya pertama adalah melihat uncle dari node tersebut. Jika uncle dari node tersebut berwarna merah maka hitamkan uncle dan parent dari node tersebut. Sedangkan jika unclenya berwarna hitam maka lakukan proses berikut:






Deletion


Cara deletion pada Red Black Tree juga sama seperti BST tetapi karena ada peraturan khusus dari Red Black Tree maka jika terjadi kesalahan harus diubah. Berikut adalah kemungkinan yang mungkin terjadi saat deletion :

- Node yang di delete berwarna merah dan merupakan node leaf. Maka langsung saja hapus node tersebut

- Terjadi double black dimana sibling dari node tersebut berwarna merah. Maka berikut adalah proses yang dilakukan:



- Terjadi double black dimana sibling berwarna hitam. Maka berikut adalh proses yang dilakukan:



- Terjadi double black dimana sibling hitam dan anak dari node sibling berwarana merah. Maka berikut adalah proses yang dilakukan:



2-3 Tree

2-3 Tree adalh BST yang memiliki node yang berbeda. Berikut adalah contoh dari 2-3 Tree:



Didalam 2-3 Tree terdapat beberapa peraturan yang dapat membentuk 2-3 Tree yaitu:
- Root lepas dari aturan
- Jika parent terdapat n value maka anaknya harus berjumlah n+1
- Didalam deletion jika terbentuk jumlah value pada node yang berjumlah ganjil maka node yang memiliki value ditengah akan dilempar ke atas.
- Dan masih banyak lagi.

PERTEMUAN KEENAM BALANCED BINARY SEARCH TREE (pt.1)

Balanced Binary Search Tree adalah BST yang diperpendek dengan tujuan untuk mempermudah pencarian sebuah node dalam tree. Balanced Binary Search Tree berasal dari dua buah metode yaitu AVL Tree dan Red Black Tree.

AVL Tree


AVL Tree adalah tree yang dibuat oleh G.M. Adelson-Veleski dan E.M. Landis pada tahun 1962. AVL Tree digunakan untuk mempermudah pembuatan balanced Balanced Binary Search Tree. Berikut adalah contoh dari sebuah AVL Tree Concept :



Didalam AVL Tree terdapat tiga proses yang dapat dilakukan, yaitu:

Insertion

Sama pada seperti cara insertion pada Binary Search Tree tetapi bentuk dari tree harus tetap balance. 

Single Rotation & Double Rotation

Single Rotation adalah proses dimana hanya terjadi suatu pertukaran node, biasanya proses ini juga disebut sebagai left left case atau right right case. Sedangkan Double Rotation adalah proses dimana terjadi dua kali pertukaran node, biasanya awal dari proses ini disebut left right case atau right left case.

Yang menentukan proses-proses ini adalah jumlah dari balance factor suatu node. Balance factor suatu node dapat ditentukan dari hasil pengurangan height node anak dari suatu node (Height anak yang nilainya lebih besar - nilainya lebih kecil). Jika hasil tersebut lebih dari 1 maka terjadi sebuah kesalahan dan harus dilakukan single atau double rotation tergantung dari dimana kesalahan tersebut dimulai.

Berikut adalah cara melakukan double rotation dan single rotation pada Balanced Binary Search Tree