Leftist Tree

 Pengertian Leftist Tree

Beberapa hal yang perlu diketahui tentang Leftist Tree:

•Leftist Tree : variasi dari heap yang dapat mencari nilai max atau min

•Leftist Tree berguna ketika kita ingin menggabungkan 2 heap menjadi satu

•Leftist Tree lebih mudah diimplementasikan menggunakan link list (selama bukan complete
                 binary tree)

Pada Leftist Tree juga mempunyai external node (yaitu node yang menggantikan node kosong). Lalu  terdapat S(x) yang merupakan path terpendek untuk mencapai external node.

Berikut adalah contoh Extended Binary Tree:

*catatan = Node merah adalah External Node 

Pada Leftist Tree, path anak kiri >= dari path anak kanan. Terdapat 2 jenis Leftist Tree:

1. Min Leftist Tree : Setiap Node lebih kecil dari Childnya

2. Max Leftist Tree : Setiap Node lebih besar dari Childnya

Berikut adalah contoh Leftist Tree:

*Angka hijau adalah S(x) = Path Terpendek 

Operasi : Combine

 1. Menggabungkan 2 Leftist Tree
 2. Dapat dipakai untuk insert dan delete

 Contoh combinasi 2 Leftist Tree

1. Misalkan kita ingin menggabungkan Min Leftist Tree A dan Tree B.
2. Bandingkan Root A dan B. Root yang paling kecil (nilainya) akan menjadi Root dari Tree gabungan. Lalu pecah anak kanan dari Root, dan bandingkan dengan Root Tree yang satu lagi. Nilai yang lebih kecil akan menjadi anak kanan Root Tree Gabungan. Lakukan terus hingga selesai.
3. Update nilai S(x) / Path terpendek.
4. Pindahkan Node dengan S(x) lebih besar ke kiri (Left-Most)

Untuk mempermudah mari kita lihat contoh berikut:
Step 1:
*Terdapat 2 Node yang ingin digabungkan
Step 2:

*2 < 5. Maka 2 menjadi root dari Tree Gabungan.
                                                                  Anak kanan (50) pecah.
Step 3:

*5 menjadi anak kanan dari Root (2)
Step 4:
*Bandingkan 8 dan 50. Nilai 8 < 50, Maka 8 
                                                                         tetap menjadi tangan kanan 5 dan 50 menjadi
                                                                         tangan kanan 8
Step 5:
*Setelah digabung, hitung kembali S(x), maka akan menjadi
                                                          right-most path.
 Step 6:
  *Perbaiki Node 8, geser ke kiri satu kali.
Step 7:
*Geser juga Node 5 ke kiri, dan pisah kan Node 7 menjadi
                                                                  tangan kanan dari Node 2 / Root
 Step 8:
  *Maka terbentuklah Min Leftist Tree.

Insertion pada Leftist Tree:
1. Buat Leftist Tree dengan 1 Node.
2. Kombinasi dengan Leftist Tree awal (utama)

Deletion pada Leftist Tree:
1. Delete Root.
2. Kombinasi Left-Child dengan Right-Child dari Root.

Tries

Tries disebut juga (Prefix Tree). Kata Trie berasal dari kata RETRIEVAL, karent tries bisa mencari tiap kemungkinan kata hanya dengan prefix (huruf awal) kata tersebut.
Kegunaan dari Tries biasa digunakan untuk auto-complete dan spell checker.
Nilai pada root adalah kosong.

Berikut adalah contoh Tries:

Pada contoh disamping, Tries mengandung kalimat:
1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR








 

Bina Nusantara University                             skyconnectiva
 =============================End================================