Heap & Tries

                              HEAPS &TRIES

  Heaps & Tries

Heaps adalah sebuah binary tree khusus yang digunakan untuk menyimpan data secara berurutan/sorted. Hal tersebut membuat pencarian menjadi lambat namun mempercepat pemasukan data serta root dari tree tersebut dapat dengan mudah dihapus.

Tries yang dibaca sebagai "Trees" adalah sebuah tree yang tidak mementikan keberadaan dari nodes, namun key/value dapat dikaitkan dengan edges dan node hanya ada untuk mengisi. Value sebenarnya dari tree ini hanya terdapat pada leaves dan sibling memiliki hubungan yang disebuit common prefix.

A. HEAPS

• Heaps sangatlah mirip dengan BST, mereka memilki dua valua namun tidak seperti BST, dimana children memiliki nialai yang selalu lebih kecil dibandingkan parentnya (atau nilai yang lebih besar pada min tree). Dalam arti root akan selalu memiliki nilai paling besar
• Karena heaps tidak begutu ketet terhadap urutan, maka dari itui memasukkan data lebih cepat daripada memasukkannya pada sorted array dikarenakan [0(log n)].
• Heaps juga lebih cepat dalam memasukkan data daripada BST dikarenakan kedalaman atau tinggi dari Tree dan juga dengan mudah Heaps Tree dapat tetap seimbang.
• Namun kelemahan dari Heaps adalah saat mencari data.
• Kelebihannya yang lain adalah efisiensi dalam penghapusan Root dari Tree-nya

Heaps biasanya memiliki 2 bentuk yaitu, Max Heap dan Min Heap.

Cara kerja Heap :

• Heaps biasanya tersimpan pada sebuah array karena heaps adalah sebuah binary tree yang dapat dengan cepat menghitung node children berdasarkan indexnya
• Kelemahannya ialah diperlukan memori yang telah dialokasi terlebih dahulu atau membuat ukuran maxnya ataupun membuat array dinamik.
• Menambahkan data ke Heap bisa disebut sebagai "up-heap”, “bubble up” dan “trickle up”.

1. Menambahkan node biasanya ditaruh di yang paling bawah pada nilai pertama yang terbuka
2. Jika Node barunya bernilai lebih kecil daripada Parent-nya maka lakukan swap dan terus  diulang hingga sesuai

• Pengurangan data ke Heap bisa disebut sebagai "downheap”, “bubble-down" dan “trickle-down”.

1. Pindahkan nilai dari yang terakhir diisi menjadi 0.
2. Jika Node barunya bernilai lebih besar daripada Child-nya maka lakukan swap dan terus diulang hingga sesuai.

Contoh pada MIN Heap

> Insert 12

> Delete Root

B. TRIES

• Tries biasanya digunakan sebagai cara cepat untuk sort dan insert data sekaligus sebagai spellchecker, autocomplete dan juga search engines.
• Root pada Tries tidak memiliki karakter/("")
• Node Tries biasanya berisi karakter.
• Kelebihan

1. Dapat dengan cepat mencari case terburuk daripada hash table yang tidak sempurna
2. Tidak perlu mementingkan hash yang buruk dan juga collision yang buruk
3. Dengan mudah membagikan sebuah listing berurutan tanpa struktur data tambahan/

• Kekurangan

1. Pencarian pada Tries dapat lebih lambat daripada Hash, tepatnya jika mesin yang digunakan memiliki waktu random-access yang buruk
2. Tidak baik digunakan saat ada chains yang tidak berguna
3. Dapat menggunakan memori ynag lebih banyak daripada hash table

Contoh dari Tries

> Insertion

Kata-kata yang terdapat pada Tries di atas yaitu :

• Bean
• Bed
• Bee
• Bell
• Brew
• Bread
• Break

AVL Tree

   AVL TREE

AVL Tree adalah bentuk dari Binary Search Tree(BST) yang telah dikembangkan untuk dapat menyeiambangkan dirinya sendiri secara otomatis saat memasukkan data didalamnya dan juga masih memiliki semua sifat dan ciri dari BST.

AVL Tree juga memiliki ciri seperti, setiap root pastinya berada di paling atas; setiap root bisa memiliki nol, satu maupun dua child nodes; setiap child node bisa memiliki nol, satu atau lebih dari satu child node lainnya; dan biasanya setiap node yang berada di posisi kanan memiliki nilai yang relatif kecil daripada node yang berada di kanan yang nilainya relatif lebih besar.

Namun AVL Tree memiliki ciri khasnya yaitu, perbedaan kedalaman antara node kiri dan node kanan tidak boleh melebihi satu, dimana dalam pemrograman AVL Tree harus memiliki kode yang dapat mengatur/mengubah/menyeimbangkan tree pada saat nilai yang baru dimasukkan kedalam node yang baru.

                             
Metode yang ada pada AVL Tree mencakup Insertion dan Deletion

INSERTION

  1. Single LEFT Rotation (LL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kanan maka perlu dilakukan  sebuah Left Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kirinya.
Seperti contoh:
                                       
Pada contoh tersebut, diambil node yang berisi nilai 85 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Left Rotation sekali.

  2. Single RIGHT Rotation (RR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kiri maka perlu dilakukan  sebuah Right Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kanannya.
Seperti contoh:
                                             

Pada contoh tersebut, diambil node yang berisi nilai 44 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Right Rotation sekali.

  3. LEFT-RIGHT Rotation (LR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kanan maka perlu dilakukan  sebuah Left-Right Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Left Rotation kemudian Right Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kiri dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kanannya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 39 menjadi poros kemudian dilakukan Left Rotation dan dilanjutkan dengan mengambil nilai 39 lagi menjadi porosnya dan dilakukan Right Rotation.
  4. RIGHT-LEFT Rotation (RL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kiri maka perlu dilakukan  sebuah Right-Left Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Right Rotation kemudian Left Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kanan dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kirinya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 40 menjadi poros kemudian dilakukan Right Rotation dan dilanjutkan dengan mengambil nilai 40 lagi menjadi porosnya dan dilakukan Left Rotation.

DELETION
Biasanya dalam operasi Deletion dalam AVL Tree memiliki 2 kasus yaitu,
1. Ketika yang akan dihapus adalah node yang tidak memiliki anak, maka dari itu penghapusan dapat segera dilakukan tanpa mengubah Tree-nya.
2. Ketika yang akan dihapus adalah node yang memiliki anak, maka dari itu proses harus dilakukan  penyeimbangkan Tree-nya setelah melakukan penghapusan.