Binary Search Tree

Nama : Sofyan Adrianto

NIM : 2301869121

Jurusan : TI dan Statistika

Binary Search Tree

hari selasa saya belajar dari pak Henry Chong,dan beberapa tambahan dari internet:

Konsep binary tree dengan binary search tree yang kita pelajari minggu lalu pada dasarnya sama,selama dia ada kata binary,artinya kakinya ada 2,bi artinya 2.Ternary artinya 3 kaki, ada yang namanya ternary tree, yang kakinya 4 juga ada.

Apa bedanya binary tree sama binary search tree?

kakinya sama yaitu, di binary search tree ada kata search tree yang berarti mencari pohon.Kalo di Binary Tree gaad aturan penempatan,semua bebas taro mana aja(gaharus sebelah kiri lebih kecil,dan disebelah kanan harus lebih besar). Kalo di Binary search tree ada aturannya. Aturan yang biasa dipakai di binary search tree yaitu :

1. Sebelah kiri lebih kecil dari parentnya.

2. Sebelah kanan lebih besar dari parentnya.

Kalo di beberapa buku(biasanya buku lama) ketemu sebelah kanan lebih kecil, kiri lebih besar. Itu sama aj,konsepnya sama, yang penting konsisten.

Ada beberapa fungsi:

1. Find

untuk mencari tree

dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

2. Insert

Biasanya kita mengenal insert dengan fungsi "push" untuk memasukkan data.

Operasi: Insertion BST

Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :

• Dimulai dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
• Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

3. Delete

Biasanya kita mengenal delete dengan fungsi "pop" untuk membuang data.

akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

• Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri).

Binary Search Tree: proses pencarian (SEARCHING) berbasis binary tree

Tree traversal adalah cara kunjungan node-node pada pohon biner. Ada tiga cara

kunjungan dalam tree:

• Pre-order

• In-order

• Post-order

1. Pre-order

a. Cetak data pada root

b. Secara rekursif mencetak seluruh data pada subpohon kiri

c. Secara rekursif mencetak seluruh data pada subpohon kanan

2. In-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Cetak data pada root

c. Secara rekursif mencetak seluruh data pada subpohon kanan

3. Post-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Cetak data pada root

Hash,Hashing Table,Binary tree

Nama : Sofyan Adrianto

NIM : 2301869121

Jurusan : TI Statistika

HASHING TABLE

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Ide Dasar

Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Misalkan kita memiliki string "abca", dan fungsi f yang memetakan string ke bilangan bulat berikut:

f(S) = (

(banyaknya 'a')*1 +

(banyaknya 'b')*2 +

(banyaknya 'c')*3 +

... +

(banyaknya 'z')*26

) mod 1000000

Artinya:

f("abca") = (2*1 + 1*2 + 1*3 + 0*4 + 0*5 + ... + 0*26) mod 1000000

= 7

Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).

Hashing

Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan hash pada string menjadi bilangan.

Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:

T["Sofyan"] = 3;

printf("%d\n", T["Sofyan"]);

Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.

Perhatikan bahwa key tidak harus berupa string. Tipe data apapun dapat didukung, asalkan didefinisikan fungsi hash-nya. Kalau untuk value, tentu saja datanya bisa bertipe apapun.

Operasi minimal yang perlu didukung oleh hash table adalah:

Diberikan key X dan value Y, catat bahwa value dari X adalah Y. Operasi ini dapat dianggap "T[X] = Y".

Diberikan key X, cari value-nya. Operasi ini dapat dianggap seperti mengakses "T[X]".

Kedua operasi ini akan saya sebut sebagai update dan read. Kompleksitas operasi-operasi ini adalah O(K), dengan O(K) adalah kompleksitas melakukan hash pada suatu key.

Fungsi Hashing

Pada bagian sebelumnya, saya memberi contoh fungsi hashing sederhana. Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:

Untuk dua buah key yang sama, hasil hashing-nya selalu sama.

Memiliki kompleksitas rendah.

Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Pada kebanyakan kasus, kompleksitas fungsi hash dapat dianggap O(1). Sehingga operasi update dan read bekerja dalam O(1).

Hashing Table pada Blockchain

Secara sederhana, hashing berarti mengambil string input dengan panjang berapapun dan memberikan output dengan panjang tetap. Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (bitcoin menggunakan SHA-256) yang memberikan output dengan panjang tetap. 

Binary tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

Konsep tree:

Root : Node di paling atas

Edge: Garis yang menghubungkan parent dengan child

Leaf: node yang tidak mempunyai anak

Siblings: node yang mempnyai parent yang sama

Degree: total subtree dari sebuah node

Height/depth: maksimum degree dari sebuah tree

jika ada garis yang menghubungkan a kepada b, a disebut ancestor dari b dan b adalah descendant dari a.

Jenis-jenis Binary Tree

1. Full Binary Tree, yaitu Binary Tree yang tiap nodenya ( kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
2. Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
3. Skewed Binar Tree, Yakni Binary Tree yang semua nodenya(kecuali leaf) hanya memiliki satu child.

Binary Search Tree Adalah binary tree dengan sifat bahwa semua left child harus lebih kecil dari right child dan parentnya. Juga semua right child harus lebih besar dari left child serteparentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.  Pada dasarnya, operasi dalam binary search tree dama dengan binary tree biasa, kecuali pada operasi insert, update, dan delete.

1. Operasi insert, Pada binary search tree, insert dilakukan setelah ditemukan lokasi yang tepat. (loksi tidak ditemukan oleh user sendiri )
2. Operasi search, Seperti pada binary tree, biasa, namun disini. Update akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan binary  search tree lagi, maka harus dilakuakn perubahan pada tree dengan melakukan perubahan rotasi supaya tetap menjadi binary  seacrh tree.
3. Operasi Delete, Seperti halnya update, delete dalam binary search tree juga turut mempengaruhi struktur dati tree tersebut. Pada operasi delete, diakukan terhadap node dengan 2 child, maka untuk menggantikannya, diambil node paling kiri dari right subtree.

ringkasan data struct 3 maret

Nama : Sofyan Adrianto

NIM : 2301869121

Jurusan : TI dan Statistika

Hari ini saya belajar:

Perintah malloc digunakan untuk memesan memori.

Dalam single linked list terdapat sebuah perjanjian yaitu head(selalu pegang paling depan) yang merupakan awal dari linked list(paling depan),biasanya tidak boleh berpindah,jika berpindah bisa terjadi salah coding dan setiap node tidak memiliki tali penghubung. Ada juga yang namanya current(biasa disingkat curr) ini bisa berpindah2 posisinya. Tail selalu pegang paling belakang. Nama tidak memengaruhi asalkan fungsinya sama seperti yang diatas.

Pemesanan memori atau yang biasa kita kenal malloc,bisa dilakukan sekali saja,jika kita menggunakan fungsi malloc yang sama berulang kali,maka memori yang dipesan bertambah banyak. Kesimpulannya jadi kurang efisien jika memesan memori berulang kali. Jadi yang harus kita lakukan adalah memesan memori (menggunakan malloc) dapat dilakukan sekali saja.

Setelah kita pesan memori, di dalam memori terdapat sebuah tempat untuk menaruh value. Value ini dapat kita isi dengan nilai seperti 10,20,30,dst.

Value tersebut dapat di print out ,berikut contoh coding singkatny

Curr= (struct data*)malloc(sizeof(struct data));

Curr->value = 10;

Printf(“%d\n”,Curr->value);

Harusnya angka 10 ter-print.

Ketika kita hanya memesan memori 1 kali,disaat kita  memasukkan nilai value yang baru = 20,maka nilai seblumnya,yaitu 10 akan terganti dengan 20.

Jika kita memesan memori berkali2,ketika kita ingin mengakses data pertama,it dtidak dapt dilakukan karna tidak ada jalan untuk kembali,karena memori itu sudah ditingglkan tapi memori itu masih ada dan gaakan pernah bisa dipakai. Intinya kita harus berhati2 dlm menggunakan malloc.

Prinsip sederhana linked list adalah bagaimana caranya supaya list yang sudah ditinggalkan tadi bisa diakses dan terhubung satu sama lain.

Jika kita ingin datanya menyatukan sebuah gerbong,dengan gerbong yang lain,maka kita harus tau dulu bahwa di dalam gerbong terdapat value. Dan kita dapat menggunakan next,untuk menyimpan alamat sebelah saya.dan alamat sebelahnya sebelah saya, dst. Karena next tugasnya menyimpan alamat di sebelahnya makanya next itu diberi pointer.

Kita dapat membua fungsi,misalnya namanya push atau insert atau apapun. Yang fungsinya untuk insert data. Misal kita membuat :

Push(10); maka gerbong pertama akan diisi nilai 10.

Dalam struct data ad 2 variabel yang bisa dikasih nilai yaitu,value dan next. Dimana value hrus diisi dengan integer,dan next harus diisi dengan alamat.

Untuk mengecek apakah list tersebut berhasil disambungkan kita bisa mengetahuinya melalui hasil dri print out nya.

Biasanya di data struct,bukan syntax yang error,tapi logicnya.

Kalau baru di push 1x, lalu kita next. Maka pas di run maka akan error. Kenapa dia bisa error? Karena disaat kita push 1x,maka head memang sudah ana valuenya. Namun ketika kita ketik head->next. Maka next nya kan null yaa,null kan tidak punya value. Tapi dri null itu kita mau akses valuenya, itu yang menyebabkan error.

Yang bisa kita print yaitu cth: head->value,head->next,curr->value,dll.

Buat hapus memori kita menggunakan syntax seperti free(curr). Kelebihannya linked list bisa mengemat memori,klo array gabisa dibuang.

Fungsi pop,berfungsi untuk menghapus dapat dilakukan dengan free. Namun perlu diingat bahwa free bukan berarti dibuang, bila data yang di free ingin digunakan sewaktu2 masih bisa.

Head sama tail Cuma bakal jadi satu kalo datanya sisa 1.

Double linked list, sama kayak single linked list. Tapi dia bisa mundur,ga Cuma searah. Tugas kita kalo ingin membuat double linked list adalah memastikan bahwa coding kita membuat setiap gerbong saling berkaitan(2arah) shg bisa maju dan mundur. Linked list bisa pnya 8 tangan,bisa ngecek 8 arah.

Circular linked list tail->next = head,head->prev=tail. Jadi muter gitu.

Tambahan dari bacaan di internet.

Stack

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Operasi-operasi dasar dalam stack ada 2 yaitu operasi push dan pop:

• Operasi push, berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas. 

Queue
pengertian queue dalam struktur data

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Algoritma Stack

a. Operasi Push

Operasi push digunakan untuk menambahkan sebuah elemen baru ke atas tumpukan. Operasi ini dapat dilakukan jika tumpukan tidak penuh.  Algoritma operasi push pada stack adalah sebagai berikut:

• Menentukan kondisi tumpukan, apakah tumpukan dalam keadaan kosong atau tidak.
• Jika kosong maka mendeklarasikan data baru yang akan dimasukkan ke dalam tumpukan.
• Memasukkan nilai data yang baru.
• Melakukan perulangan untuk memasukkan data hingga batas penuh tumpukan.
• Jika tumpukan sudah penuh maka selesai.

b. Operasi Pop

Operasi pop digunakan untuk menghapus elemen teratas dari tumpukan. Algoritma operasi pop pada stack adalah sebagai berikut:

•  Melakukan pengecekan kondisi antrian, ada isi data atau tidak.
•  Jika terdapat data pada antrian, maka lakukan penghapusan data dengan cara memindahkan head (elemen teratas tumpukan) ke elemen dibawahnya.
• Kemudian menghapus elemen teratas tumpukan.
• Jika tidak terdapat data pada tumpukan maka selesai.

Perbedaan stack dan queue

• Stack merupakan tumpukan sedangkan queue merupakan antrian.
• Stack bersifat LIFO (Last in first out) yang artinya data yang terakhir masuk adalah data yang pertama keluar sedangkan queue bersifat FIFO ( First in first out) yaitu data yang pertama masuk akan pertama kali keluar.
• Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas akan dihapus paling awal (LIFO). Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan (FIFO).

• Operasi pop, berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah. ^[5] Berikut ilustrasi kerja pada operasi pop: