Archive for May, 2016

Rangkuman Struktur Data 8

0
8 years
by in Uncategorized

HEAP

Heap adalah sebuah complete binary tree.

Sebuah tree disebut heap maksimum saat semua node nilainya lebih besar dari childnya. (Semakin kebawah semakin kecil)

Sebuah tree disebut heap minimum saat semua node nilainya lebih kecil dari childnya. (Semakin kebawah semakin besar)

Contoh max heap:

max-heap

 

Contoh min heap:

min-heap

 

Insertion

I. Max heap

Saat node baru diinsert, lakukan pengecekan terhadap parentnya. Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent. Lakukan pengecekan tersebut sampai syarat tidak terpenuhi lagi.

 

II. Min heap

Saat node baru diinsert, lakukan pengecekan terhadap parentnya. Jika node baru bernilai lebih kecil dibandingkan parent, tukar posisinya dengan parent. Lakukan pengecekan tersebut sampai syarat tidak terpenuhi lagi.

 

Deletion

Deletion pada heap pasti dilakukan di root, lalu ditukar posisi dengan node pada posisi terakhir. Lalu cek node tersebut dengan childnya sesuai dengan heapnya (jika max heap, tukar node dengan childnya jika node tersebut lebih kecil dari childnya, sebaliknya untuk min heap).

 

MIN-MAX HEAP

Min-max heap adalah kombinasi dari min heap dan max heap.

Tiap levelnya akan berganti antara min heap dan max heap.

Kegunaan min-max heap adalah untuk menemukan nilai max dan min dalam 1 heap saja.

1

 

Insertion

Jika node baru berada di level min, bandingkan dengan parentnya. Jika parent lebih kecil dari node baru, maka tukar node dengan parentnya, lalu upheapmax. Jika tidak, upheapmin.

Jika node baru berada di level max, bandingkan dengan parentnya. Jika parent lebih besar dari node baru, maka tukar node dengan parentnya, lalu upheapmin. Jika tidak, upheapmax.

 

Deletion

I. Delete min

Tuker root dengan node terakhir dari heap lalu hapus root yang sudah berada di node terakhir tersebut. Downheapmin dari root.

II. Delete max

Tukar anak kiri atau kanan dari root dengan node terakhir dari heap lalu hapus. Downheapmax dari node tersebut.

 

TRIES

Tries adalah suatu tree sruktur data yang digunakan untuk menyimpan array asosiatif.

Trie berasal dari kata RETRIEVAL, karena tries dapat menemukan satu kata dalam kamus dengan hanya awalan kata.

Contoh tries:

4084796

 

HASHING

Hashing adalah transformasi dari string yang berupa karakter menjadi sebuah versi yang lebih pendek sambil tetap mewakili karakter awalnya.

Fungsi dalam hashing:

  • Mid-square: String dikuadratkan, lalu ambil nilai tengah untuk menjadi hash key.
  • Division : Bagi string dengan menggunakan operator modulus.
  • Folding : Bagi string menjadi beberapa bagian, kemudian tambahkan bagian-bagian tersebut untuk mendapatkan hash key.

Rangkuman Struktur Data 7

0
8 years
by in Uncategorized

RED BLACK TREE

  • Root selalu warna hitam
  • External node selalu warna hitam
  • Node baru selalu warna merah
  • Node merah tidak boleh mempunyai anak warna merah

 

INSERTION

 

Picture1

Jika paman berwarna merah, maka tukar warna parent dan paman nya menjadi hitam, dan grand parent menjadi merah.

 

Picture2                         Picture3

Jika paman berwarna hitam, maka lakukan single rotation atau double rotation.

 

 

DELETION

 

Jika menghapus node berwarna merah, maka langsung hapus.

Jika menghapus node berwarna hitam, maka langsung hapus dan digantikan oleh anaknya, lalu ubah warnanya menjadi hitam.

Jika terjadi double black:

Picture4           Picture5          Picture6

 

 

2-3 TREE

Tree yang memungkinkan untuk memiliki 2 atau 3 data dlam sebuah node.

2-node : Node yang berisi 1 data dan mempunyai 2 child.

2node

3-node : Node yang berisi 2 data dan mempunyai 3 child.

3node

 

INSERTION

Data yang dimasukkan pasti masuk ke leaf.

Jika dimasukkan ke 2-node, maka langsung masukkan.

Jika dimasukkan ke 3-node, maka data tengah naik menjadi parent.

 

DELETION

Tentukan di node mana data yang ingin dihapus

Jika berada dalam 3-node, langsung hapus saja datanya.

Jika berada dalam 2-node:

I. Jika parent adalah 3-node: ambil satu data dari parent.

  • Jika sibling adalah 3-node, ambil salah satu datanya untuk dijadikan data parent.
  • Jika sibling adalah 2-node, buat parent menjadi 2-node dengan menggabungkan sibling dengan node tempat data didelete.

II. Jika parent adalah 2-node:

  • Jika sibling adalah 3-node, turunkan data parent ke node dan ambil satu data dari sibling untuk menggantikan parent.
  • Jika sibling adalah 2-node, gabungkan sibling dengan node yang dihapus datanya.

 

Rangkuman Struktur Data 6

0
8 years
by in Data Structure

AVL TREE

 

AVL Tree adalah BST yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree berfungsi untuk menyeimbangkan(balance) BST. Dengan adanya AVL Tree, waktu pencarian dapat dipersingkat dan bentuk tree dapat disederhanakan.

 

Contoh AVL Tree:

AVLSample

 

Insertion dalam AVL Tree

Setiap penambahan sebuah node ke AVL Tree harus dilakukan pemeriksaan dari node baru ke root. Node pertama yang memiliki balance factor lebih dari 1 diseimbangkan. Proses penyeimbangan dibagi menjadi 2, yaitu Single Rotation dan Double Rotation.

 

Single Rotation

 

  • Left Rotation

avl_left_rotation

 

  • Right Rotation

avl_right_rotation

 

 

Double Rotation

 

  • Left-Right Rotation

 

1   Sebuah node dimasukkan ke subtree kanan dari subtree kiri.

 

2  Lakukan left rotation pada subtree kiri dari node C. A menjadi subtree kiri dari B.

 

3  Node C masih belum seimbang karena subtree kiri dari subtree kiri.

 

4  Lakukan right rotation sehingga B menjadi root, C menjadi subtree kanan dari subtree kirinya.

 

5 Tree menjadi seimbang.

 

 

  • Right-Left Rotation

 

6   Sebuah node dimasukkan ke subtree kiri dari subtree kanan.

 

7  Lakukan right rotation pada node C. C menjadi subtree kanan dari subtree kirinya. B menjadi subtree kanan dari A.

 

8   Node a masih belum seimbang.

 

9 Lakukan left rotation sehingga B menjadi root, A menjadi subtree kiri dari subtree kanan nya.

 

10 Tree menjadi seimbang.

 

 

Deletion dalam AVL Tree

Deletion dalam AVL Tree mirip dengan BST, hanya perlu diperhatikan keseimbangan tree seperti dalam insertion. Lakukan single atau double rotation setiap ada ketidakseimbangan.

 

 

GUEST LECTURE

Guest lecture: Selvakumar Manickam dari University of Science, Malaysia.

Guest lecture menjelaskan tentang Tree, BST, serta keektifannya.

 

DSO

 

Go to Top