Hashing Table & Binary Tree

Muhamad Rafif Hadi Kusmawan
2301913154
CD - 01

Hashing Table

Hashing Table adalah struktur data yang digunakan untuk menyimpan pasangan kunci / nilai. Ini menggunakan fungsi hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari. Dengan menggunakan fungsi hash yang baik, hashing dapat bekerja dengan baik. Di bawah asumsi yang masuk akal, waktu rata-rata yang diperlukan untuk mencari elemen dalam hash table.

dibawah ini ada beberapa fungsi hash untuk mengubah string menjadi key

1. Mid - Square

2. Division (most common)

3. Folding

4. Digit Extraction

5. Roating Hash

Fungsi hash adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut hash value, hash codes, hash sums, or simple hahses.

Binary Tree

Binary Tree adalah structrur data tree di mana setiap node setiap node paling banyak memiliki 2 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.

dibawah ini ada beberapa jenis binary tree

1. Perfect Binary Tree: pohon biner yang setiap level (kedalaman) nya berada di kondisi yang sama.

2. Binary Tree Lengkap: satu pohon biner yang kedalamannya berjumlah n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama sekali, boleh saja tanpa atau tidak.

3. Pohon biner miring: Setiap pohon biner yang setiap nodenya hanya memiliki 1 anak.

4. Pohon Biner Seimbang: satu pohon biner yang tinggi di antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.

Data Struct

Muhamad Rafif Hadi Kusmawan
2301913154
CD - 01

Linked List

Linked List adalah structer data linear, yang dimana elemen tidak tersimpan di lokasi memori dengan jarak yang berdekatan. Elemen - elemen dalam linked list yang akan dihubungkan menggunakan pointer seperti gambar yang ada di bawah ini :

Linked List yang hanya terdapat satu penghubung ke node lain disbut single linked list. Dalam linked list, pointer Head yang menunjuk pada node pertama dalam linked list tersebut.

Linked List akan dikatakan kosong apabila isi pointer Head adalah NULL.

Berikut adalah beberapa operasi yang terdapat dalam sebuah linked list:

1. Push

            adalah sebuah operasi insert dimana dalam linked list terdapat 2 kondisi insert, yaitu melalui depan (push depan) dan belakang (push belakang). Jadi push(depan) ketika ada data yang baru maka akan berada di depan data lainnya, sedangakan push(belakang) sebaliknya dari push(depan) berati ketika ada data yang baru makan akan berada di belakang data lainnya.

Contoh :

- Push Depan : 2, 4, 6, 8 hasilnya adalah : 8 -> 6 -> 4 -> 2 -> NULL
- Push Belakang : 2, 4, 6, 8 hasilnya adalah : 2 -> 4 -> 6 -> 8 -> NULL


2. Pop

            adalah sebuah operasi untuk delete, kebalikan dari Push. Dan dalam linked list terdapat 2 kondisi delete yaitu, delete dari depan (Pop Depan) dan delete delete dari belakang (Pop Belakang). perbedaannya adalah, Pop Depan adalah data yang akan di hapus berada di paling depan dan Pop Belakang adalah data yang akan di hapus berada di paling belakang.

Single Linked List

single linked list merupakan tempat yang disediakan pada satu area memori untuk menyimpan adata dengan kata lain node atau simpul. Dan setiap node memiliki pointer yang menunjuk ke node berikutnya, dengan demikian hanya diperlukan variable pointer. Dalam pembuatan single linked list terdapat 2 metode pembuatannya yaitu :

- LIFO (Last In First Out), seperti -> Stack (tumpukan)

- FIFO (First in First Out), seperti -> Queue (antrian)

Double Linked List

dalam double linked list berbeda halnya dengan single linked list yaitu, hanya terdapat satu pointer yang bergerak ke satu arah dalam single linked list dan dalam double linked list terdapat dua pointer yang bergerak ke dua arah. Contohnya seperti gambar yang dibawah ini :

Circular Double Linked List

adalah double linked list yang node awalnya menuju ke node terakhirnya dan node terakhirnya menuju ke node awalnya, sehingga terbentuk suatu lingkaran yang saling terhubung.

Macam - macam operasi dalam linked list :

- Insert

fungsinya adalah untuk menambahkan sebuah node baru kedalam suatu linked list.

- IsEmpty

fungsinya adalah untuk menentukan apakah linked list kosong atau tidak.

- Find First

fungsinya adalah untuk mencari elemen pertama pada linked list.

- Find Next

fungsinya adalah untuk mencari elemen sesudah elemen yang di tunjuk now.

- Retrieve

fungsinya adalah untuk mengambil elemen yang di tunjuk oleh now. Elemen tersebut kemudian          dikembalikan oleh fungsi.

- Update

fungsinya adalah untuk mengubah elemen yang di tunjuk oleh now dengan isi dari sesuatu.

- Delete Now

fungsinya adalah untuk menghapus elemen yang di tunjuk oleh now. Jika yang di hapus adalah elemen yang pertama dari linked list (head), maka (head) akan berpindah ke elemen berikutnya.

- Delete Head

fungsinya adalah untuk menghapus elemen yang ditunjuk oleh (head). (head) berpindah ke elemen sesudahnya.

- Clear

fungsinya adalah untuk menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan apabila ingin mengakhiri dari sesbuah program yang menggukan linked list. Jika melakukannya maka, data - data yang dialokasikan ke memori pada sesbuah program sebelumnya akan tetap tertinggal dalam memori.