datStruct-4

BINARY SEARCH TREE

Binary search tree(BST) adalah bentuk turunan dari binary tree. binary tree adalah tree yang hanya memiliki 2 node. pada BST, node kiri selalu bernilai lebih rendah dan node kanan selalu bernilai lebih besar.

*Dengan BST, segala insertion, deletion, dan search dapat dilakukan dalam Olog(N) (N=jumlah node pada tree). Akan berguna dalam kasus N nya berjumlah banyak.

*Karena semua tersusun dengan rapi, maka pencarian dapat dilakukan dengan mudah.

3 Operation utama dalam BST:
1. find()
2. insert()
3. remove()








INSERT()

insert(x,root)// node dimulai dari root karena root merupakan level paling dasar pada tree.

(t == null) // artinya node tersebut belum terpakai dan node baru akan disimpan di tempat itu sebagai leaf (left dan right = NULL)



//bila x lebih kecil dari node, maka lakukan insert dengan node->left sebagai node currentnya. begitu juga bila x lebih besar, maka node->right sebagai node current.






REMOVE()

untuk remove(), perlu diperhatikan apabila node yang dihapus bukan leaf (node memiliki 2 sub tree), maka node itu perlu di replace dengan kanan paling kecil atau kiri paling besar









//findMin(t->right) : untuk mencari node terkecil pada right sub tree
//node yang akan di remove di replace dengan temp
//kemudian lakukan remove pada node original yang digunakan pada temp
//deletion bisa juga menggunakan findMax(t->left) ,dengan kiri paling besar


//bila node yang ingin dihapus hanya memiliki 1 child, maka hubungkan parent dari node dengan child dari node










FIND()

//jika key lebih besar daripada current node, maka node yang dicari pasti berada di kanan current node
jika lebih kecil, maka di kiri.

datStruct-3

1. HASHING

Hashing adalah sebuah data struktur dengan fungsi bernama "Hash Function" yang dapat mempersingkat proses untuk mengakses suatu element di dalam list.

Hash table adalah table yang berfungsi untuk menampung value dan index dari sebuah key. value berisi string dan index berisi hashed key dari string tersebut.

Cara mendapatkan hashed key dari sebuah string adalah dengan menggunakan sebuah formula/metode yang mempersingkat string tersebut.

Sebagai contoh, terdapat sebuah list yang berisi 11, 12, 13, 14, 15. salah satu cara untuk mendapatkan Hashed Key dari masing masing data adalah dengan metode "Division", yaitu dengan fungsi
H(x) = [x % M),
x = key
M = value yang digunakan untuk membagi key, biasa berupa angka prima, size dari hash table, atau size dari memory yang digunakan.

*Metode Division adalah Metode yang paling sering digunakan umumnya.

Berikut adalah metode yang dapat digunakan sebagai Hash Function:

1. Mid-square

Men-kuadratkan value dari key, lalu mengambil nilai pada digit tengah sebagai hashed key.
contoh : key = 3121
              squared value = 9740641
              hashed key = 406

2. Division

3. Folding

Membagi key menjadi beberapa part, setiap part berisi paling banyak 2 digit, kemudian menjumlahkan setiap partnya.

4. Digit extraction

Menentukan digit berapa saja yang akan digunakan untuk mengambil nilai sebagai Hashed key.
contoh: digit 1, 3, 5. key = 123456. hashed key = 135.

5. Rotating Hash

Dimulai dengan menggunakan metode 1,2,3,4, dan merotate hashed key.
contoh: hashed key = 40989. rotate menjadi 98904.


Collision
yaitu sebutan apabila ada 2 key yang memiliki hashed key yang sama, istilahnya bertabrakan.
contoh:
jika ada hash function yang mengambil char paling pertama, maka string Andi dan Anton akan memiliki hashed key yang sama yaitu 0. (karena A=0, B=1, C=2, dst).

Untuk mengatasi collision, digunakan 2 cara, yaitu:

1. Linear Probing
Dengan mencari tempat yang kosong selanjutnya pada table.
Misal jika tadi Andi ditempatkan pada 0, maka Anton ditempatkan pada 1.
Namun linear probing sedikit tidak efektif karena dapat melakukan banyak perulangan untuk mencari value yang memiliki hashed key yang sama.

Misal jika urutan stringnya adalah Andi, Budi, lalu Anton, maka Andi=0, Budi=1, Anton=2.
sedangkan Anton seharusnya 0, maka akan dicari index 0 dan jika bukan anton, akan melakukan iterasi hingga menemukan value Anton.

2. Chaining
Metode ini menggunakan Linked List, jadi jika ada string Andi, Budi Anton
Andi=0, Budi = 1, Anton = 0 -> next.



2. BINARY TREE

Binary Tree adalah bentuk dari tree dimana tiap node hanya dapat memiliki cabang maksimum 2 (left and right).

Contoh BINARY TREE

*Node paling atas disebut root.
jadi root pada gambar : 8

*Node yang tidak memiliki child disebut leaf.
jadi leaf pada gambar : 1,4,7,13

















Binary Tree dibagi lagi menjadi 4 type :

1. Perfect Binary Tree (termasuk complete binary tree, setiap level memiliki depth yang sama)
2. Complete Binary Tree (setiap level, kecuali terakhir, memiliki depth yang sama)
3. Skewed Binary Tree ( setiap node hanya memiliki 1 child)
4. Balanced Binary Tree (suatu leaf tidak melebihi leaf lainnya sebanyak 1)

Binary Tree dapat direpesentasikan dengan menggunakan Array dan Linked  List

*Array

*Linked List

datStruct-2

STACK

stack adalah data structure yang menyimpan kumpulan element, mirip seperti array dan linked list.
namun, operasi pada stack yaitu insert dan deletion hanya dapat dilakukan pada 1 sisi, yang umumnya disebut "TOP".

apabila di dalam linked list kita dapat insert middle, before, after, pada Stack kita hanya dapat melakukan insert head.

prinsip stack yaitu last-in first-out (LIFO)

analogi : seperti tumpukan piring, kita dapat memindahkan/menabahkan piring hanya dari paling atas.

stack dapat di representasikan dalam bentuk ARRAY dan LINKED LIST. dalam teknik pembuatan mungkin array lebih mudah, namun kelemahan array dibanding linked list yaitu pada array perlu mendeklarasikan jumlah dari element itu.

operation pada stack:
1. push() : yaitu  untuk menambahkan suatu element / item paling atas
2. pop()  : untuk memindahkan / remove suatu element yang paling atas
3. top() : untuk mengembalikan nilai dari element yang paling atas

Stack juga digunakan pada notasi postfix dan prefix.
infix : 4 * 10                  (normal)
prefix : * 4 10                (operator ditulis sebelum operand)
postfix : 4 10 *              (operator ditulis setelah operand)

prefix dan postfix akan memudahkan komputer dalam membaca operasi matematika.
kompleksitas pada infix : O(N^2)                  *N = panjang string
sedangkan pada postfix dan prefix : O(N)

dengan STACK, komputer dapat membaca notasi postfix dan prefix lebih cepat dibanding infix.

4 + 5 * 6 pada POSTFIX

1. push(4)
2. push(5)
3. push(6)
4. pop(5), pop(6), push(5*6)
5. pop(30), pop(4), push(30+4)

result = 34








kita juga dapat melakukan conversion dari infix  ke postfix dan prefix dengan menggunakan stack.

DEPTH FIRST SEARCH (DFS) yaitu sebuah algoritma untuk menelusuri atau mencari pada sebuah tree atau graph. pertama-tama, kita memulai dari root kemudian terus berjalan hingga ke cabang cabang berikutnya sebelum backtracking.

VISIT ORDER : A , C , B , E, D

QUEUE

apabila prinsip stack adalah last-in first-out (LIFO), pada queue prinsipnya adalah first-in first-out (FIFO). inilah yang membedakan stack dengan queue.

analogi : ketika mengantri bus, orang yang mengantri paling dahulu akan masuk ke dalam bus paling dahulu pula. orang paling terakhir akan masuk paling terakhir.

sama seperti stack, queue dapat dipresentasikan dengan ARRAY dan LINKED LIST.
apabila pada stack menggunakan "TOP", pada queue kita menggunakan "FRONT" dan "REAR".
setiap INSERTION akan dilakukan pada REAR, dan setiap DELETION akan dilakukan pada FRONT.

operation dalam queue:
1. push() : yaitu  untuk menambahkan suatu element / item ke antrian / queue paling belakang (rear)
2. pop()  : untuk memindahkan / remove suatu element pada antrian paling depan (front)
3. front() : untuk mengembalikan nilai dari item yang berada paling depan (front) dari antrian

apabila menggunakan array, maka dapat terjadi suatu  kondisi apabila kita melakukan push sebanyak size array, lalu pop sebanyak size array, lalu ketika kita push lagi data akan tersimpan diluar array tersebut. untuk menanggulangi hal ini, dapat digunakan CIRCULAR QUEUE

pada circular queue, digunakan wrap-around index L dan R.
jika R mencapai size maksimum dari array, maka R akan di set ke 0, begitupula dengan L.

BREADTH FIRST SEARCH (BFS) sama seperti DFS pada queue.
apabila DFS menggunakan STACK, pada BFS menggunakan QUEUE.