STRUKTUR DATA - Material Review + Binary Search Tree

Array

Array adalah kumpulan elemen data yang homogen, karena memiliki kesamaan tipe data. Biasanya disimpan secara berurutan didalam suatu memory. Index biasanya dimulai dengan 0 sampai n-1, dimana n adalah jumlah elemen.

Pointer

Pointer adalah variabel yang menyimpan alamat memory dari suatu variabel lain. Pengubahan suatu nilai pada variabel pointer akan mempengaruhi nilai variabel yang disimpan pula, sehingga penggunaannya cukup beresiko.
Array dan pointer saling berhubungan. karena  array juga menunjuk suatu alamat sama halnya seperti pointer, seperti A[10] memiliki arti yang sama jika ditulis *(A + 10)


Linked List

Linked List atau senarai berantai adalah suatu struktur data dimana setiap elemennya (node) dihubungkan oleh pointer sehingga membentuk suatu rangkaian/rantai data. Linked list ada beberapa jenis, yaitu :
  • Single/Singly Linked List
  • Double/Doubly Linked List
  • Multiple Linked List
  • Circular Linked List

Array Vs Linked List




Linked list dapat dibuat circular, sehingga dari data terakhir dapat kembali ke data pertama. Sedangkan array tidak, namun array tetap dapat dibuat circular dengan menggunakan rumus berikut untuk kondisinya:

F + 1 % n

dengan F = front/head/elemen pertama ; n = jumlah data

Selain itu, kelemahan array juga ketidakdinamisannya dalam jumlah memory, akan tetapi array dapat dibuat dinamis dengan menggunakan rumus berikut :

sizeof (array) / sizeof (int)


Stack

Stack adalah suatu kumpulan data seperti tumpukan yang menggunakan konsep FILO(first in last out) atau LIFO(last in first out). Elemen terakhir yang diinput atau elemen teratas dalam suatu stack disebut TOP.
  • Suatu stack dikatakan kosong/empty apabila Top = -1
  • Suatu stack dikatakan penuh/full apabila Top = Max-1, dengan max adalah jumlah data

Kedua kondisi diatas, merupakan suatu kondisi dimana stack menggunakan array.
Pengambilan elemen Top pada stack disebut Peek.

Queue

Queue adalah suatu kumpulan data seperti antrian yang menggunakan konsep FIFO(first in first out) atau LILO(last in last out). Namun ada juga yang sebut Priority Queue yaitu queue berdasarkan prioritas. Dimana queue tersebut sudah tersorting otomatis sesuai prioritas.

Abstract Data Type

Abstract Data Type atau ADT adalah tipe data yang digunakan untuk menyembunyikan isi datanya sehingga hanya dia (pembuat) yang mengetahui data sebenarnya. Contohnya : struct, class, dan typedef.

Prefix, Infix, dan Postfix

Prefix, infix dan postfix merupakan suatu cara penulisan atau notasi suatu operasi perhitungan / matematika berdasarkan operan dan operatornya.
  • Operan adalah bilangan/angka yang kita akan hitung
  • Operator adalah lambang perhitungan yang kita gunakan untuk mengoperasikan operan, misalnya +, -, /, *, ^, dsb.
  • Prefix : Operator diletakan sebelum operan.
  • Infix : Operator diletakan diantara operan.
  • Posfix : Operator diletakan setelah operan.


Binary Tree

Binary Tree adalah sebuah struktur data yang menyerupai pohon dan setiap simpulnya memiliki cabang maksimal 2. Selain itu penempatan simpulnya pun bebas, kiri atau kanan tergantung keinginan. Ada beberapa jenis BT, yaitu :
  • Perfect Binary Tree
  • Complete Binary Tree
  • Skewed Binary Tree
  • Balanced Binary Tree


Binary Search Tree

Binary Search Tree adalah sebuah binary tree dimana dalam penempatan simpulnya tidak bebas, melainkan melalui aturan tertentu, seperti sebelah kiri nilainya harus lebih kecil dari root, dan kanan lebih besar. Sehingga simpul tersebut nilainya sudah tersorting otomatis. Dalam BST, setiap simpulnya tidak boleh memiliki nilai yang sama.

Setiap pohon memiliki root dan leaf, root adalah simpul yang tidak memiliki parent dan leaf adalah simpul yang tidak memiliki anak. Berikut ilustrasinya :


Pada BT terdapat istilah Ancestor dan Descendent, dimana Ancestor adalah induk dari suatu simpul. Sedangkan Descendent adalah turunan dari suatu simpul. Contoh pada gambar diatas :
  • Ancestor dari E adalah B dan A.
  • Descendent dari A adalah B, D dan E.

untuk menulis notasi prefix, infix, atau postfix dari tree, dapat menggunakan cara berikut :
  • Prefix = VLR
  • Infix = LVR
  • Postfix = LRV
dengan v = cetak, r = right, l = kiri 

contohnya :

dari tree diatas,
  • prefix = +-132, 
  • infix = 1-3+2, 
  • postfix = 13-2+

Dalam BST ada 2 jenis atau cara pencarian, yaitu :
  • Depth First Search (DFS): DFS adalah pencarian berdasarkan kedalamannya.
  • Breadth First Search (BFS): BFS adalah pencarian berdasarkan perluasannya.

Ilustrasinya :





Location: indonesia

Comments

Post a Comment

POPULAR

STRUKTUR DATA - Linked List

Linked List Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.  Head adalah elemen yang berada pada posisi pertama dalam suatu linked list Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list Ada beberapa macam Linked List, yaitu : Single Linked List Double Linked List Circular Linked List Multiple Linked List Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL. contoh : contoh codingannya : struct Mahasiswa{       char nama[25];       int usia;       struct
Read more

STRUKTUR DATA - Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree

Balanced Binary Search Tree Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N  adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan seaching, kecepatan waktu merupakan hal yang cukup penting untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. untuk menetapkan tingginya, kita dapat menggunakan rumus berikut: O(log n) 2 contoh tree yang termasuk ke dalam balanced binary search tree, yaitu : - AVL Tree - Red Black Tree (RBT) AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisi
Read more

STRUKTUR DATA - B Tree and Heap & Deap

B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree  merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak. Aturan pada B-Tree : m = order Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak Root memiliki anak minimal 2, selama root bukan leaf Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1 Data yang tersimpan pada node harus terurut secara inorder Semua leaf berada pada level yang sama, level terbawah Berikut contoh B-Tree : B-Tree order 4 B-Tree order 6 Operasi : Searching Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-ta
Read more