Pertemuan 7 - (Red Black Tree dan 2-3 Tree)

RED BLACK TREE

Red Black Tree adalah BST dimana terdapat node berwarna merah atau hitam.

ATURAN RED BLACK TREE :

1. root selalu berwarna hitam
2. external node selalu berwarna hitam
3. node yang baru di insert selalu berwarna merah
4. node merah tidak boleh bertemu merah (child merah)
5. jumlah node hitam sama dari root ke external node

INSERTION

terdapat dua kondisi jika terjadi masalah
1. jika node yang baru di insert memiliki paman hitam (Black Uncle) maka penyelesaiannya:

• Rotasi dan tukar warna parent dengan siblingnya untuk single rotation

2. jika node yang baru di insert memiliki paman merah (Red Uncle) maka penyelesaiannya:

• Tukar warna paman dan parent menjadi hitam dan grand parent menjadi merah 

DELETION

terdapat 6 case dalam deletion RBT :

1. Jika node yang ingin di hapus merah, maka langsung hapus saja 

2. Jika node yang ingin di hapus hitam, maka tukar dengan child lalu recoloring menajdi hitam

3. Jika terdapat double black memiliki keponakan merah, maka lakukan single rotation atau double rotation

4. Jika terdapat double black memiliki saudara merah (red sibling), maka lakukan rotasi tarik lalu recoloring (double black blm hilang)

5. Jika terdapat double black memiliki parent merah (red parent), maka dengan melakukan recoloring antara parent dengan sibling double black hilang

6. Jika terdapat double black memiliki saudara hitam (black sibling), maka dengan melakukan recoloring pada siblingnya, double black pindah ke parent

2-3 TREE

2-3 Tree berbeda dengan binary tree. setiap node yang memiliki satu data elemen memiliki setidaknya 2 children atau dua data elemen memiliki setidaknya 3 children.

Syarat-syarat 2-3 Tree antara lain:1. Semua data disimpan secara berurut.
2. Semua leaf ada pada level yang sama (level terbawah).
3. Setiap non leaf adalah sebuah 2 node atau 3 node
4. Sebuah 3 node terdiri dari 2 data elemen dan 3 child.
5. Sebuah 2 node terdiri atas 1 data elemen dan 2 child.

INSERTION

insert (45). ketika ingin melakukan insert 45 yang menuju dua node maka 45 bisa langsung disisipkan

insert (75). ketika ingin melakukan insert 75 yang menuju dua node tetapi sudah penuh maka kita akan membandingkan ketiga nila tsb. nilai yang berada di tengah akan menjadi parent.

DELETION

Kondisi 1 

Kondisi 2

Continue reading →

Pertemuan 6 - (AVL Tree)

Jika suatu Binary Tree yang diinsert terus menerus pada saat kondisi tertentu akan menimbulkan height tree semakin besar dan berat sebelah yang menjadikan binary tree tidak efektif. 

Maka dari itu dibutuhkan Balanced Binary Tree agar tetap efektif. Salah satunya dengan menggunakan AVL Tree

AVL TREE

AVL Tree adalah binary tree yang memiliki perbedaan tinggi/level maksimal 1 antara subtree kiri dan subtree kanan.

Penambahan node 

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Terdapat 4 kasus pada saat tidak balance :

1. Node yang terdalam terletak di sebelah left subtree dari left child node T (LL)
2. Node yang terdalam terletak di sebelah right subtree dari right child node T (RR)
3. Node yang terdalam terletak di sebelah left subtree dari right child node T (LR)
4. Node yang terdalam terletak di sebelah lright subtree dari left child node T (RL)

Terdapat dua cara penyelesaian :

• Single Rotation (Kasus 1 & 2)
• Double Rotation (Kasus 3 & 4)

Single Rotation

Double Rotation

Penghapusan Node

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. 

Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

Delete 60

terjadi ketidak seimbangan, lakukan single rotation (RR) 

masih terjadi ketidak seimbangan, lakukan double rotation (LR) setelah itu lakukan single rotation (LL)

Binary Tree sudah dalam keadaan Balance

Continue reading →

Pertemuan 5 - (Binary Search Tree)

BINARY SEARCH TREE

adalah sebuah pohon biner dimana value yang lebih kecil diletakan dikiri dari root sedangkan yang lebih besar terletak dikanan root.

Operasi - operasi yang dapat dilakukan dengan binary search tree :

- Insert

- Delete

- View 

- Search

Insert

- Jika value yang di insert lebih kecil, maka pergi ke kiri

- Jika menemukan leaf, maka buat node baru

- Selain itu pergi ke kiri

lakukan hal tersebut berulan kali hingga menemukan leaf.

Delete

- Cari node dengan value yang ingin di hapus
- Jika value tersebut adalah leaf, maka hapus node tersebut
- Jika value tersebut mempunyai satu child, maka  hapus node tersebut lalu sambungkan child tersebut ke node sebelumnya
- Selain itu hapus value, kemudian tuker dengan successor

Search

- Jika tidak ada node, maka kemabalikan nilai NULL

- Jika node sama dengan value yang ingin dicari, maka kembalikan value

- Jika node lebih kecil dari value yang ingin dicari, maka pergi ke kiri

- Selain itu pergi ke kanan

ulangi langkah tersebut samai value yang ingin dicari sama dengan nodenya.

Continue reading →

Pertemuan 4 - (Tree Concept and Binary Concept)

Konsep Tree

tree adalah kumpulan node yang terhubung satu sama lain dan membentuk struktur seperti sebuah pohon.

istilah istilah yang sering digunakan dalam tree

1. Degree = banyak child dalam suatu node
2. Height = banyak tingkatan dalam suatu tree
3. Size = banyaknya node dalam suatu tree
4. Predecesor = node yang berada diatas suatu node tertentu
5. Successor = node yang berada dibawah suatu node tertentu
6. Parent = predecesor satu level diatas suatu node
7. Child = successor satu level dibawah suatu node
8. Sibling = node - node yang memiliki parent yang sama
9. Ancestor = seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama 
10. Descendant = seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama

Pembentukan Tree

Dapat dilakukan dengan 2 cara : Rekursif dan Non Rekursif 

Perhatikan kapan node dipasang di kiri dan dipasang di kanan


Jenis Tree ada yang berupa Binary Tree.

Binary Tree

merupakan Tree dengan syarat bahwa tiap nodenya maksimal memiliki dua subpohon dan masing masing subpohon harus terpisah.

Jenis - jenis Binary Tree

1. Full Binary Tree

tree yang memiliki 2 child dan setiap pohon memiliki panjang yang sama

2. Complete Binary Tree

tree yang mirip dengan Full Binary Tree tetapi setiap subtree boleh memiliki panjang yang berbeda. Full Binary Tree pasti merupakan Complete Binary Tree

3. Skewed Binary Tree
tree yang setiap nodenya hanya mempunyai satu child

Sifat - Sifat Binary Tree

Maksimum node dalam satu level dapat dihitung dengan cara 2^k. dimana k adalah level.

Maksimum node yang ada dalam binary tree dapat dihitung dengan cara 2^(h+1) - 1. Dimana h adalah height atau tingkatannya

Minimum height dapat dihitung dengan cara 2log(n) . Dimana n adalah jumlah node

Maksimum height dapat dihitung dengan cara n-1 . Dimana n adalah jumlah node

Continue reading →

Pertemuan 3 - (Stack & Queue)

Push = Enstack = Enqueue
Pop = Destack = Dequeue

KONSEP STACK

Stack mempunyai konsep Last In First Out (LIFO)

dengan kata lain, data yang masuk terakhir akan keluar pertama. Penyisipan selalu dilakukan di paling atas, dan penghapusan juga dilakukan di paling atas.

push : digunakan untuk menambahkan item pada stack pada tumpukan paling atas
pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

awal pointer pada linked list digunakan sebagai TOP. Jika TOP = NULL, artinya stack kosong.

DEPTH FIRS SEARCH

merupakan suatu algoritma penulusuran struktur graf/pohon beradasarkan kedalaman.

Kelebihan DFS adalah:

• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.

• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah:

• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

BREADTH FIRST SEARCH

juga merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon.

KONSEP QUEUE

Queue memiliki konsep Fisrt In First Out

start pointer linked list sebagai FRONT. Insert pada REAR dan delete pada FRONT. FRONT = REAR = NULL, artinya queue kosong.

Continue reading →

Pertemuan 2 - (Big Data, Arduini, Raspberry Pi, Cloud, Augmented Relaity)

Big Data

Merupakan data yang berukuran sangat besar, sangat variatif, sangat cepat pertumbuhannya, dan tidak terstruktur.

karena begitu besarnya sehingga sulit untuk memproses dengna menggunakan teknik database dan perangkat lunak biasa.

contoh big data adalah seperti petabyte dan exabyte (kapasitas diatas terabyte)

Google bisa dikatakan sebagai pelopor big data. Google meluncurkan Google bigtable. Dengan triliyunan user, google harus mampu menyimpan data berskala besar dan dapat memprosesnya secara cepat.

Arduino

Merupukan sebuah Mikrokontroler. Mikrokontroler adalah sebuah sistem komputer fungsional dalam sebuah chip.

Arduino merupakan sebuah rangkaian elektronik yang bersifat open source. Arduino dapat mengenali lingkungannya dengan sebuah sensor dan dapat mengendalikan lampu, motor,  dan berbagai jenis aktuator lainnya.

Berikut adalah gambaran fungsi Arduino :

Raspberry Pi

Merupakan sebuah mini kit  yang bisa dijadikan komputer mini. OS nya bisa macam - macam, salah satunya Linux. Ukurannya sangat kecil hanya sebesar kartu kredit. 

Berikut adalah contoh hasil karya dengna menggunakan Raspberry Pi atau biasa disebut Raspi :

Cloud

Merupakan gabungan pemanfaatan teknologi komputer dalam suatu jaringan dengan pengembangan internet.

Teknologi komputer yang berbasis seperti ini menggunakan internet sebagai pusat server untuk mengelola data dan juga aplikasi user.

Berikut adalah manfaat dari teknologi cloud :

1. Semua data tersimpan secara terpusat di server
2. Keamanan data
3. Fleksibilitas dan Skalabilitas yang tinggi
4. Investasi jangka panjang

Augmented Reality

atau dalam bahasa indonesia disebut sebagai realitas tambahan merupakan teknologi yang menggabungkan benda maya dua dimensi atau tiga dimensi dengan dunia nyata.

 

Continue reading →

Pertemuan 1 - (Introduction to Linked List)

Tujuan Pembelajaran :

• Menjelaskan konsep data struktur dan kegunaannya.

• Mengaplikasikan penggunaan data struktur.

POINTER 

adalah penunjuk dari suatu alamat yang berada dalam memory.

dengan adanya pointer kita dapat memanipulasi data yang berada pada alamat tertentu dalam memory. berbeda dengan variabel dimana jika kita menyimpan suatu data maka akan disimpan secara acak oleh sistem, sedangkan pointer kita dapat menunjuk letak penyimpanannya.

STRUCTURE 

adalah user-defined data type yang bisa menyimpan berbagai macam tipe data (heterogen) secara bersamaan. Struct terdiri dari beberapa anggota yang disebut dengan member atau variabel.

berbeda dengan array yang hanya dapat menampung tipe data yang sejenis.

• Memberikan nilai pada structure

untuk memberikan nilai pada struct dapat digunakan operator . (dot) untuk mengakses anggota dari suatu struct.

contoh : 

struct mhs{

char nama[100];

char nim[10];

int age;

};

mhs binus;

strcpy(binus.nama,"Renaldo");

strcpy(binus.nim,"1901559520");

binus.age = 19;

• Nested Structure 

adalah struct yang bertingkat dimana terdapat struct didalam sebuah struct.

contoh :

struct profile {

  int   age;

  char  name[100];

};

•

struct student {

  struct profile p;

  int  score;

  char grade;

};

----------------------------------------------------------------------------

DATA STRUKTUR

adalah dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan. secara efisien.

Berikut adalah contoh - contoh data struktur :

1.  Array
2. Linked Lists
3. Queues
4. Stacks
5. Binary Trees
6. Hash Tables

ARRAY

adalah kumpulan data yang bertipe sejenis (Homogen). Isi dari array disimpan pada memori yang berurutan dan tersusun berdasarkan index.

array index dimulai dari nol.

• Pendeklarasian Array 

contoh :

char nama[100];

• Pengaksesan Array

contoh :

nama[2] = 'F';

nama[3] = 'E';

nama[4] = 'R';

LINKED LIST 

adalah tipe data struktur yang terdiri dari urutan data records yang tersusun secara sekuensial, saling sambung-menyambung dan terbatas.

linked list saling terhubung dengan bantuan variabel pointer.

member dalam linked list disebut node. Node biasanya berupa struct yang memiliki beberapa field.

didalam linked list  biasa terdapat istilah head dan tail.Head adalah elemen yang berada pada posisi pertama suatu linked list. Kebalikannya, tail adalah elemen yang  berada pada posisi terakhir suatu linked list.

berikut adalah contoh Linked List :

• Single Linked List

adalah Linked List yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data. Hanya ada satu pointer yang menghubugkan setiap node (satu arah "next").

single linked list dibagi menjadi 2 :
- Single linked list circular
- Single linked list non circular.

cara untuk mendeklarasikan Single Linked List :
- Buat Struct
- Deklarasi variable pointer
- Alokasikan memori
- Isi data

• Single Linked List : Insert

Melakukan penyisipan data pada linked list, dilakukan dengan cara menghapus rantai hubungan terlebih dahulu lalu memberikan angka baru dan selanjutnya memberikan rantai hubungan baru.

• Single Linked List : Delete

untuk menghapus suatu nilai kita harus temukan terlebih dahulu lokasi node yang akan kita hapus, hilangkan dahulu node tersebut lalu hubungkan kembali node nya.

ada dua kondisi yang harus kita perhatikan :
- apakah node yang akan kita hapus berada di Head. 
- apakah node yang akan kita hapus berada tidak berada di Head.

contoh :

struct tnode *curr = head;

}

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);

// if x is not in head node, find the location

else {

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

LINKED LIST vs ARRAY

ARRAY 

- Kumpulan data
- Statis

- Dapat diakses secara random berdasarkan index

- Letaknya berurutan

LINKED LIST 

- Kumpulan node
- Dinamis

- Harus diakses secara berurutan

- Letaknya random

QUEUE

anggota yang masuk pertama adalah anggota yang akan keluar pertama. Atau biasa dikenal dengan istilah First In First Out (FIFO).

ada beberapa jenis Queue :

- Circular Queue : Queue yang kedua ujungnya saling terhubung.

- Priority Queue : Terdapat suatu anggota/elemen yang diprioritaskan.

STACKS

stacks dapat direpresentasikan sebagai array yang bertumpuk. Dimana setiap anggota yang masuk pertama adalah anggota yang akan keluar terakhir. Atau biasa dikenal dengan istilah First In Last Out (FILO).

BINARY TREES 

adalah kumpulan elemen yang disebut dengan node. Setiap elemen mempunyai pointer kiri dan pointer kanan.

MEMORY ALLOCATION

jika anda butuh untuk mengalokasikan memori pada saat run time, anda dapat menggunakan keyword malloc di C/C++.

untuk mende-alokasikannya anda dapat menggunakan keyword free.

Nama : Renaldo Akhira Ruslan 
Nim : 1901509520

Continue reading →