Hash Table & Binary Tree

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

Hash table itu sebenarnya hanya array biasa saja, hanya penempatan posisi nilainya itu tergantung fungsi hash dari kuncinya.

Karena posisinya sudah ditentukan dengan fungsi hash, kita sudah tidak perlu mikir lagi taruh di posisi array sebelah mana. Pokoknya kita tahunya kunci dan nilainya.

class Map:

  def __init__(self):

    self.data = [None] * 30

  def set(self, key, value):

    self.data[hash(key) % len(self.data)] = value

  def get(self, key):

    return self.data[hash(key)]

Kita bisa menggunakan fungsi hash apapun yang dapat memastikan tiap kunci itu unik, tapi karena keterbatasan ukuran array, sangat mungkin terjadi tabrakan(collision). Maksudnya tabrakan itu, dua kunci atau lebih mendapat posisi yang sama. Okelah fungsi hash sudah unik, tapi karena kita menggunakan modulo untuk menyesuaikan ukuran array, bisa saja dua kunci yang jauh berbeda mendapat posisi yang sama.

 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.

Operasi-operasi pada Binary Tree :

1.      Create : Membentuk binary tree baru yang masih kosong.

2.      Clear : Mengosongkan binary tree yang sudah ada.

3.      Empty : Function untuk memeriksa apakah binary tree masih kosong.

4.      Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

5.      Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

6.      Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

7.      Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

8.      DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

9.      Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

10.  Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

-        PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

-        InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

-        PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi