BINARY SEARCH TREE

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. It allows us to support faster searching, rapid sorting, and easy insertion and deletion.

Binary Search Tree has the following basic operations:

·        find(x)                   : find key x in the BST

·        insert(x)               : insert new key x into BST

·        remove(x)            : remove key x from BST

Cara Kerja :

• Find

Metode ini ga jauh beda sama insert Cuma metode ini lebih rumit aja. Input X yang akan dicari lalu dia akan terus mencari sampai ketemu dengan kondisi jika X lebih kecil dari root key maka dia akan mencari di sebelah kiri dan sebaliknya. Pencarian akan di lakukan berulang sampai ketemu.

• Insert

Input X untuk di cari. Lalu bandingkan dengan tree paling atas, jika lebih besar taro di sebelah kanan jika lebih kecil taro di sebelah kiri. Akan di lakukan terus sampai ketemu.

• Remove

Np : Cuma mau kasih tau kalo BBT ini kemaren di jelasin di kelas gede dia itu di pake di pembuatan game NFS a.k.a Need For Speed. Jadi ternyata gw juga baru tau kalo mobil di NFS itu ngga bergerak dan yang bergerak itu backgroundnya menggunakan si insert dan remove itu. Itu aja sih fact nya. Thankyou.

HASHING TABLE

Hash Table

Hash table adalah sebuah table yang isinya adalah sebuah data yang berfungsi untuk memetakan nilai kunci unik untuk setiap baris menjadi angka lokasi record tersebut di dalam tabel. Hash tabel sendiri memiliki sebuah kelebihan yaitu waktu aksesnya cepat sehingga jika ada record yang di cari maka langsung terletak pada angka hash lokasi storage nya.

Fungsi Hashing

Sebenarnya fungsi hashing itu bebas, terserah kalian ingin mendefinisikannya seperti apa. Tapi, berikut adalah fungsi hashing yang di harapkan :

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

·        Memiliki kompleksitas rendah.

·        Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Ada beberapa operasi pada Hash tabel :

·        - Insert

·        - Find

·       -  Remove

·       -  getIterator

Hash collision

Perhatikan bahwa jumlah kemungkinan kunci sangat banyak. Jika kunci adalah nama, jumlah kemungkinan nama tersebut sangat banyak, sedangkan jumlah sel dalam hash table terbatas. Hal ini bisa memungkinkan terjadinya collision.

Karena collision tidak mungkin terhindarkan, implementasi hash table harus menentukan apa yang harus dilakukan bila terjadi collision. Salah satu cara yang banyak dipakai yaitu dengan mengijinkan lebih dari satu nilai dalam satu lokasi. Umumnya hash table menggunakan struktur data linked list untuk menyimpan lebih dari satu nilai dalam satu lokasi yang sama.

Bila data akan dimasukkan ke dalam bucket yang sudah ada isinya (collision terjadi), maka operasinya tidak sesederhana pada kasus bucket kosong. Mari kita perhatikan animasi yang saya buat di bawah ini.

Ketika memasukkan data (insert), pada bucket yang tidak kosong maka perlu dilakukan operasi komparasi kunci untuk melihat apakah kunci yang sama sudah ada di bucket itu atau belum. Bila kunci yang sama ternyata ada di situ, artinya operasi insert berubah menjadi operasi update, yaitu mengubah data yang lama dengan yang baru. Bila kunci yang dimasukkan tidak ada di situ, maka kunci dan data yang dimasukkan akan disimpan di node paling akhir dari bucket tersebut.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

• Linear Probing
• Quadratic Probing
• Double hashing

2.   Open hashing

Pada dasarnya open hashing membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Stack and Queue

Tentang prefix dan postfix:

• ·        Postfix itu caranya dengan menaruh semua operator di sebelah kanan dan mulai di scannya dari sebelah kiri. Lalu setiap angka yang bertemu dengan sebuah operator, maka angka tersebut akan di kalkulasikan dengan 1 angka sebelum angka tersebut dan hasilnya berada di posisi yang sama. Cara tersebut akan di lakukan terus sampai semuanya terkalkulasi.
• ·        Prefix itu hanya beerbeda dari mana mulainya. Kalau postfix semua operator di taruh di sebelah kiri, prefix kebalikannya. Begitu juga dengan cara menghitungnya, kebalikan dari postfix.

Stack

Sebuah penyimpanan data yang tersusun secara linear. Hanya ada 1 jalan keluar sehingga jika ada yang di taruh di atas atau paling terakhir, maka yang di paling atas atau terakhir juga yang di keluarkan atau di sebut dengan last in first out (LIFO).

Queue

Berbeda dengan stack, queue akan menyimpan sebuah data dengan lebih terstruktur. Ibaratnya seperti kita mengantri yang pertama datang yang pertama di layani atau di sebut first ini first out (fifo).