5 - binary search tree - 2101656755 - Wantika Aprilia Wangke

Selamat datang di pertemuan ke-lima dengan topik Binary Search three

Binary Search Tree sendiri adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.

Sub Topics

- Operations: Search, Insertion, Deletion

- Program Example

- Expression Tree Concept

- Create Exp. Tree from prefix

- Create Exp. Tree from postfix

- Create Exp. Tree from Infix

- Prefix, Postfix, Infix Traversal

 

1.  Operations

Binary search tree memiliki beberapa basic operation:
- find(x) = search / cari "x" BST
- insert(x)= push / masukkan '"x" ke dalam BST
- remove(x) = pop / hapus "x" dari BST
 

Search:

 

Pencarian (Searching) dimulai dari rootnya (di gambar adalah angka 50). Jika angka yang dicari belum ditemukan, maka pencarian akan dilanjutkan, jika angka yang dicari lebih kecil dari root, maka pencarian akan ke sebelah kiri root, jika sebaliknya maka akan dicari ke sebelah kanan root. Begitu seterusnya samapi ditemukan angka yang dicari.
Misal jika angka yang dicari adalah 23, maka pencarian akan dimulai dari:

• 23 != root, maka 23 dibandingkan dengan root
• 23 < 50, maka pencarian dilanjutkan ke sebelah kiri
• 23 != 17, maka 23 dibandingkan dengan 17
• 23 > 17, maka pencarian dilanjutkan ke sebelah kanan
• 23 == 23, maka pencarian telah berhasil dan selesa

Insertion

Data yang lebih kecil daripada root / parent, diletakan di sebelah kiri.

Data yang lebih besar daripada root / parent  diletakan disebelah kanan.

contoh:

insert 35 kedalam BST. Maka 35 akan diletakan di sebelah kanan 32.

 

Deletion

 

Ada 3 cases yang harus diperhatikan:

-       Jika kuncinya adalah leaf, hapus saja nodenya

-        Jika kuncinya adalah node yang hanya mempunyai satu anak, hapus nodenya dan konek anaknya kepada orangtuanya.

-        Jika kuncinya adalah node mempunyai dua anak, temukan anak yang paling benar yang mempunyai sub tree disebelah kiri, gantikan kuncinya dengan kunci P’s dan hapus P secara recursive.

Demikian blog hari ini trima kasih!

4- Introduction to tree, binary tree and expression tree- 2101656755 - Wantika Aprilia Wangke

Hallo!
Mari segera kita bahas tentang sub topik yang ada:

Tree & Binary Tree:

-Tree Concept

-Binary Tree Concept

-Type of Binary Tree

-Property of Binary Tree

-Representation of Binary Tree

-Expression Tree Concept

-Create Expression Tree from Prefix, Postfix and Infix

-Prefix, Postfix and Infix Traversal

~KONSEP TREE~

Bagian utama dari tree adalah:

Root = node teratas dari tree (data yang pertama kali di-push).
Children = sub-tree dari sebuah node.
Leaf = node yang tidak memiliki children.
Sibling = node yang mempunyai parent yang sama.
Degree = total sub-tree dari sebuah node.
Height/Depth = degree maksimum dari sebuah node.
Ancestor = semua node parent dan yang di atas parent
Descendant = semua node child dan yang di bawa child

 

contoh dari tree

Root = A
Children dari A = B, C, D
Leaf  = E, F, G,
Sibling = F & G
Degree dari A = 3
Height = 3
Ancestor dari E = B & A
Descendant dari A = B, C, D, E, F, G

~KONSEP BINARY TREE~

Binary Tree adalah data structure bercabang yang masing-masing nodenya maksimal memiliki dua anak, yaitu anak kiri dan anak kanan

~TYPE OF BINARY TREE~ 
 PERFECT Binary Tree

 COMPLETE Binary Tree

 SKEWED Binary Tree

3 - linked list implementation 2- 2101656755 - Wantika Aprilia Wangke

Hal yang di tekankan di kelas tadi adalah:

●Stack concept
Stack adalah struktur data yang penting dan menyimpan unsur-unsurnya secara teratur atau juga Stack adalah struktur data linier yang dapat diimplementasikan dengan menggunakan array atau linked list.
Kamu pernah makan potato chips yg di tabung itu kan? Nah bila kamu memasukkan potato chips ke dalam tabung maka otomatis potato chips yang keluar pertama nanti adalah potato chips yang kamu masukkan paling terakhir. Nah seperti konsep potato chips itu, kamu dapat menambahkan dan menghapus elemen (yaitu pelat) hanya di / dari satu posisi yang merupakan posisi paling atas.
Elemen dalam tumpukan ditambahkan dan dihapus hanya dari satu ujung, yang disebut bagian atas.
Data disimpan dalam cara Last In First Out (LIFO).

-Stack operations
Opertor stack ada 3 yaitu :
Push (x): tambahkan item x ke bagian atas tumpukan.
pop (): hapus item.
top (): mengungkapkan / mengembalikan item teratas dari stack

●Infix, Postfix and Prefix Notation

Prefix, infix, dan postfix adalah suatu cara penulisan ungkapan-ungkapan yang rumit, misalnya pemakaian tanda kurung dalam operasi matematika.
Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.
Contoh pemakaian prefix adalah +AB, – +ABC, * + AB – CD.
Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.
Cara menggingatnya posisi operator dengan baik =
(Pre)fix, (in)fix, dan (post)fix.

Sekian dari saya trimakasih.

2 - linked list implementation 1- 2101656755 - Wantika Aprilia Wangke

Hari ini pada pertemuan kedua kami belajar tentang

LO1: konsep struktur data dan penggunaannya dalam aplikasi.
LO2: Terapan struktur data dalam aplikasi.

Sub topik
Single Linked List
-Polynomial Representation
-Circular Single Linked List
-Doubly Linked List
-Circular Doubly Linked List
-Header Linked List

Berikut adalah pembahasan sub topik yang ada:
1. Single linked list
Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Representasi sebuah linked list dapat digambarkan melalui gambar di bawah ini:

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.

Berikut adalah algoritma untuk memasukkan, menghapus dan mencari node dalam satu linked list.

Insert: Untuk memasukkan node baru di awal daftar, buat pointer berikutnya dari node baru menunjuk ke kepala daftar dan buat node baru sebagai head. Untuk memasukkan pada akhirnya, cukup melintasi seluruh daftar dan pindah ke node terakhir, lalu buat pointer berikutnya dari titik satu terakhir ke yang baru. Misalkan, Anda ingin memasukkan node baru p antara dua node x dan y (daftar saat ini adalah x -> y). Kemudian, buatlah berikutnya dari titik ke y dan selanjutnya x menunjuk ke hlm. Daftar yang dihasilkan adalah x -> p -> y.

Hapus: Misalkan daftar saat ini adalah x -> y -> z. Untuk menghapus x, buat saja head point ke y dan hapus x. Untuk menghapus z, buat saja y berikutnya ke NULL dan hapus z. Untuk menghapus y, buat titik x berikutnya ke z dan hapus y (daftar hasilnya adalah x -> z).

Pencarian: Untuk mencari sebuah node, daftarnya harus dilalui mulai dari daftar utama.

2. Polynomial Representation
Masalah aritmatika polinom adalah membuat sekumpulan subrutin manipulasi terhadap polinom simbolis

(symbolic Polynomial).&nbsp; Misalnya:

P1 = 6x8 + 8x7 + 5x5 + x3 + 15

P2 = 3x9 + 4x7 + 3x4 + 2x3 + 2x2 + 10

P3 = x2 + 5

Terdapat empat operasi aritmatika polinom dasar antara lain:

Penambahan (P1 + P2 = 3x9 + 6x8 + 12x7 + 5x5 + 3x4 + 3x3 + 2x2 + 25)

- Pengurangan (P1 - P2 = - 3x9 + 6x8 + 4x7 + 5x5 - 3x4 - x3 - 2x2 + 5)

- Perkalian (P1 * P3 = 6x10 + 8x9 + 5x7 + x5 + 15x2 + 30x8 + 40x7 + 25x5 + 5x3 + 75 = 6x10+ 8x9 + 30x8+45x7 + 26x5 + 5x3 + 15x2 + 75)

- Turunan (P2'= 27x8 + 28x6 + 12x3 + 6x2 + 4x)

Representasi bilangan polinom dengan array :

int P1[10] = {0,6,8,0,5,0,1,0,0,15};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

int P2[10] = {10,0,2,2,3,0,0,4,0,3};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

int P3[10] = {5,0,1,0,0,0,0,0,0,0};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

3. Circular Single Linked List

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi Single Linked List Circular
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
Berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head

PEMBUATAN SINGLE LINKED LIST CIRCULAR
Deklarasi node
Dibuat dari struct berikut ini:
typedef struct TNode
int data;
TNode *next;
};

Penjelasan:
- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

4. Doubly Linked List
Double Link List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang.

Elemen double link list terdiri dari tiga bagian:
- Bagian data informasi
- Pointer next yang menunjuk ke elemen berikutnya
- Pointer prev yang menunjuk ke elemen sebelumnya

Untuk menunjuk head dari double link list, pointer prev dari elemen pertama menunjuk NULL. Sedangkan untuk menunjuk tail, pointer next dari elemen terakhir menunjuk NULL.
Contoh Membuat TDA(Tipe Data Abstrak) dari Double Linked Circular List tersebut.
Instan :
Double Linked Circular List
Operasi :
Buat_node(char x) : membuat node baru dengan informasi x
Tambah_elemen_didepan() : menambah elemen paling depan (pointernya menunjuk elemen pertama link list)
Tambah_elemen_dibelakang() : menambah elemen paling belakang (pointer elemen yang baru menunjuk elemen pertama)
Hapus_elemen_() : Menghapus elemen (pointer menunjuk elemen yang akan dihapus)
Cetak () : menelusuri elemen satu demi dan menampilkan informasinya.

5. Double Linked List Circular

Pengertian secara umumnya DLLCitu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer berikutnya “next“,
1 field menunjuk pointer sebelumnya ” prev “,
1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

Ilustrasi Double Linked List Circular

6. Header Linked List
Header linked list merupakan header spesial yang terdiri dari node headernya. Jadi, linked list jenis ini tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.

1- array and linked list - 2101656755 - Wantika Aprilia Wangke.

Sesi pertama pada pertemuan pertama ini kami membahas tentang konsep dasar struktur data yang akan sering digunakan dalam software engineering dan programming practices, konsep array, structure, stack, queue, graph, and trees.

Sub topics:

1.     Array Review

2.     Pointer Review

3.     Types of Data Structures

4.     Abstract Data Type

Berikut adalah penjelasan tentng sub topics yg ada::

1.  Array

Array adalah kumpulan dari data yang memiliki tipe data yang sama (homogenous). Untuk pemogramman c/c++ indeks array selalu bertipe integer yang dihitung dari angka nol [0]. Untuk mendeklarasikan array digunakan tanda [] (bracket). Pada Array kita harus memesan tempat terlebih dahulu maka tempat yang sudah kita pesan tidak bisa ditambah atau dikurangi lagi. Array di bagi menjadi beberapa macam antara lain:

·        Array Satu Dimensi

Pada dimensi ini variabel array hanya berisi satu dimemensi saja. Pendeklarasian array satu dimensi delakukan dalam benuk :

Tipe namaArray [];

Atau

Tipe [] namaArray;

Syntax:

Type name[size];

                        Size N ber index 0 to N-1.

           

Contoh :

Int arr[3] = {1,2,3}  // dimana indeks ke-0 sampai indeks ke-2 secara berurutan adalah 1,2,3.

·        Array dua Dimensi

Array dua dimemnsi merupakan array dari array, artinya terdapat sebuah array yang setiap elemen nya juga betipe array. Cara mendeklarasikan array dua dimensi dengan :

tipe namaArray [ ][ ];

atau

tipe  [ ][ ] namaArray;

Syntax:

      type name[size1][size2];

contoh :

 int array[1][2];

 indeks pertama dari array rangednya dari 0 sampai size1-1

 indeks kedua dari array rangednya dari 0 sampa size2-1

·        Array Multi Dimensi

Array multidimensi adalah suatu array yang mempunyai array lebih dari dua. Bentuk pendeklarasian array sama saja dengan array dimensi satu maupun array dimensi dua:

Tipe_data nama_Array[size1][size2]…[sizeN];

            Dalam Array multidimentional kita dapat membuat array hingga mencapai maksimal 256 dimana banyaknya tergantung pada compiler.

Operasi yang terdapat dalam Array:

1. Tranversal   : mencetak/mengolah semua elemen satu persatu

2. Insertion     : menambah sebuah elemen pada index.

3. Searching    : mencari suatu elemen array dengan menggunakan index atau nilai yang diberikan

4. Deletion      : menghapus sebuah elemen pada index tertentu

5. Merging      : penggabungan beberapa elemen

6. Sorting        : Menyortir

2.  Pointer

pointer adalah suatu data type dimana variabel nya menyimpan alamat dari variabel lain dan menyimpan nya di memory komputer sifatnya menunjuk pada alamat memori lain.

Dua operator yang paling penting dalam pointer yaitu;

·        &  (Aserisk)             menyimpan/mengambil alamat dari variabel

·        *   (Ampersand)      mengambil isi dari variabel nya

Cara pendeklarasian pointer:

Data_type*pointer_name;

Atau

Int x = 1;

Int *px = &x; 

// maka isi dari var px adalah alamat dari var x, dan var *px adalah 1.

Double pointer, example :

int x;

int **px;

Dari penjelasan diatas kita dapat mengambil kesimpulan perbedaan dari single pointer dan double pointer yaitu double pointer dapat digunakan untuk mengambil data dari variabel pointer yang lain sedangkan single pointer itu mengambil data variabel langsung dari induknya.

3.  Data Structures

Data structures adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secar efisien dan bersifat dinamis. Disebut juga sebagai jenis data kompleks atau data aggregates terdapat beberapa struktur data:

1.     Array

Kumpulan beberapa elemen sejenis yang memiliki tipe data yang sama, nilai nya terbatas dan tidak dapat dirubah lagi.

2.     Linked List

Adalah struktur data linier yang disebut nodes, diamana setiap mode akan menunjukkan pada node lain melalui sebuah pointer. Linked list dibentuk secara dinamik. Pada saat awal program dijalankan belum ada data.

Linked list memiliki 3 jenis yaitu:

Single link list.

Doube link list.

Mutiple link list.

3.     Queues

Queues adalah sistem data dimana memakai system data antrian dimana memiliki sifat FIFO “First In, First Out” dimana bari pertama disebut “front” dan baris paling belakang disebut “rear” . Dapat kita ambil contoh pada antrian orang mengambil uang di ATM dll. Jika memakai array diawal maka tidak dapat balik lagi ke awal.

4.     Stacks

Stuck memiliki sistem data dimana memakai system semacam tumpukan. Dimana struck memiliki sifat FILO (First In Last Out)  atau LIFO (Last In First Out). Kita dapat mengambil contoh pada tumpukan bola tenis yang berada pada dalam tabung.

5.     Binary Trees

Adalah suatu pohon struktur data dimana setiap simpul memiliki paling  banyak dua cabang, cabang tersebut dinamakan pointer kiri dan pointer kanan. Binary trees banyak di pakai di multi level, database, dan lainnya.

6.     Hash Table

Hash dulu dianggap tidak terlalu penting namun di zaman sekarang hash table banyak di pelajari oleh banyak orang dan sering digunakan.

4.  Abstract Data Type (ADT)

Abstract Data Type (ADT) adalah tipe data yang disusun sedemikian rupa sehingga spesifikasi objek dan spesifikasi operasi pada objek dipisahkan dari representasi objek dan pelaksanaan operasi. Jadi ini adalah sebuah tools untuk menghindari pemograman yang kompleks dengan cara penyederhanaan suatu program. Representasi, operasi dan tipe objek didefinisikan dalam single unit

C / C ++ memiliki konsep yang disebut class dan struct yang membantu programmer dalam mengimplementasikan tipe data abstrak.

Pada sesi 2 terdapat pembicara tamu yaitu bapak Samuel Theodorus sebagai Presiden Director dari sebuah perusahaan yang bernaung dalam bidang digital marketing yang sudah banyak melakukan relasi antara banyak perusahaan , yaitu PT. Elven Digital. Beliau menjelaskan tentang SEO dan perkembangan digital marketing di indonesia. Berikut ini merupakan beberapa materi yang di jelas kan oleh bapak Samuel.

SEO (Search Engine Optimazition)

SEO adalah sebuah usaha pengomtimalisasi website untuk mesin pencarian agar mendapatkan peringkat yang lebih baik di hasil pencarian.

Jenis SEO yaitu:

1.     On page SEO

2.     Off page SEO

Yang perlu dipelajari dari seo adalah pengoptimalan halaman website, riset kata kunci (keyword research), menganalisa kompeti, membuat konten yang teroptimalisasi, membangun populasi, link, dan reputasi, serta melakukan audit terhadap performa SEO.

            Sekian rangkuman pertemuan pertama Data Structure oleh Wantika Aprilia Wangke              2101656755.

Terima kasih...