Hash Table And Binary Tree

 HASH TABLE                                                                                                                        
       Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain. keunggulan dari Hash Table adalah waktu mengakses lebih cepat.

• Operasi pada Hash Table

                insert: diberikan sebuah key,insert nilai dalam tabel

                find   : diberikan sebuah key,menemukan nilai yang berhubungan dengan key

                remove: diberikan sebuah key,menemukan nilai yang berhubungan dengan key kemudian                                    di hapus nilai tersebut.

                getiterator: mengembakikan iterator, yang memeriksa nilai satu demi satu. 

• Metode untuk membangun Hash function:

            1.Mid Square       :  Mengkuadratkan nilai yang di dapat lalu beberapa digit ditengah diambil                                              yang nanti akan menjadi nilai hash nya.

            2.Division            :Sebuah String  dibagi menggunakan operasi Modulus.

            3.Folding             :Membagi nilai key ke beberapa bagian kemudian dijumlahkan. lalu itu                                                   sebagai  nilai hasnya.

            4.Digit Extraction: Dengan mengambil digit dari urutan nomor yang sudah ditentukan.

            5.Rotating Hash   :Menggunakan salah satu metode sebelumnya kemudian hasil dari nilai                                                   di acak kembali untuk mendapatkan alamat hash yang baru.

BINARY TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut  terpisah.  maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis jenis Binary tree

1.Full Binary Tree: 

tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

2.Complete Binary tree: 

tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

3.Skewed Binary Tree:

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Impelementasi Binary Tree

Create          : Membentuk binary tree baru yang masih kosong.

Clear            : Mengosongkan binary tree yang sudah ada.

Empty          : Function untuk memeriksa apakah binary tree masih kosong.

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.

Find              : Mencari root, parent, left child, atau right child dari suatu node.tree tak boleh kosong

Update          : Mengubah isi dari node yang ditunjuk oleh pointer current. tree tak boleh kosong

Retrieve         : Mengetahui isi dari node yang ditunjuk pointer current. tree tak boleh kosong

DeleteSub      : Menghapus sebuah subtree  yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

Characteristic : Mengetahui karakteristik dari suatu tree, yaitu: size, height, serta average lengthnya. Tree tidak boleh kosong. 

Traverse         : Mengunjungi seluruh node-node pada tree, masing-masing sekali.  Adatiga cara traverse : Pre Order, In Order, dan Post Order.