WA comifuro 2

jika ingin bertanya sesuatu seputar PO dan barang : 

Nomor WA : 081381324093

BINARY SEARCH TREE

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.

Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.

contoh binary search tree dalam pemrograman java :

// A utility function to search a given key in BST
public Node search(Node root, int key)
{
// Base Cases: root is null or key is present at root
if (root==null || root.key==key)
return root;

// val is greater than root's key
if (root.key > key)
return search(root.left, key);

// val is less than root's key
return search(root.right, key);
}

ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data

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.

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

Gambar Binary Tree :



Data yang pertama bisa diturunkan ke data selanjutnya dan terbagi menjadi bagian bagian.Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.

Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Binary Tree dan hashing table

Pengertian dari hashing table adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif struktur yang dapat memetakan kunci ke nilai.Hashing table menggunakan fungsi hash untuk menghitung indeks,juga disebut kode hash,ke dalam array dari ember atau slot,dari mana nilai yang diinginkan dapat ditemukan.

Algoritma dalam hashing table :

index = f (key, array_size)

Hashing table dua langkah :

hash = hashfunc (kunci)
index = hash% array_size

Dalam metode ini, hash tidak tergantung pada ukuran array, dan kemudian dikurangi menjadi indeks (angka antara 0 dan array_size − 1 ) menggunakan operator modulo ( % ).

Jika semua kunci diketahui sebelumnya, fungsi hash sempurna dapat digunakan untuk membuat tabel hash sempurna yang tidak memiliki tabrakan. Jika hashing minimal sempurna digunakan, setiap lokasi di tabel hash dapat digunakan juga.

Gambaran Hashing Tree :



Binary tree adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

Ada 3 jenis binary tree yaitu:
1.Strict Binary Tree

Harus memiliki 2 anak,atau tidak punya sama sekali.

2.Complete Binary Tree

Harus punya anak dahulu dari yang paling kiri ke kanan.

3.Perfect Binary Tree

Semua harus punya anak dengan jumlah yang sama dan segitiga sempurna.

Selanjutnya ada yang dinamakan dengan binary search tree.Dimana pada tree ini data akan dimasukin ke sebelah kiri apabila lebih kecil dari nilai parent dan akan pergi ke sebelah kanan apabila nilai lebih besar dari parent.Hal ini akan terus berlanjut sampai menemukan nilai yang kosong/NULL.

Berikut merupakan cara untuk traversal dalam binary tree:
1.Inorder traversal

Berurutan berdasarkan nilai terkecil sampai terbesar.Dimulai dari paling kiri lalu dilanjutkan ke kanan dan mulai lagi ke paling kiri.

2.Preorder traversal

Mulai dari parent paling atas setelah itu ke kiri sampai leaf baru ke kanan.

3.Postorder traversal

Mulai dari child paling bawah kiri.Mulai dari leaf paling kiri lalu dilanjutkan ke kanan terus ke kiri dan kanan seterusnya.

gambaran Binary Tree :

LINKED LIST DAN PUSH

Linked list harus ada tail,head,curr,dan next.Yang pertama kali harus ditulis yaitu struct dalam bahasa kita yaitu merancang sesuatu.
Nama dari struct sendiri bisa diganti ganti.Push berfungsi untuk menggeserkan parameter yang ada kalimat pertama.Selain itu linked list mempunyai
dua istilah,yaitu double dan single.Perbedaannya terlihat penggunaan codingan next dan prev nya

contoh double linked list :

#include
struct node {
int value;
struct node *next;
struct node *prev;
};
struct node *head = 0;
struct node *tail = 0;

contoh single linked list :

#include
struct tnode {
int value;
struct tnode *next;
}*head,*tail,*curr;

struct tnode *head = 0;

int main()
{
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head = node;
}

kalau double linked list bolak balik untuk transfer data nya.kalau single linked list itu cuman memakai push dan next.
NULL dalam gambar pertama itu berfungsi sebagai tidak adanya data setelahnya lagi jadi jika di push lagi maka akan kembali ke bar pertama.
banyak programmer salah karena lupanya menulis "printf("%d\n",next->curr);" jika push tidak disertakan dalam int main ataupun program manapun maka program akan crash.

PERTEMUAN PERTAMA

Linked list DAN ARRAY

Apa itu Linked list ?

Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.

perbedaan Linked list dengan Array adalah pada saat program dijalankan.Array lebih memakan banyak memori daripada linked list.
Walaupun array yang dibuat sudah banyak namun tetap sama juga hasilnya karena linked list lebih efesien.

Salah satu ciri Array adalah perlu ditentukan ukurannya sebelum dapat digunakan. Karena perlu pengalokasian di memory.

Array menggunakan indeks integer untuk menentukan urutan elemen-elemennya, dimana elemen pertamanya dimulai dari indeks 0,elemen kedua memiliki indeks 1, dan seterusnya.jadi dengan adanya indeks, dimungkinkan untuk pengaksesan secara acak (random Access).

Berbeda dengan linked list yang Tidak ada unsur Random Access via indeks seperti Array dan setiap operasi biasanya perlu operasi sekuensial dari node awal.

CONTOH CODINGAN ARRAY
#Menghapus data berdasarkan index
del Arr[index]
Arr.pop(index)
Arr.pop() #remove data terakhir
#Remove data berdasarkan data
Arr.remove(data)