This is my story as a proud Binusian!

Diary of Binusian

Tag Archives: node

Data Structure (Pertemuan 8)

Posted on by Posted in Data Structures Leave a comment

HEAP

Heap merupakan sebuah complete binary tree yang memiliki beberapa sifat tertentu.

Min-Heap

  • Data pada node lebih kecil dari data pada anaknya.
  • Node dengan nilai terkecil terletak pada root.
  • Node dengan nilai terbesar terletak pada leaf.
  • Heap dapat diimplementasikan menggunakan linked-list, namun akan lebih mudah bila menggunakan array.
  • Contoh Min-Heap:

Operasi dalam Min-Heap

  • Find-Min
    Mencari data terkecil pada Min-Heap (Root).
  • Insertion
    1. Insert data baru sebagai node terakhir dari heap.
    2. Lakukan Up-Heap
      Bandingkan nilai data yang di-insert dengan parent-nya. Jika lebih kecil dari parent, maka tukar nilainya.
    3. Upheap dihentikan jika nilai parent-nya lebih kecil dari current node atau jika current node adalah root.
  • Deletion
    1. Tukar nilai dari data terakhir dengan root. Root sebagai current node.
    2. Karena data yang ingin dihapus sekarang berada pada leaf, langsung hapus.
    3. Lakukan Down-Heap
      Bandingkan nilai current node dengan kedua anaknya. Jika salah satu anaknya lebih kecil dari current node, tukar posisi. Jika kedua anaknya lebih kecil nilainya dari current node, tukar posisi dengan anak yang nilainya paling kecil.
    4. Down-Heap dihentikan jika current node bernilai lebih kecil dari kedua anaknya atau jika current node adalah leaf.

Max-Heap

  • Merupakan kebalikan dari Min-Heap.
  • Data pada node lebih besar dari data pada anaknya.
  • Node dengan nilai terbesar terletak pada root.
  • Node dengan nilai terkecil terletak pada leaf.
  • Operasi pada Max-Heap hampir sama dengan operasi pada Min-Heap. Yang membedakan hanya konsepnya saja (data terbesar ada pada root, parent lebih besar dari anak).

Min-Max Heap

  • Kondisi pada heap bergantian antara minimum dan maximum antar level.
  • Element pada level genap bernilai lebih kecil dari anaknya (min-level).
  • Element pada level ganjil bernilai lebih besar dari anaknya (max-level).
  • Root memiliki nilai paling kecil dan kedua anaknya memiliki nilai paling besar.
  • Contoh Min-Max Heap:

Operasi pada Min-Max Heap

  • Insertion
    1. Insert data baru sebagai node terakhir dari heap.
    2. Lakukan Upheap
      Proses Upheap pada Min-Max Heap:

      • Jika node baru ada pada Min-Level:
        1. Jika parent dari node baru lebih kecil dari node baru tersebut maka tukar nilai dan upheapmax dari parent.
        2. Selain di atas, upheapmin dari node baru.
      • Jika node baru ada pada Max-Level:
        1. Jika parent dari node baru lebih besar dari node baru tersebut maka tukar nilai dan upheapmin dari parent.
        2. Selain di atas, upheapmax dari node baru.
      • Upheapmin
        1. Bandingkan nilai dari current node dengan nilai dari grand-parent.
        2. Jika nilai dari current node lebih kecil dari parent-nya, maka tukar nilai.
      • Upheapmax
        1. Bandingkan nilai dari current node dengan nilai dari grand-parent.
        2. Jika nilai dari current node lebih besar dari parent-nya, maka tukar nilai.
  • Deletion
    • Deletion dari data terkecil:
      1. Tukar nilai root dengan nilai dari data terakhir pada heap.
      2. Hapus data terakhir.
      3. Downheapmin dari root.
    • Deletion dari data terbesar:
      1. Tukar nilai anak kiri atau anak kanan dari root dengan nilai dari data terakhir pada heap.
      2. Hapus data terakhir.
      3. Downheapmax dari node.
    • Downheapmin
      • m adalah anak dengan nilai terkecil dari current node dan grand-children.
      • Jika m adalah grand-children dari current node, maka:
        • Jika m lebih kecil dari current node, maka:
          1. Tukar nilainya.
          2. Jika m lebih besar dari parent-nya maka tukar nilainya.
          3. Lanjutkan downheapmin dari m.
      • Jika m adalah children dari current node, maka:
        • Jika m lebih kecil dari current node, maka:
          1. Tukar nilainya.
    • Downheapmax
      Kebalikan dari downheapmin.

_______________________________________________________________________

TRIES

Tries merupakan konsep struktur data yang digunakan untuk menyimpan string.

Contoh konsep Tries:

_______________________________________________________________________

HASHING

Pengertian Hashing:

  • Hashing adalah transformasi sebuah string dari beberapa karakter yang lebih singkat atau suatu kunci yang mewakili string aslinya.
  • Hashing digunakan untuk mengambil item dalam database karena lebih cepat untuk menemukan suatu item menggunakan hashed key daripada mencari value aslinya.

Hash Table

  • Merupakan sebuah tabel (array) dimana kita menyimpan string aslinya.
  • Index dari tabel tersebut berupa hashed key sementara nilainya (value) adalah string asli.
  • Contoh Hash Table:

Fungsi dalam Hash:

  • Mid-square
  • Division
  • Folding

Cara meng-handle collision:

  • Linear Probing
    Mencari slot kosong dan menempatkan string di slot kosong tersebut.
  • Chaining
    Menempatkan string pada slot sebagai chained list (linked list).

Data Structure (Pertemuan 7)

Posted on by Posted in Data Structures Leave a comment

RED BLACK TREE

Red Black Tree merupakan salah satu Balanced Binary Search Tree. Konsepnya hampir sama dengan AVL, namun Red Black Tree menggunakan pewarnaan merah atau hitam pada node dan violation ditentukan dari pewarnaan node tersebut.

Syarat dalam Red Black Tree:

  1. Root selalu berwarna hitam.
  2. Node berwarna merah tidak bisa memiliki parent atau child berwarna merah.
  3. Jumlah node hitam ke node eksternal sama.
  4. Apabila insert node baru, node tersebut diberi warna merah.

Operasi dalam Red Black Tree:

  1. Searching
    Proses searching pada Red Black Tree sama dengan proses searching Binary Search Tree.
  2. Insertion
    • Proses insertion sama dengan BST
    • Node yang di-insert diberi warna merah
    • Pastikan tidak ada violation
    • Bila ada violation gunakan langkah berikut:
      • Color Swap
      • Single Rotation
      • Double Rotation
  3. Deletion
    • Proses deletion pada RBT sama dengan deletion pada BST.
    • Anggap node yang ingin dihapus adalah M dan anaknya adalah C.
    • Jika M berwarna merah, maka gantikan M dengan C dan C harus hitam.
    • Jika M berwarna hitam dan C berwarna merah, ganti M dengan C dan ganti warna C menjadi hitam.
    • Jika M dan C berwarna hitam:
      • Ganti M dengan C.
      • Jika sibling berwarna merah, tukar warna sibling dan parent. Lalu lakukan single rotation pada parent.
      • Jika sibling berwarna hitam dan kedua anaknya juga berwarna hitam, maka ubah warna sibling menjadi merah.
      • Jika sibling berwarna merah dan salah satu anaknya berwarna merah, maka lakukan single rotation atau double rotation.

_______________________________________________________________________

2-3 TREE

2-3 Tree bukan merupakan binary tree. 2-3 Tree merupakan struktur data dimana:

  1. Setiap node yang memiliki 2 anak akan memiliki 1 data pada node.
  2. Setiap node yang memiliki 3 anak akan memiliki 2 data pada node.

Syarat pada 2-3 Tree:

  1. Setiap node internal (non leaf) adalah 2-node (1 data dan 2 anak) atau 3-node (2 data dan 3 anak).
  2. Data disimpan secara urut:
    • Pada 2-node, anak kiri lebih kecil dari anak kanan.
    • Pada 3-node, anak kiri lebih kecil dari anak kanan dan anak yang di tengah memiliki nilai yang masuk dalam range parents-nya (nilainya di antara parents-nya).
  3. Semua leaf berada di level yang sama.

Contoh 2-3 Tree:

Operasi pada 2-3 Tree:

  1. Searching
    Konsep searching pada 2-3 Tree sama dengan konsep searching pada BST. Perbedaan hanya pada maksimal jumlah data per node dan maksimal jumlah anak per node.
  2. Insertion
    • Konsep pada 2-3 Tree hampir sama dengan BST. Anak kiri lebih kecil dari anak kanan. Data kiri lebih kecil dari data kanan pada suatu node. Maka, apabila data yang di-insert lebih kecil dari node, penelusuran bergerak ke anak kiri menuju ke leaf. Sedangkan apabila data yang di-insert lebih besar dari node, penelusuran bergerak ke anak kanan menuju ke leaf.
    • Jika leaf merupakan 2-node, maka lakukan insert menjadi 3-node.
    • Jika leaf merupakan 3-node, push data tengah ke parent dan data dari node tersebut dipisahkan menjadi 2-node. Perbaiki parent secara rekursif.
  3. Deletion
    • Sama seperti BST, cari sebuah data pada leaf yang akan menggantikan data yang mau dihapus. Deletion akan selalu terjadi pada leaf.
    • Jika leaf berupa 3-node, maka delete node sehingga menjadi 2-node.
    • Jika leaf berupa 2-node:
      • Jika parent berupa 3-node, ambil 1 value dari parent. Jika sibling berupa 3-node, push 1 value dari sibling-nya ke parent (untuk membuat parent kembali menjadi 3-node). Jika sibling berupa 2-node, ubah parent menjadi 2-node dan gabungkan dengan sibling.
      • Jika parent berupa 2-node dan sibling-nya berupa 3-node, maka ambil 1 value dari parent dan push 1 value dari sibling ke parent. Jika sibling berupa 2-node, maka gabungkan parent dengan sibling.
      • Perbaiki parent secara rekursif.
    • Contoh deletion:



Tree, Binary Tree dan Expression Tree

Posted on by Posted in Data Structures Leave a comment

TREE 

Tree adalah kumpulan dari satu node atau lebih.

Beberapa istilah atau konsep dalam tree:

  • Root : Node yang berada di paling atas
  • Parent : Induk dari sebuah node
  • Child / children : Turunan dari sebuah node
  • Edge : Garis yang menghubungkan parent dengan child
  • Leaf : Node yang tidak memiliki children
  • Sibling : Node yang memiliki parent yang sama
  • Degree : Jumlah sub-tree dari sebuah node
  • Height / depth : Degree maksimum dalam sebuah tree
  • Ancestor : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node
  • Descendant : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node

_______________________________________________________________________

BINARY TREE

Binary tree adalah sebuah tree yang tiap node-nya memiliki paling banyak 2 children. Kedua child ini biasanya dibedakan menjadi left child dan right child. 

Tipe dari binary tree:

  • PERFECT Binary Tree, adalah binary tree yang seluruh level-nya memiliki height (depth) yang sama.
  • COMPLETE Binary Tree, adalah binary tree yang seluruh level-nya terisi penuh (kemungkinan terkecuali level terakhir). Semua node berada pada bagian kiri sejauh mungkin (bergantung pada jumlah parents, dsb.). Perfect Binary Tree termasuk Complete Binary Tree.
  • SKEWED Binary Tree, adalah binary tree yang tiap node-nya memiliki paling banyak satu child.
  • BALANCED Binary Tree, adalah binary tree yang terbentuk dimana tidak ada leaf yang lebih jauh dari root dibandingkan dengan leaf yang lain (tidak ada leaf yang lebih jauh atau lebih dekat dari leaf lain).

Properti dari Binary Tree:

  • Jumlah maksimal node pada binary tree dari level k adalah 2<sup>K</sup>
  • Jumlah maksimal node pada binary tree dari height h adalah 2<sup>h+1</sup>-1
  • Height maksimum suatu binary tree dari node n adalah <sup>2</sup>log(n)
  • Height minimum suatu binary tree dari node n adalah n-1

Representasi dari Binary Tree menggunakan array:

  • Index dari array merepresentasikan atau menunjukan nomor node
  • Index ke-0 merupakan root
  • Index dari Left Child adalah 2p + 1, dimana p = index dari parent
  • Index dari Right Child adalah 2p + 2, dimana p = index dari parent
  • Index dari Parent adalah (p-1)/2

Representasi dari Binary Tree menggunakan linked list:

_______________________________________________________________________

EXPRESSION TREE 

Expression tree dapat dibuat dari prefix atau postfix dengan proses rekursif.

Konsep dari expression tree:

  • Prefix : Print L R
    Contoh : *+abc
  • Postfix : L R Print
    Contoh : ab+c*
  • Infix : L Print R
    Contoh : (a+b)*c