Month: May 2016

Session – 8

Heap

Heap merupakan sebuah complete binary tree.

Heap terbagi menjadi 3 jenis yaitu :

• Min Heap
• Max Heap
• Min-Max Heap

Min Heap

Pada tree terdapat Min Heap, jika Parent selalu lebih kecil dari childnya. Sehingga nilai data yg paling kecil ada pada Rootnya.

Max Heap

Pada tree terdapat Max Heap, jika  Parentnya selalu lebih besar dari childnya (kebalikan dari Min Heap). Sehingga data yg ada pada Rootnya selalu data terbesar.

Min – Max Heap

Min-max heap merupakan sebuah kombinasi dari Min heap dan Max heap. Tiap levelnya akan berganti antara min heap dan max heap.

Tries

Tries adalah  sebuah variasi pada tree yang digunakan untuk menyimpan array asosiatif. Tries berfungsi untuk menebak dan mencari kata yang akan kita buat.

Hashing

Hashing merupakan sebuah alat pengubah/perubahan aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Dalam istilah bahasa hash berarti memenggal dan kemudian menggabungkan

Session 7

RBT (Red Black Tree)

Red – Black Tree atau yang biasa disebut dengan RBT merupakan sebuah part atau bagian dari self balancing binary search tree.

RBT memiliki ciri – ciri :

• Setiap node mempunyai warna (hanya terdapat 2 warna hitam atau merah)
• Root (akar induk node) memiliki warna default yaitu warna merah
• Node yang baru di insert berwarna merah
• Node yang memiliki anak, anaknya harus berwarna hitam (tidak boleh merah ketemu merah entar ga serasi).

Pada RBT terdapat beberapa fungsi yaitu :

• Insertion
• Deletion

Insertion

Merupakan salah satu operasi pada RBT yang berfungsi untuk me – Insert sebuah node. operasi insert pada RBT ini sama dengan operasi insert pada binary search tree.

Memiliki ciri – ciri :

• Node baru (new node) yang akan dimasukkan berwarna merah
• Kalau parent dari sebuah node itu berwarna merah akan terjadi sebuah violation (semacam intimidasi karena node sama – sama berwarna merah)

Deletion

Merupakan salah satu operasi pada RBT yang berfungsi untuk me – delete sebuah node. Sama seperti insertion pada RBT operasi sama persis dengan binary search tree (BST).

Memiliki ciri – ciri :

• Jika node yang dihapus berwarna merah, ganti dengan anaknya yg berwarna hitam.
• Jika node yang dihapus berwarna hitam dan anaknya merah, ganti dengan anaknya lalu ubah warna childnya menjadi hitam.

 

 

AVL Tree

AVL Tree merupakan sebuah Binary Search Tree yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan.

AVL Tree Berfungsi untuk menyeimbangkan Binary Search Tree, Jadi dengan menggunakan AVL Tree waktu pencarian dan bentuk tree dapat disederhanakan.

AVL Tree terdiri dari 2 jenis yaitu :

• Single Rotation
• Double Rotation

Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti gambar berikut

Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar