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