All About Binusian Life at Binus | 2016

Data Structure (Pertemuan 8)

0

9 years

by hansadvent in Uncategorized

HEAP

Heap adalah salah satu data structure yang berbentuk tree dan berbeda dengan binary search tree (BST).

Jenis-jenis dari heap adalah Max-Heap, Min-Heap, dan Min-Max Heap.

MAX HEAP

Node paling atas berisi value angka yang paling besar dari anak-anak dan keturunannya.

Anak dari suatu node harus lebih kecil daripada orang tuanya, jika tidak maka harus dilakukan rotasi.

MIN HEAP

Node paling atas berisi value angka yang paling kecil dari anak-anak dan keturunannya.

Anak dari suatu node harus lebih besar daripada orang tuanya, jika tidak maka harus dilakukan rotasi.

MIN-MAX HEAP

Min-max heap tersusun dari tree yang tiap levelnya memiliki heap yang berbeda (max atau min).

Pada level 0 (paling atas) adalah min heap, pada level 1 max heap dan seterusnya.

INSERT

Heap di insert / disusun dari atas ke bawa dan dari kiri ke kanan.

Pada gambar di bawah, terdapat salah satu contoh insert angka 15 pada max heap.

Setelah angka 15 di insert, karena heap adalah max heap maka dia harus cek ke parentnya apakah angka 15 tersebut lebih besar daripada parentnya. Jika ya, maka keduanya harus bertukar tempat. Begitu seterusnya sampai angka 15 lebih kecil daripada parentnya atau angka 15 telah sampai di level 0.

TRIES

Tries adalah struktur data yang berbentuk tree dan digunakan untuk mencari sebuah kata (misalnya dalam sebuah search engine).

Tries berasal dari kata Retrieval .

HASHING

Hashing adalah salah satu struktur data yang merupakan transformasi dari string untuk mengambil nilai length terpendek dalam string.

Tujuan dari Hashing adalah untuk mempercepat pencarian data yang sudah tersimpan sebelumnya.

Data Structure (Pertemuan 7)

0

9 years

by hansadvent in Uncategorized

RED BLACK TREE

Red Black Tree bisa disebut sebagai Binary Search Tree yang mempunyai fungsi yang sama.

Ciri-ciri dari Red Black Tree adalah:

1. Setiap node mempunyai warna yang antara lain adalah merah atau hitam

2. Root (external node) selalu berwarna hitam

3. Leaf atau akar dari root berwarna hitam

4. Jika suatu node berwarna merah, maka anak-anaknya berwarna hitam

5. Node yang baru dimasukkan selalu berwarna merah

Insertion

Ada beberap violation yang dapat terjadi dalam insertion:

Jika parent dan uncle dari new node adalah merah, maka violation dapat dihindari dengan cara merubah wanr dari parent dan uncle menjadi hitam

Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih kecil daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan single rotate seperti pada gambar

Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih besar daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan double rotate seperti pada gambar

Deletion

Deletion pada Red Black Tree umumnya sama seperti pada BST

Dalam Deletion pada Red Black Tree, ada dua hal yang dapat terjadi pada umumnya

Jika node yang ingin di-delete adalah node merah, maka dapat langsung dihapus
Jika node yang ingin di-delete adalah node hitam, maka dapat terjadi double black

Pada gambar dibawah, terjadi double black pada node a. Jika saudara dari a adalah merah, maka terjadi single rotatation dan X menjadi warna merah.

Pada gambar di bawah, jika a adalah double black dan Y beserta anak-anaknya adalah hitam juga, maka Y akan menjadi warna merah dan double black berpindah kepada parent dari a dan Y.

Pada gambar di bawah, a adalah double black, saudara dari a (Z) adalah hitam dan mempunyai anak yang berwarna merah. Pada kondisi tersebut, harus dilakukan double rotation.

2-3 Tree

2-3 Tree:

Setiap internal node merupakan 2 node yang punya 1 data dan 2 anak, atau 3 node yang punya 2 data dan 3 anak
Semua leaf harus berada dalam level yang sama
Semua node ter organisir seperti halnya dengan BST

Insertion

Jika tree kosong, insert new node pada letaknya
Jika tree sudah terisi satu value, maka buat node barunya di sebelah value dalam node tersebut
Jika tree sudah terdapat 2 value, dan masih ingin diletakkan node baru, maka value tengah dari ketiga tersebut akan split

Data Structure (Pertemuan 6)

0

9 years

by hansadvent in Uncategorized

AVL TREE

Pada pertemuan sebelumnya, telah diketahui bahwa Binary Search Tree (BST) adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.

Sedangkan AVL Tree adalah Binary Search Tree yang sudah seimbang (dapat menyeimbangkan treenya sendiri). Tujuan / kelebihan dari avl tree ada pada proses searching yang lebih cepat karena sudah seimbang kiri dan kanan dari tree tersebut.